Студенческий совет Берляндского государственного университета собирается устроить Чемпионат по Пятнашкам. Эту идею активно поддержало руководство университета, ведь ректор — большой фанат Пятнашек (он даже хочет все головоломки для Чемпионата подготовить самостоятельно). А ещё он — большой фанат программирования, со всеми вытекающими отсюда последствиями.
Ректор хочет, чтобы организаторы устроили соревнования не просто между участниками, а между программами, написанными участниками. Победителем станет участник, программа которого сможет решить наибольшее количество головоломок, предложенных ректором. А вот приз, который получит победитель, должен зависеть от того, насколько его результат отличается от результата эталонного искусственного интеллекта, написанного организаторами. Если количество головоломок, решённых победителем, больше или равно количеству головоломок, решённых эталонным ИИ, то победитель получает 1 миллион рублей. Если же нет, то победитель получает 100 тысяч рублей.
У ректора совершенно чёткие представления о скорости, с которой должна работать программа организаторов, — решение одной головоломки не должно занимать больше 2 секунд. Ректор просит вас помочь организаторам и написать такой эталонный искусственный интеллект, который пройдёт все имеющиеся головоломки и уложится в указанный лимит времени.
Первая строка содержит целое число N (2 ≤ N ≤ 4) — размер игрового поля Пятнашек.
Следующие N строк описывают игровое поле. Каждая из них содержит N целых чисел Aij (0 ≤ Aij ≤ N2 - 1). Все числа Aij различны, число 0 означает пустую ячейку игрового поля.
Выведите строку, состоящую из заглавных латинских букв 'L', 'R', 'U', 'D', — решение головоломки. Каждый символ строки должен означать направление изменения положения пустой ячейки на игровом поле: 'L' — влево, 'R' — вправо, 'U' — вверх, 'D' — вниз. Гарантируется, что решение головоломки существует, и количество ходов в нем не превышает 100. Если подходящих решений несколько, выведите любое из них.
## Входные Данные
Первая строка содержит целое число N (2 ≤ N ≤ 4) — размер игрового поля Пятнашек.Следующие N строк описывают игровое поле. Каждая из них содержит N целых чисел Aij (0 ≤ Aij ≤ N2 - 1). Все числа Aij различны, число 0 означает пустую ячейку игрового поля.
## Выходные Данные
Выведите строку, состоящую из заглавных латинских букв 'L', 'R', 'U', 'D', — решение головоломки. Каждый символ строки должен означать направление изменения положения пустой ячейки на игровом поле: 'L' — влево, 'R' — вправо, 'U' — вверх, 'D' — вниз. Гарантируется, что решение головоломки существует, и количество ходов в нем не превышает 100. Если подходящих решений несколько, выведите любое из них.
## Примеры
Входные данные21 20 3Выходные данныеRULRDВходные данные30 1 35 2 64 7 8Выходные данныеRDLDRR
[samples]
**Definitions**
Let $ N, M \in \mathbb{Z}^+ $ with $ 1 \leq N, M \leq 100 $.
For each selector $ i \in \{1, \dots, N\} $:
- Let $ \mathbf{X}_i \in \mathbb{Z}^N $ be the direction vector.
- Let $ K_{i,j} \in \mathbb{Z} $ be the transmission coefficient for gear $ j \in \{1, \dots, M\} $, with $ K_{i,1} < K_{i,2} < \dots < K_{i,M} $ and $ \exists j $ such that $ K_{i,j} = 0 $.
The total speed vector for selector settings $ \mathbf{g} = (g_1, \dots, g_N) $ is:
$$
\mathbf{S}(\mathbf{g}) = \sum_{i=1}^N K_{i,g_i} \cdot \mathbf{X}_i
$$
**Constraints**
1. $ |K_{i,j}| \leq 1000 $, $ \|\mathbf{X}_i\|_\infty \leq 1000 $ for all $ i,j $.
2. The set $ \{\mathbf{X}_1, \dots, \mathbf{X}_N\} $ spans $ \mathbb{R}^N $ (i.e., any target speed vector is achievable via real coefficients).
3. For each $ i $, exactly one $ K_{i,j} = 0 $.
**Objective**
Find $ \mathbf{g}^* = (g_1^*, \dots, g_N^*) \in \{1, \dots, M\}^N $ such that:
$$
\mathbf{S}(\mathbf{g}^*) = \mathbf{0}
$$
**Interaction**
- You may make at most 120 queries.
- Each query: output `? g_1 g_2 ... g_N`, receive $ \mathbf{S} = (s_1, \dots, s_N) $.
- If any component of the response is $ 987654321 $, terminate immediately.
- When solved: output `A g_1^* g_2^* ... g_N^*` and terminate.