CF1023E.Down or Right

This is an interactive problem.

Bob lives in a square grid of size $n \times n$, with rows numbered $1$ through $n$ from top to bottom, and columns numbered $1$ through $n$ from left to right. Every cell is either allowed or blocked, but you don't know the exact description of the grid. You are given only an integer $n$.

Bob can move through allowed cells but only in some limited directions. When Bob is in an allowed cell in the grid, he can move down or right to an adjacent cell, if it is allowed.

You can ask at most $4 \cdot n$ queries of form "? $r_1$ $c_1$ $r_2$ $c_2$" ($1 \le r_1 \le r_2 \le n$, $1 \le c_1 \le c_2 \le n$). The answer will be "YES" if Bob can get from a cell $(r_1, c_1)$ to a cell $(r_2, c_2)$, and "NO" otherwise. In particular, if one of the two cells (or both) is a blocked cell then the answer is "NO" for sure. Since Bob doesn't like short trips, you can only ask queries with the manhattan distance between the two cells at least $n - 1$, i.e. the following condition must be satisfied: $(r_2 - r_1) + (c_2 - c_1) \ge n - 1$.

It's guaranteed that Bob can get from the top-left corner $(1, 1)$ to the bottom-right corner $(n, n)$ and your task is to find a way to do it. You should print the answer in form "! S" where $S$ is a string of length $2 \cdot n - 2$ consisting of characters 'D' and 'R', denoting moves down and right respectively. The down move increases the first coordinate by $1$, the right move increases the second coordinate by $1$. If there are multiple solutions, any of them will be accepted. You should terminate immediately after printing the solution.

这是一个交互式问题。

鲍勃生活在一个 $n \times n$ 的正方形网格中，行号从上到下依次为 $1$ 到 $n$，列号从左到右依次为 $1$ 到 $n$。每个格子要么是允许通行的，要么是被封锁的，但你并不知道该网格的具体结构。你仅被给定一个整数 $n$。

鲍勃只能在允许通行的格子中移动，且移动方向受限：当鲍勃位于某个允许通行的格子时，他仅能向下或向右移动至相邻格子（前提是目标格子也允许通行）。

你最多可提出 $4 \cdot n$ 个形如 “? $r_1$ $c_1$ $r_2$ $c_2$” 的查询（其中 $1 \le r_1 \le r_2 \le n$，$1 \le c_1 \le c_2 \le n$）。系统将返回 “YES”，当且仅当鲍勃能从格子 $(r_1, c_1)$ 到达格子 $(r_2, c_2)$；否则返回 “NO”。特别地，若两个格子中至少有一个被封锁，则答案必定为 “NO”。由于鲍勃不喜欢短途旅行，你提出的每个查询必须满足两格子间的曼哈顿距离至少为 $n - 1$，即需满足如下条件：$(r_2 - r_1) + (c_2 - c_1) \ge n - 1$。

题目保证鲍勃可以从左上角 $(1, 1)$ 到达右下角 $(n, n)$，你的任务是找出这样一条路径。你需要以 “! S” 的形式输出答案，其中 $S$ 是一个长度为 $2 \cdot n - 2$ 的字符串，仅由字符 'D'（表示向下移动）和 'R'（表示向右移动）组成。向下移动使第一坐标加 $1$，向右移动使第二坐标加 $1$。若存在多条可行路径，输出任意一条即可。在输出答案后，你必须立即终止程序。

The only line of the input contains an integer $n$ ($2 \le n \le 500$) — the size of the grid.

输入仅包含一行，其中有一个整数 $n$（$2 \le n \le 500$）——表示网格的大小。

When you are ready to print the answer, print a single line containing "! S" where where $S$ is a string of length $2 \cdot n - 2$ consisting of characters 'D' and 'R', denoting moves down and right respectively. The path should be a valid path going from the cell $(1, 1)$ to the cell $(n, n)$ passing only through allowed cells.

当您准备输出答案时，请输出一行，格式为 ! S，其中 $S$ 是一个长度为 $2 \cdot n - 2$ 的字符串，仅由字符 'D' 和 'R' 组成，分别表示向下和向右的移动。该路径应是从单元格 $(1, 1)$ 到单元格 $(n, n)$ 的一条合法路径，且只能经过允许的单元格。

The first example is shown on the picture below.

To hack, use the following input format:

The first line should contain a single integer $n$ ($2 \le n \le 500$) — the size of the grid.

Each of the next $n$ lines should contain a string of $n$ characters '#' or '.', where '#' denotes a blocked cell, and '.' denotes an allowed cell.

For example, the following text encodes the example shown above:

4
..#.
#...
###.
....

第一个示例见下图所示。

要进行 hack，请使用以下输入格式：

第一行应包含一个整数 $n$（$2 \le n \le 500$）——表示网格的大小。

接下来的 $n$ 行，每行包含一个长度为 $n$ 的字符串，由字符 # 或 . 组成，其中 # 表示被封锁的格子，. 表示允许通行的格子。

例如，以下文本编码了上图所示的示例：

4
..#.
#...
###.
....