Є сітка з \(H\) горизонтальних рядків і \(W\) вертикальних стовпців. (\(i, j\)) позначає квадрат у \(i\)-му рядку зверху та \(j\)-му стовпчику зліва.

\(N\) квадратів, \((r_1, c_1), (r_2, c_2), \ldots, (r_N, c_N)\), мають стіни.

Степан спочатку знаходиться в квадраті (\(r_\mathrm{s}, c_\mathrm{s}\)).

Степаг має \(Q\) інструкцій. Для \(i = 1, 2, \ldots, Q\) \(i\)-та інструкція представлена ​​парою символів \(d_i\) і натуральне число \(l_i\). \(d_i\) є одним із L, R, U та D, які представляють напрямки вліво, вправо, вгору та вниз відповідно.

Враховуючи \(i\)-й напрямок, Степан повторює наступну дію \(l_i\) разів:

• Якщо квадрат без стіни є суміжним з поточним квадратом у напрямку, представленому \(d_i\), перейдіть до цього квадрата; інакше нічого не робіть.

Для \(i = 1, 2, \ldots, Q\), виведіть квадрат, де буде Степан після того, як він виконає перші \(i\) інструкції.

Обмеження

• \(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\) то \((r_i, c_i) \neq (r_j, c_j)\)
• \(1 \leq Q \leq 2 \times 10^5\)
• \(d_i\) є одним із символів L, R, U та D.
• \(1 \leq l_i \leq 10^9\)
• Усі значення у вхідних даних, крім \(d_i\) є цілими числами.

Формат вхідних даних

Перший рядок містить цілі числа \(H,W,r_s,c_s\)

Наступний  рядок містить \(N\)

Наступні  \(N\) рядків містять цілі числа \(r_i,c_i\)

Далі рядок містить \(Q\)

Наступні  \(Q\) рядків містять \(d_i,l_i\)

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть \(Q\) рядків. Для \(i = 1, 2, \ldots, Q\) \(i\)-й рядок має містити квадрат (\(R_i, C_i\)), де буде Степан після виконання перших \(i\) інструкцій

Приклад вхідних даних

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

Приклад вихідних даних

4 2
3 2
3 1
3 5

Приклад вхідних даних

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

Приклад вихідних даних

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