CF329D.The Evil Temple and the Moving Rocks

Important: All possible tests are in the pretest, so you shouldn't hack on this problem. So, if you passed pretests, you will also pass the system test.

You are an adventurer currently journeying inside an evil temple. After defeating a couple of weak monsters, you arrived at a square room consisting of tiles forming an n × n grid, surrounded entirely by walls. At the end of the room lies a door locked with evil magical forces. The following inscriptions are written on the door:

The sound of clashing rocks will awaken the door!

Being a very senior adventurer, you immediately realize what this means. In the room next door lies an infinite number of magical rocks. There are four types of rocks:

• '^': this rock moves upwards;
• '<': this rock moves leftwards;
• '>': this rock moves rightwards;
• 'v': this rock moves downwards.

To open the door, you first need to place the rocks on some of the tiles (one tile can be occupied by at most one rock). Then, you select a single rock that you have placed and activate it. The activated rock will then move in its direction until it hits another rock or hits the walls of the room (the rock will not move if something already blocks it in its chosen direction). The rock then deactivates. If it hits the walls, or if there have been already 107 events of rock becoming activated, the movements end. Otherwise, the rock that was hit becomes activated and this procedure is repeated.

If a rock moves at least one cell before hitting either the wall or another rock, the hit produces a sound. The door will open once the number of produced sounds is at least x. It is okay for the rocks to continue moving after producing x sounds.

The following picture illustrates the four possible scenarios of moving rocks.

• Moves at least one cell, then hits another rock. A sound is produced, the hit rock becomes activated.

  

• Moves at least one cell, then hits the wall (i.e., the side of the room). A sound is produced, the movements end.

  

• Does not move because a rock is already standing in the path. The blocking rock becomes activated, but no sounds are produced.

  

• Does not move because the wall is in the way. No sounds are produced and the movements end.

  

Assume there's an infinite number of rocks of each type in the neighboring room. You know what to do: place the rocks and open the door!

重要提示：所有可能的测试用例均已包含在预测试中，因此本题不允许进行 Hack。也就是说，若你通过了预测试，则系统测试也必然通过。

你是一名正在邪恶神庙中冒险的探险者。在击败了几只弱小的怪物后，你抵达了一间正方形的房间，该房间由 $ n \times n $ 的方格瓷砖构成，四周完全被墙壁包围。房间尽头有一扇门，被邪恶的魔法力量锁住。门上刻有如下铭文：

碎石相击之声，将唤醒此门！

作为一名经验极其丰富的探险者，你立刻明白了其含义。隔壁房间中存有无限数量的魔法石块。石块共分四种类型：

• '^'：该石块向上移动；
• '<'：该石块向左移动；
• '>'：该石块向右移动；
• 'v'：该石块向下移动。

为打开这扇门，你首先需将若干石块放置于部分方格上（每个方格至多放置一块石块）。随后，你从中选择恰好一块已放置的石块并将其激活。被激活的石块将沿其对应方向持续移动，直至撞上另一块石块或撞上房间墙壁（若其初始移动方向上已有障碍物，则该石块不发生任何移动）。此后，该石块即进入非激活状态。若其撞上墙壁，或自开始以来已累计发生 $10^7$ 次石块被激活的事件，则整个运动过程终止。否则，被撞击的石块将被激活，上述过程重复进行。

若某石块在撞上墙壁或另一石块之前至少移动了一个方格，则此次撞击将产生一声“响声”。当产生的响声总数不少于 $x$ 时，门即开启。注意：即使响声数已达 $x$，石块仍可继续运动。

下图展示了石块运动的四种可能情形：

• 移动至少一个方格后，撞上另一石块。此时产生一声响声，被撞石块被激活。

  

• 移动至少一个方格后，撞上墙壁（即房间边缘）。此时产生一声响声，运动过程终止。

  

• 因路径上已有石块阻挡而无法移动。此时阻挡石块被激活，但不产生响声。

  

• 因墙壁阻挡而无法移动。此时不产生响声，运动过程终止。

  

假设隔壁房间中每种类型的石块均有无限供应。你已知晓该怎么做：布置石块，开启大门！

The first line will consists of two integers n and x, denoting the size of the room and the number of sounds required to open the door. There will be exactly three test cases for this problem:

• n = 5, x = 5;
• n = 3, x = 2;
• n = 100, x = 105.

All of these testcases are in pretest.

第一行包含两个整数 $n$ 和 $x$，分别表示房间的大小以及打开门所需的音效数量。本题恰好包含三个测试用例：

• $n = 5,\ x = 5$；
• $n = 3,\ x = 2$；
• $n = 100,\ x = 105$。

以上所有测试用例均包含在预测试中。

Output n lines. Each line consists of n characters — the j-th character of the i-th line represents the content of the tile at the i-th row and the j-th column, and should be one of these:

• '^', '<', '>', or 'v': a rock as described in the problem statement.
• '.': an empty tile.

Then, output two integers r and c (1 ≤ r, c ≤ n) on the next line — this means that the rock you activate first is located at the r-th row from above and c-th column from the left. There must be a rock in this cell.

If there are multiple solutions, you may output any of them.

输出 n 行。每行包含 n 个字符——第 i 行的第 j 个字符表示第 i 行第 j 列方格的内容，且必须为以下字符之一：

• '^'、'<'、'>' 或 'v'：如题目描述所示的岩石；
• '.'：空方格。

随后，在下一行输出两个整数 r 和 c（1 ≤ r, c ≤ n）——这表示你首先激活的岩石位于从上往下数第 r 行、从左往右数第 c 列。该位置上必须存在一块岩石。

若存在多种解法，可输出任意一种。

Here's a simulation of the first example, accompanied with the number of sounds produced so far.

0 sound

1 sound

2 sounds

3 sounds

4 sounds

still 4 sounds

In the picture above, the activated rock switches between the '^' rock and the '<' rock. However, no sound is produced since the '^' rock didn't move even a single tile. So, still 4 sound.

5 sounds

At this point, 5 sound are already produced, so this solution is already correct. However, for the sake of example, we will continue simulating what happens.

6 sounds

7 sounds

still 7 sounds

8 sounds

And the movement stops. In total, it produces 8 sounds. Notice that the last move produced sound.

Here's a simulation of the second example:

0 sound

1 sound

2 sounds

Now, the activated stone will switch continuously from one to another without producing a sound until it reaches the 107 limit, after which the movement will cease.

In total, it produced exactly 2 sounds, so the solution is correct.

以下是第一个示例的模拟过程，同时标出截至目前已产生的声音数量。

0 声音

1 声音

2 声音

3 声音

4 声音

仍为 4 声音

在上图中，被激活的岩石在 '^' 岩石与 '<' 岩石之间反复切换。但由于 '^' 岩石未发生任何格子的移动，因此未产生声音，故仍为 4 声音。

5 声音

此时，已产生 5 声音，因此该解法已正确。但为便于说明，我们将继续模拟后续过程。

6 声音

7 声音

仍为 7 声音

8 声音

随后运动停止。总共产生了 8 声音。注意：最后一次移动产生了声音。

以下是第二个示例的模拟过程：

0 声音

1 声音

2 声音

此时，被激活的石块将在两者之间持续切换，且不再产生声音，直至达到上限 107 次后，运动终止。

总计恰好产生 2 声音，因此该解法正确。