P12704 Retribution


给你一个 $n\times m$ 的棋盘，每个格点上标有一个字符 $c_{i,j}\in\{\texttt{U},\texttt{D},\texttt{L},\texttt{R}\}$，分别代表上、下、左、右。在一个格点可以移动到一个与它相邻的格点，但移动方向**不能**与当前所在格点上的字符所代表的方向相同且不能移出棋盘。 给出 $q$ 次询问，每次询问给出两个格点 $s,t$，询问能否从格点 $s$ 通过若干次移动到达格点 $t$。

为避免输入数据过大，本题使用特殊的读入方式。**请使用 `C++11` 及以上的语言进行编写与提交。** 第一行四个正整数 $n,m,q,seed$，其中 $seed$ 为输入参数。 接下来 $n$ 行，每行 $m$ 个字符描述棋盘。 ```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); } ``` 你需要在你的代码中加入此段代码，初始化时调用 `init(seed);` 接下来 $q$ 次调用 `int a=get(1,n),b=get(1,m),x=get(1,n),y=get(1,m);`，其中 $a,b,x,y$ 分别描述 $s,t$ 的位置 $(a,b),(x,y)$，表示一次询问。

输出一行 $q$ 个字符，第 $i$ 个字符为 $0$ 表示第 $i$ 个询问中 $s$ 无法到达 $t$，为 $1$ 则表示第 $i$ 个询问中 $s$ 可以到达 $t$。

**Retribution - Kry.exe & nm-y (Insane 16.2)** ### 样例解释 **为了便于阅读，对于样例 1 和样例 2，直接输入了询问而不使用特殊方式读入。** 对于样例 1 第一次询问，格点 $(2,1)$ 无法移动出第 $1$ 列。 对于样例 1 第四次询问，格点 $(2,3)$ 可以移动到 $(2,2)$ 从而移动到 $(1,2)$。 对于样例 1 第六次询问，格点 $(1,3)$ 可以依次移动到 $(1,2),(2,2),(2,3)$。 ### 数据规模 本题采用捆绑测试。 | $\text{Subtask}$ | $n\le$ | $m\le$ | $q\le$ | 分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $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$ | 对于所有数据，保证 $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