There are $$$n$$$ mirrors on the grid numbered with integers from $$$1$$$ to $$$n$$$. Mirrors have two types, 'A' and 'B', the two shapes are shown below. Both sides of the mirror can reflect rays. We define the bottom left corner as $$$(1,1)$$$.
You need to answer $$$q$$$ queries. The $$$i$$$-th query has two integers $$$x_i,y_i$$$ and one letter $$$c_i\in\{$$$'L','U','R','D'$$$\}$$$, denotes a ray with $$$(x_i, y_i)$$$ as the starting point and $$$c_i$$$ as the direction. 'L','U','R','D' denotes $$$Left, Up, Right, Down$$$ respectively. Changes of the coordinate corresponding to the direction are as follows:
- $$$Left$$$:$$$(x,y)\rightarrow(x-1,y)$$$
- $$$Up$$$:$$$(x,y)\rightarrow(x,y+1)$$$
- $$$Right$$$:$$$(x,y)\rightarrow(x+1,y)$$$
- $$$Down$$$:$$$(x,y)\rightarrow(x,y-1)$$$
For each query, find the last mirror reached by the ray.
You can refer to the note for a better understanding of the problem.
The first line contains two integers $$$n,q\ (1\le n,q\le 10^5)$$$ — the number of mirrors and queries.
Then $$$n$$$ lines follow, each line contains $$$2$$$ integers $$$X_i,Y_i$$$ and $$$1$$$ character $$$T_i$$$ — the coordinates and type of the $$$i$$$-th mirror. $$$1\le X_i, Y_i\le 10^5$$$, $$$T_i\in \{$$$'A','B'$$$\}$$$.
Then $$$q$$$ lines follow, each line contains $$$2$$$ integers $$$x_i,y_i$$$ and $$$1$$$ character $$$c_i$$$ — the starting point and direction of the ray in the $$$i$$$-th query. $$$1\le x_i,y_i\le 10^5$$$, $$$c_i\in\{$$$'L','U','R','D'$$$\}$$$.
It is guaranteed that no two mirrors are in the same position and that for each query there are no mirrors at the starting point of the ray.
The output contains $$$q$$$ lines, each line contains an integer — the last mirror reached by the ray. If the ray will reflect infinitely, print $$$-1$$$. If the ray doesn't reach any mirror, print $$$0$$$.
7 3 1 3 B 7 8 B 9 10 B 7 3 A 3 8 A 9 8 A 7 10 A 3 2 U 6 1 R 9 9 D
1 0 -1
The grid of the sample is as follows.
