20031번 - Remote Control 다국어

Jaemin lives on an infinitely large rectangular grid. Recently, he moved to a new grid, so currently there is only one wall in the grid, which occupies one of the cells.

Each cell has a coordinate determined by the following: the wall is at the coordinate $(0,0)$. If a cell has coordinate $(x,y)$, then the cell immediately to the right is $(x+1,y)$, the cell immediately to the left is $(x-1,y)$, the cell immediately above is $(x,y+1)$, and the cell immediately below is $(x,y-1)$.

Today, he brought his favorite remote-controlled toy car to the grid. The car occupies exactly one cell in the grid. Unfortunately, as this grid is extremely large, he forgot where he put the car. In this case, the only way to move the car is to press a button on the remote control. Upon pressing it, the car will try to execute a predetermined path of $N$ moves, where each move involves the car trying to move to an adjacent cell in one of the four directions. Note that the car cannot go into the wall; if there is a wall at the cell the car is trying to move to, the car will ignore that command and not move, but will continue to try to execute the moves afterwards.

Since you decided to help him, he will ask you $Q$ questions of the form: "if my car starts at $(x,y)$, and I press the button once, where will it end up at?" Can you answer his questions?

On the first line, the length of the command $N$ is given, where $1 \leq N \leq 300\,000$.

On the next line, the car's predetermined path is given. It is a string of length $N$, and each character is either L, R, U, or D, meaning that the car moves left, right, up, or down, respectively. When he presses the button, the car follows each character of the command one by one as described above.

On the next line, the number of questions $Q$ is given, where $1 \leq Q \leq 300\,000$.

On each of the next $Q$ lines, two space-separated integers $x$ and $y$ are given. The starting point of the car is $(x,y)$. The input satisfies $-300\,000 \leq x, y \leq 300\,000$, and $(x,y) \neq (0,0)$.

For each question, output $x$ and $y$ on one line, separated by a space, where $(x,y)$ is the answer to the question.