题目背景

题目描述

给你一个 $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$ 个字符描述棋盘。

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);
}

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

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

提示

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$		$10^3$	$10$
$2$	$3$	$500$	$2\times10^5$	$20$
$3$	$300$
$4$	$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<2^{31}$。

子任务依赖

本题开启所有合理的子任务依赖。