409651: GYM103660 D Reflection
Description
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)$$$.
![](https://espresso.codeforces.com/5b671db78fa2ee2a7280a8fafa8b57faf5246648.png)
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.
InputThe 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.
OutputThe 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$$$.
ExampleInput7 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 DOutput
1 0 -1Note
The grid of the sample is as follows.
![](https://espresso.codeforces.com/eb63673695e10e83f8ad5ea12821112fa5a67eb2.png)