409651: GYM103660 D Reflection

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.