A9127 | Escaping on Beaveractor

The first line contains two integers: the number of traffic rules $n$ and the size of the campus $b$ , $0<=n$ , $1<=b$ . Next $n$ lines contain the rules. Each line of the rules contains four space-separated integers $x_{0}$ , $y_{0}$ , $x_{1}$ , $y_{1}$ — the beginning and the end of the arrow. It is guaranteed that all arrows are parallel to the coordinate axes and have no common points. All arrows are located inside the campus, that is, $0<=x_{0},y_{0},x_{1},y_{1}<=b$ holds.

Next line contains integer $q$ — the number of plans the scientists have, $1<=q<=10^{5}$ . The $i$ -th plan is represented by two integers, $x_{i}$ , $y_{i}$ are the Beaveractor's coordinates at the initial time, $0<=x_{i},y_{i}<=b$ , character $w_{i}$ , that takes value U, D, L, R and sets the initial direction up, down, to the left or to the right correspondingly (the Y axis is directed upwards), and $t_{i}$ — the time passed after the escape started, $0<=t_{i}<=10^{15}$ .

- to get 30 points you need to solve the problem with constraints $n,b<=30$ (subproblem D1);
- to get 60 points you need to solve the problem with constraints $n,b<=1000$ (subproblems D1+D2);
- to get 100 points you need to solve the problem with constraints $n,b<=10^{5}$ (subproblems D1+D2+D3).

Print $q$ lines. Each line should contain two integers — the Beaveractor's coordinates at the final moment of time for each plan. If the Smart Beaver manages to leave the campus in time $t_{i}$ , print the coordinates of the last point in the campus he visited.

无