J - Grid Construction Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

Score: 100 points

Problem Statement

You are given positive integers H and W. You aim to draw an H-row by W-column grid on the coordinate plane using several "U-shapes."

To draw one U-shape, perform the following operation:

  • Choose integers 1 \le x \le H and 1 \le y \le W.
  • From the following four line segments, select any three distinct ones:
    • The line segment connecting (x-1, y-1) and (x-1, y)
    • The line segment connecting (x-1, y-1) and (x, y-1)
    • The line segment connecting (x, y) and (x-1, y)
    • The line segment connecting (x, y) and (x, y-1)
  • Draw the selected three line segments on the coordinate plane.

However, the line segments you draw must not share any points (other than endpoints) with any line segments drawn previously.

Is it possible to draw all the length-1 line segments connecting grid points with 0 \le x \le H and 0 \le y \le W by repeating this operation? If possible, provide an example.

Constraints

  • All input values are integers.
  • 1 \le H, W \le 1000

Partial Score

10 points will be awarded for passing the testset satisfying the additional constraint H,W\le 5.

Input

The input is given from Standard Input in the following format:

H W

Output

If it is impossible to draw the grid by repeating the operation, output No.

If it is possible, output such an operation sequence in the following format:

Yes
S_1
\vdots
S_H

Here, S_1, \dots, S_H are strings of length W, and the j-th character of S_i (1 \le i \le H, 1 \le j \le W) is defined as follows:

  • If there is no operation with (x, y) = (i, j), the j-th character of S_i is ..
  • Otherwise, there is exactly one operation with (x, y) = (i, j). In that operation:
    • If the three selected line segments are those excluding "the line segment connecting (x-1, y-1) and (x-1, y)," then the j-th character of S_i is v.
    • If the three selected line segments are those excluding "the line segment connecting (x-1, y-1) and (x, y-1)," then the j-th character of S_i is >.
    • If the three selected line segments are those excluding "the line segment connecting (x, y) and (x-1, y)," then the j-th character of S_i is <.
    • If the three selected line segments are those excluding "the line segment connecting (x, y) and (x, y-1)," then the j-th character of S_i is ^.

Note that the judge is case-insensitive for Yes and No.

Refer to the sample inputs and the visualizer for further clarification.

Visualizer

You can use the visualizer via the following link:

https://img.atcoder.jp/ttpc2024_1/grid_construction_visualizer_9cdb863ae8b195d0a47d8d6e2c9e05cd.html

Sample Input 1

3 3

Sample Output 1

Yes
<<^
v.^
v>>

As shown in the figure, you can draw a 3 \times 3 grid by drawing U-shapes. Note that no U-shape is drawn at the location corresponding to the center cell. (For clarity, the U-shapes are colored, but this is irrelevant to the problem.)

Sample Input 2

4 4

Sample Output 2

No

Sample Input 3

4 5

Sample Output 3

No

配点 : 100 点

問題文

正整数 H,W が与えられます。あなたは座標平面にいくつかの「コの字」を用いて H 行 W 列のグリッドを描こうとしています。

1 つのコの字を描くには、次の操作を行います。

  • 1\le x\le H, 1\le y\le W なる整数 x,y を選ぶ。
  • 次の 4 本の線分のうち、異なる 3 本を選ぶ。
    • (x-1,y-1) と (x-1,y) を端点に持つ線分
    • (x-1,y-1) と (x,y-1) を端点に持つ線分
    • (x,y) と (x-1,y) を端点に持つ線分
    • (x,y) と (x,y-1) を端点に持つ線分
  • 選んだ 3 本の線分を座標平面に描く。

ただし、描いた線分は、それまでに描いた線分と端点以外で共有点を持ってはいけません。

0 \le x \le H, 0 \le y \le W の範囲にある格子点同士を結ぶ長さ 1 の線分すべてを、この操作を繰り返すことで描くことは可能でしょうか？可能である場合は一例を示してください。

制約

  • 入力はすべて整数
  • 1\le H,W\le 1000

部分点

追加の制約 H, W \le 5 を満たすデータセットに正解した場合は 10 点が与えられる。

入力

入力は以下の形式で与えられる。

H W

出力

操作を繰り返してグリッドを描くことが不可能である場合は、No を出力せよ。

操作を繰り返してグリッドを描くことが可能である場合は、そのような操作列を以下の形式で出力せよ。

Yes
S_1
\vdots
S_H

ここで、S_1, \dots, S_H はそれぞれ長さ W の文字列であり、S_i の j 文字目 (1 ≤ i ≤ H,\ 1 ≤ j ≤ W) は次のように定義される。

  • (x, y) = (i, j) であるような操作が存在しない場合、S_i の j 文字目は . である。
  • そうでない場合、(x, y) = (i, j) であるような操作はちょうど 1 回存在する。その操作において、
    • 「(x-1,y-1) と (x-1,y) を端点に持つ線分」以外 の 3 本を選んだ場合、S_i の j 文字目は v である。
    • 「(x-1,y-1) と (x,y-1) を端点に持つ線分」以外 の 3 本を選んだ場合、S_i の j 文字目は > である。
    • 「(x,y) と (x-1,y) を端点に持つ線分」以外 の 3 本を選んだ場合、S_i の j 文字目は < である。
    • 「(x,y) と (x,y-1) を端点に持つ線分」以外 の 3 本を選んだ場合、S_i の j 文字目は ^ である。

なお、ジャッジは Yes と No の大文字・小文字を区別しない。

入出力例やビジュアライザも参考にせよ。

ビジュアライザ

以下のリンクからビジュアライザを利用できます。

https://img.atcoder.jp/ttpc2024_1/grid_construction_visualizer_9cdb863ae8b195d0a47d8d6e2c9e05cd.html

入力例 1

3 3

出力例 1

Yes
<<^
v.^
v>>

図のようにコの字を描くことで、 3 \times 3 のグリッドを描くことができます。中央のマスに対応する場所にはコの字を描いていないことに注意してください。（見やすさのため、コの字に色をつけていますが、問題には関係ありません。）

入力例 2

4 4

出力例 2

No

入力例 3

4 5

出力例 3

No