Problem Statement

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 squares, (r_1, c_1), (r_2, c_2), \ldots, (r_N, c_N),$ have walls.
Takahashi is initially at square $(r_\mathrm{s}, c_\mathrm{s})$.
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.
Given the i-th direction, Takahashi repeats the following action l_i times:

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.

For $i = 1, 2, \ldots, Q$, print the square where Takahashi will be after he follows the first i instructions.

Input

The input is given from Standard Input in the following format:
$H W r_\mathrm{s} c_\mathrm{s}$
N
r_1 c_1
r_2 c_2
$\vdots$
r_N c_N
Q
d_1 l_1
d_2 l_2
$\vdots$
d_Q l_Q

Output

Print Q lines.
For $i = 1, 2, \ldots, Q$, the i-th line should contain the square (R_i, C_i) where Takahashi will be after he follows the first i instructions, in the following format:
R_1 C_1
R_2 C_2
$\vdots$
R_Q C_Q

Constraints

• $2 \leq H, W \leq 10^9$
• $1 \leq r_\mathrm{s} \leq H$
• $1 \leq c_\mathrm{s} \leq W$
• $0 \leq N \leq 2 \times 10^5$
• $1 \leq r_i \leq H$
• $1 \leq c_i \leq W$
• $i \neq j \Rightarrow (r_i, c_i) \neq (r_j, c_j)$
• $(r_\mathrm{s}, c_\mathrm{s}) \neq (r_i, c_i)$ for all $i = 1, 2, \ldots, N$.
• $1 \leq Q \leq 2 \times 10^5$
• d_i is one of the characters L, R, U, and D.
• $1 \leq l_i \leq 10^9$
• All values in the input other than d_i are integers.

Sample Input 1

5 5 4 4
3
5 3
2 2
1 4
4
L 2
U 3
L 2
R 4

Sample Output 1

4 2
3 2
3 1
3 5

The 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:
...#.
.#...
.....
...T.
..#..

Given the 1-st instruction, Takahashi moves 2 squares to the left, ending up in square (4, 2) as follows:
...#.
.#...
.....
.T...
..#..

Given 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:
...#.
.#...
.T...
.....
..#..

Given 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:
...#.
.#...
T....
.....
..#..

Given the 4-th instruction, Takahashi moves 4 squares to the right, ending up in square (3, 5) as follows:
...#.
.#...
....T
.....
..#..

Sample Input 2

6 6 6 3
7
3 1
4 3
2 6
3 4
5 5
1 1
3 2
10
D 3
U 3
L 2
D 2
U 3
D 3
U 3
R 3
L 3
D 1

Sample Output 2

6 3
5 3
5 1
6 1
4 1
6 1
4 1
4 2
4 1
5 1

见题面 Input 部分

见题面 Output 部分