Background

Problem Description

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.

Input Format

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.

mt19937_64 R;
inline void init(int seed){
    R=mt19937_64(seed);
}
inline int get(int l,int r){
    uniform_int_distribution<int> 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 Format

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.

2 3 6 0
RLD
RLU
2 1 1 3
2 2 1 3
2 3 1 1
2 3 1 2
1 2 2 3
1 3 2 3

010111

3 3 5 0
DRU
ULU
DRD
1 1 1 3
1 3 1 1
3 1 2 1
2 3 2 1
1 1 1 1

01111

2 3 6 10000001
RLD
RLU

111001

Hint

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.

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<2^{31}$.

Subtask Dependencies

All reasonable subtask dependencies are enabled for this problem.

Translated by ChatGPT 5