P12704 Retribution


You are given an $n \times m$ chessboard. Each grid point is labeled with a character $c_{i,j}\in\{\texttt{U},\texttt{D},\texttt{L},\texttt{R}\}$, representing up, down, left, and right. From a grid point, you may move to an adjacent grid point, but the moving direction **must not** be the same as the direction indicated by the character on the current grid point, and you must not move outside the board. There are $q$ queries. Each query gives two grid points $s,t$ and asks whether it is possible to reach $t$ from $s$ by making several moves.

To avoid oversized input, this problem uses a special input method. **Please write and submit using `C++11` or above.** The first line contains four positive integers $n,m,q,seed$, where $seed$ is an input parameter. The next $n$ lines each contain $m$ characters describing the board. ```cpp mt19937_64 R; inline void init(int seed){ R=mt19937_64(seed); } inline int get(int l,int r){ uniform_int_distribution distribution(l,r); return distribution(R); } ``` You need to include this code in your program, and call `init(seed);` during initialization. Then, for $q$ times, call `int a=get(1,n),b=get(1,m),x=get(1,n),y=get(1,m);`, where $a,b,x,y$ describe the positions of $s,t$ as $(a,b),(x,y)$, representing one query.

Output one line containing $q$ characters. The $i$-th character is $0$ if in the $i$-th query $s$ cannot reach $t$, and $1$ otherwise.

**Retribution - Kry.exe & nm-y (Insane 16.2)** ### Sample Explanation **For readability, in Sample 1 and Sample 2, the queries are given directly instead of using the special input method.** For the first query of Sample 1, the grid point $(2,1)$ cannot move out of column $1$. For the fourth query of Sample 1, the grid point $(2,3)$ can move to $(2,2)$ and then to $(1,2)$. For the sixth query of Sample 1, the grid point $(1,3)$ can move to $(1,2),(2,2),(2,3)$ in order. ### Constraints This problem uses bundled testdata. | $\text{Subtask}$ | $n\le$ | $m\le$ | $q\le$ | Score | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $100$ | $100$ | $10^3$ | $10$ | | $2$ | $3$ | $500$ | $2\times10^5$ | $20$ | | $3$ | $300$ | $300$ | $2\times10^5$ | $20$ | | $4$ | $1500$ | $1500$ | $10^6$ | $50$ | For all testdata, it is guaranteed that $1\le n,m\le 1.5\times10^3$, $1\le q\le 10^6$, $c_{i,j}\in\{\texttt{U},\texttt{D},\texttt{L},\texttt{R}\}$, $1\le a,x\le n$, $1\le b,y\le m$, $0\le s