{"raw_statement":[{"iden":"statement","content":"**This is an interactive problem.**\n\nVladik has favorite game, in which he plays all his free time.\n\nGame field could be represented as _n_ × _m_ matrix which consists of cells of three types:\n\n*   «_._» — normal cell, player can visit it.\n*   «_F_» — finish cell, player has to finish his way there to win. There is exactly one cell of this type.\n*   «_*_» — dangerous cell, if player comes to this cell, he loses.\n\nInitially player is located in the left top cell with coordinates (1, 1).\n\nPlayer has access to 4 buttons \"_U_\", \"_D_\", \"_L_\", \"_R_\", each of them move player up, down, left and right directions respectively.\n\nBut it’s not that easy! Sometimes friends play game and change functions of buttons. Function of buttons \"_L_\" and \"_R_\" could have been swapped, also functions of buttons \"_U_\" and \"_D_\" could have been swapped. Note that functions of buttons can be changed only at the beginning of the game.\n\nHelp Vladik win the game!"},{"iden":"input","content":"First line contains two space-separated integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 100) — number of rows and columns respectively.\n\nEach of next _n_ lines contains _m_ characters describing corresponding row of field. Set of characters in field is described above.\n\nGuaranteed that cell with coordinates (1, 1) is normal and there is at least one way from initial cell to finish cell without dangerous cells."},{"iden":"interaction","content":"You can press buttons no more than 2·_n_·_m_ times.\n\nTo press a button you should print \"_U_\", \"_D_\", \"_L_\", \"_R_\" in new line. It’s necessary to print newline character and _flush_ output. After flushing buffer you should read answer from input data. Answer is the pair of space-separated integers _x_, _y_ — new position of player. In case, if there is no cell in direction of moving, position will not change. If after any move player lost, in other words player move to dangerous cell, then _x_ and _y_ will be equal to  - 1.\n\nIf after any move player is in finish or dangerous cell, then you should terminate your program.\n\nTo finish output buffer (i. e. for operation _flush_) right after printing direction and newline you should do next:\n\n*   _fflush(stdout)_ in C++\n*   _System.out.flush()_ in Java\n*   _stdout.flush()_ in Python\n*   _flush(output)_ in Pascal\n*   read documentation for other languages.\n\n**Hacks**\n\nTo perform a hack you should use this format:\n\nn m swapLR swapUD  \na_1  \na_2  \n...  \na_n\n\nWhere _n_, _m_ — number of rows and columns in game field. _swapLR_ is equal to 1 in case, when directions \"_L_’’ and \"_R_’’ is swapped, and equal to 0 otherwise. _swapUD_ is equal to 1, when directions \"_U_’’ and \"_D_’’ is swapped, and equal to 0 otherwise. _a_1, _a_2, ..., _a__n_ — description of corresponding rows of game field."},{"iden":"example","content":"Input\n\n4 3\n...\n**.\nF*.\n...\n1 1\n1 2\n1 3\n1 3\n2 3\n3 3\n4 3\n4 2\n4 1\n3 1\n\nOutput\n\nR\nL\nL\nD\nU\nU\nU\nR\nR\nD"},{"iden":"note","content":"In first test case all four directions swapped with their opposite directions. Protocol of interaction In more convenient form:\n\n![image](https://espresso.codeforces.com/72a61d8c41d19408adcbd41364091b2b1d7af2f1.png)\n\nThis test could be presenter for hack in following way:\n\n4 3 1 1\n...\n**.\nF*.\n..."}],"translated_statement":[{"iden":"statement","content":"*这是一个交互式问题。*\n\nVladik 有一个他空闲时经常玩的游戏。\n\n游戏场地可以表示为一个 #cf_span[n × m] 的矩阵，包含三种类型的格子：\n\n初始时，玩家位于左上角坐标为 #cf_span[(1, 1)] 的格子。\n\n玩家可以使用 #cf_span[4] 个按钮：“_U_”、“_D_”、“_L_”、“_R_”，分别代表向上、向下、向左、向右移动。\n\n但事情没那么简单！有时朋友会改变按钮的功能。按钮 “_L_” 和 “_R_” 的功能可能被交换，按钮 “_U_” 和 “_D_” 的功能也可能被交换。注意，按钮功能只能在游戏开始时改变。\n\n帮助 Vladik 赢得游戏！\n\n第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 100]），分别表示行数和列数。\n\n接下来的 #cf_span[n] 行每行包含 #cf_span[m] 个字符，描述对应行的场地。场地中的字符集合如上所述。\n\n保证坐标为 #cf_span[(1, 1)] 的格子是正常的，并且存在一条从初始格子到终点格子、不经过危险格子的路径。\n\n你可以按按钮的次数不超过 #cf_span[2·n·m] 次。\n\n要按一个按钮，你需要在新的一行打印 “_U_”、“_D_”、“_L_” 或 “_R_”。必须打印换行符并 _刷新_ 输出。刷新缓冲区后，你需要从输入读取答案。答案是一对用空格分隔的整数 #cf_span[x], #cf_span[y]，表示玩家的新位置。如果移动方向上没有格子，位置不会改变。如果在任何移动后玩家失败，即玩家移动到了危险格子，则 #cf_span[x] 和 #cf_span[y] 将等于 #cf_span[ - 1]。\n\n如果在任何移动后玩家位于终点或危险格子，你应该终止程序。\n\n在打印方向和换行符后，为了正确刷新输出缓冲区（即执行 _flush_ 操作），你应该执行以下操作：\n\n*黑客（Hacks）*\n\n要进行黑客攻击，应使用以下格式：\n\n其中 #cf_span[n], #cf_span[m] 是游戏场地的行数和列数。#cf_span[swapLR] 在 “_L_” 和 “_R_” 方向被交换时等于 #cf_span[1]，否则等于 #cf_span[0]。#cf_span[swapUD] 在 “_U_” 和 “_D_” 方向被交换时等于 #cf_span[1]，否则等于 #cf_span[0]。#cf_span[a1, a2, ..., an] 是游戏场地对应行的描述。\n\n在第一个测试用例中，所有四个方向都与其相反方向交换。交互协议以更直观的形式表示如下：\n\n\n\n该测试用例可作为以下形式的黑客示例：\n\n"},{"iden":"input","content":"第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 100]），分别表示行数和列数。接下来的 #cf_span[n] 行每行包含 #cf_span[m] 个字符，描述对应行的场地。场地中的字符集合如上所述。保证坐标为 #cf_span[(1, 1)] 的格子是正常的，并且存在一条从初始格子到终点格子、不经过危险格子的路径。"},{"iden":"interaction","content":"你可以按按钮的次数不超过 #cf_span[2·n·m] 次。要按一个按钮，你需要在新的一行打印 “_U_”、“_D_”、“_L_” 或 “_R_”。必须打印换行符并 _刷新_ 输出。刷新缓冲区后，你需要从输入读取答案。答案是一对用空格分隔的整数 #cf_span[x], #cf_span[y]，表示玩家的新位置。如果移动方向上没有格子，位置不会改变。如果在任何移动后玩家失败，即玩家移动到了危险格子，则 #cf_span[x] 和 #cf_span[y] 将等于 #cf_span[ - 1]。如果在任何移动后玩家位于终点或危险格子，你应该终止程序。在打印方向和换行符后，为了正确刷新输出缓冲区（即执行 _flush_ 操作），你应该执行以下操作：\n\n* C++: _fflush(stdout)_\n* Java: _System.out.flush()_\n* Python: _stdout.flush()_\n* Pascal: _flush(output)_\n* 其他语言请查阅相关文档。\n\n*黑客（Hacks）*\n\n要进行黑客攻击，应使用以下格式：\n\nn m swapLR swapUD\na_1\na_2\n...\na_n\n\n其中 #cf_span[n], #cf_span[m] 是游戏场地的行数和列数。#cf_span[swapLR] 在 “_L_” 和 “_R_” 方向被交换时等于 #cf_span[1]，否则等于 #cf_span[0]。#cf_span[swapUD] 在 “_U_” 和 “_D_” 方向被交换时等于 #cf_span[1]，否则等于 #cf_span[0]。#cf_span[a1, a2, ..., an] 是游戏场地对应行的描述。"},{"iden":"note","content":"在第一个测试用例中，所有四个方向都与其相反方向交换。交互协议以更直观的形式表示如下：该测试用例可作为以下形式的黑客示例： 4 3 1 1...**.F*.... "}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions:**\n\n- Let $ G = (V, E) $ be a grid graph of size $ n \\times m $, where each cell $ (i, j) \\in [1, n] \\times [1, m] $ is a vertex.\n- Each cell is labeled as one of:\n  - `'.'` — normal (safe) cell,\n  - `'F'` — finish cell,\n  - `'#'` — dangerous cell.\n- Initial position: $ (1, 1) $, guaranteed to be `'.'`.\n- Target: reach any cell labeled `'F'`.\n\n**Constraints:**\n\n- The player can issue moves: $ \\text{U}, \\text{D}, \\text{L}, \\text{R} $.\n- Two binary swap flags are fixed at the start of the game (unknown to the player):\n  - $ s_{LR} \\in \\{0, 1\\} $: if $ s_{LR} = 1 $, then $ \\text{L} \\leftrightarrow \\text{R} $ are swapped.\n  - $ s_{UD} \\in \\{0, 1\\} $: if $ s_{UD} = 1 $, then $ \\text{U} \\leftrightarrow \\text{D} $ are swapped.\n- The effective move mapping is:\n  - If $ s_{LR} = 0 $: $ \\text{L} \\to (-1, 0), \\text{R} \\to (1, 0) $; else: $ \\text{L} \\to (1, 0), \\text{R} \\to (-1, 0) $.\n  - If $ s_{UD} = 0 $: $ \\text{U} \\to (0, -1), \\text{D} \\to (0, 1) $; else: $ \\text{U} \\to (0, 1), \\text{D} \\to (0, -1) $.\n- Moves that would take the player outside the grid are ignored (position unchanged).\n- If a move leads to a cell labeled `'#'`, the response is $ (-1, -1) $, and the program must terminate (loss).\n- If a move leads to a cell labeled `'F'`, the program must terminate (win).\n- Maximum number of moves: $ 2 \\cdot n \\cdot m $.\n\n**Objective:**\n\nFind a sequence of moves $ M = (m_1, m_2, \\dots, m_k) $, $ k \\leq 2nm $, such that starting from $ (1,1) $, applying the (unknown) swapped move semantics leads to a cell labeled `'F'`, without ever stepping on a `'#'`.\n\n**Interaction Protocol:**\n\n- For each move $ m_i \\in \\{\\text{U}, \\text{D}, \\text{L}, \\text{R}\\} $:\n  - Print $ m_i $ followed by a newline.\n  - Flush output.\n  - Read response $ (x, y) $:\n    - If $ (x, y) = (-1, -1) $: terminate (dangerous cell).\n    - If $ (x, y) $ is the coordinates of a cell labeled `'F' $: terminate (win).\n    - Otherwise: update current position to $ (x, y) $.\n\n**Note:** The swap flags $ s_{LR}, s_{UD} $ are unknown and fixed. The solution must work for any combination of $ (s_{LR}, s_{UD}) \\in \\{0,1\\}^2 $.","simple_statement":null,"has_page_source":false}