{"raw_statement":[{"iden":"problem statement","content":"There is a grid with $H$ horizontal rows and $W$ vertical columns. $(i, j)$ denotes the square at the $i$\\-th row from the top and $j$\\-th column from the left.  \n$N$ squares, $(r_1, c_1), (r_2, c_2), \\ldots, (r_N, c_N)$, have walls.\nTakahashi is initially at square $(r_\\mathrm{s}, c_\\mathrm{s})$.\n$Q$ instructions are given to Takahashi. For $i = 1, 2, \\ldots, Q$, the $i$\\-th instruction is represented by a pair of a character $d_i$ and a positive integer $l_i$. $d_i$ is one of `L`, `R`, `U`, and `D`, representing the directions of left, right, up, and down, respectively.\nGiven the $i$\\-th direction, Takahashi repeats the following action $l_i$ times:\n\n> If a square without a wall is adjacent to the current square in the direction represented by $d_i$, move to that square; otherwise, do nothing.\n\nFor $i = 1, 2, \\ldots, Q$, print the square where Takahashi will be after he follows the first $i$ instructions."},{"iden":"constraints","content":"*   $2 \\leq H, W \\leq 10^9$\n*   $1 \\leq r_\\mathrm{s} \\leq H$\n*   $1 \\leq c_\\mathrm{s} \\leq W$\n*   $0 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq r_i \\leq H$\n*   $1 \\leq c_i \\leq W$\n*   $i \\neq j \\Rightarrow (r_i, c_i) \\neq (r_j, c_j)$\n*   $(r_\\mathrm{s}, c_\\mathrm{s}) \\neq (r_i, c_i)$ for all $i = 1, 2, \\ldots, N$.\n*   $1 \\leq Q \\leq 2 \\times 10^5$\n*   $d_i$ is one of the characters `L`, `R`, `U`, and `D`.\n*   $1 \\leq l_i \\leq 10^9$\n*   All values in the input other than $d_i$ are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$H$ $W$ $r_\\mathrm{s}$ $c_\\mathrm{s}$\n$N$\n$r_1$ $c_1$\n$r_2$ $c_2$\n$\\vdots$\n$r_N$ $c_N$\n$Q$\n$d_1$ $l_1$\n$d_2$ $l_2$\n$\\vdots$\n$d_Q$ $l_Q$"},{"iden":"sample input 1","content":"5 5 4 4\n3\n5 3\n2 2\n1 4\n4\nL 2\nU 3\nL 2\nR 4"},{"iden":"sample output 1","content":"4 2\n3 2\n3 1\n3 5\n\nThe given grid and the initial position of Takahashi are as follows, where `#` denotes a square with a wall, `T` a square where Takahashi is, and `.` the other squares:\n\n...#.\n.#...\n.....\n...T.\n..#..\n\nGiven the $1$\\-st instruction, Takahashi moves $2$ squares to the left, ending up in square $(4, 2)$ as follows:\n\n...#.\n.#...\n.....\n.T...\n..#..\n\nGiven the $2$\\-nd instruction, Takahashi first moves $1$ square upward, then he \"does nothing\" twice because the adjacent square in his direction has a wall. As a result, he ends up in square $(3, 2)$ as follows:\n\n...#.\n.#...\n.T...\n.....\n..#..\n\nGiven the $3$\\-rd instruction, Takahashi first moves $1$ square to the left, then he \"does nothing\" once because there is no square in his direction. As a result, he ends up in square $(3, 1)$ as follows:\n\n...#.\n.#...\nT....\n.....\n..#..\n\nGiven the $4$\\-th instruction, Takahashi moves $4$ squares to the right, ending up in square $(3, 5)$ as follows:\n\n...#.\n.#...\n....T\n.....\n..#.."},{"iden":"sample input 2","content":"6 6 6 3\n7\n3 1\n4 3\n2 6\n3 4\n5 5\n1 1\n3 2\n10\nD 3\nU 3\nL 2\nD 2\nU 3\nD 3\nU 3\nR 3\nL 3\nD 1"},{"iden":"sample output 2","content":"6 3\n5 3\n5 1\n6 1\n4 1\n6 1\n4 1\n4 2\n4 1\n5 1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}