题目描述

给你一个 $n\times m$ 的表格，每个格子上标有一个字符 $c_{i,j}\in\{\texttt{U},\texttt{D},\texttt{L},\texttt{R}\}$，分别代表上、下、左、右。在一个格点可以移动到一个与它相邻的格点，但移动方向不能与当前所在格点上的字符所代表的方向相同且不能移出表格。

给出 $q$ 次询问，每次询问给出两个格点 $s,t$，询问能否从格点 $s$ 通过若干次移动到达格点 $t$。

输入格式

为避免输入数据过大，本题使用特殊的读入方式。

第一行四个正整数 $n,m,q,seed$，其中 $seed$ 为输入参数。 接下来 $n$ 行，每行 $m$ 个字符描述表格。

namespace Input{
    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);
    }
}
using Input::init;
using Input::get;

你需要在你的代码中加入此段代码，初始时调用 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$。

样例 #1

样例输入 #1

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

样例输出 #1

010111

样例 #2

样例输入 #2

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

样例输出 #2

01111

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

样例输出 #2

样例 #3

样例输入 #3

2 3 6 10000001
RLD
RLU

样例输出 #3

111001

提示

样例解释

为了便于阅读，对于样例 1 和样例 2，直接输入了询问而不使用特殊方式读入。

对于样例 1 第一次询问，格点 $(2,1)$ 无法移动出第 $1$ 列。

对于样例 1 第四次询问，格点 $(2,3)$ 可以移动到 $(2,2)$ 从而移动到 $(1,2)$。

对于样例 1 第六次询问，格点 $(1,3)$ 可以依次移动到 $(1,2),(2,2),(2,3)$。

数据规模

本题采用捆绑测试。

对于 $100\%$ 的数据，$1\le n,m\le 1.8\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}$。