题目背景

译自 Potyczki Algorytmiczne 2017 R5 Osady i warownie [A] (OSA)。$\texttt{3s,512M}$。

原题为函数式交互题，此处改为强制在线的传统题。

题目描述

一个长为 $n$，宽为 $m$ 的长方形被划分为 $n\times m$ 个 $1\times 1$ 的方格。我们记第 $i$ 行第 $j$ 列的方格为 $(i,j)$。

每个方格可能是城镇，堡垒或者空地。商人在城镇间来往贸易，可以从一个方格移动到四连通的方格，但是不能经过堡垒。

有 $q$ 次在线操作：

• $\texttt{1}$ $r$ $c$：在 $(r,c)$ 上尝试建立一座堡垒，保证 $(r,c)$ 是空地。
  • 如果建立堡垒后，商人仍能从一个城镇到达任意一个城镇，则建立成功，$(r,c)$ 变为堡垒，输出 $1$；
  • 否则忽略本次操作，$(r,c)$ 仍为空地，输出 $0$。
• $\texttt{2}$ $r_1$ $c_1$ $r_2$ $c_2$：
  • 将 $(r_1,c_1)$ 上的城镇移动到相邻的 $(r_2,c_2)$。
  • 保证 $(r_1,c_1)$ 是城镇，$(r_2,c_2)$ 是空地。
  • 保证 $|r_1-r_2|+|c_1-c_2|=1$。

输入格式

注意，本题的输入量可能很大。

第一行两个正整数 $n,m$。

接下来 $n$ 行，第 $i$ 行一个长度为 $m$ 的字符串 $s_i$：

• $s_{i,j}=\texttt{.}$，表示 $(i,j)$ 是空地；
• $s_{i,j}=\texttt{W}$，表示 $(i,j)$ 是堡垒；
• 否则 $s_{i,j}=\texttt{K}$，表示 $(i,j)$ 是城镇。

第 $(n+2)$ 行，一个整数 $q$。

接下来 $q$ 行，每行若干个整数，表示一次加密的操作：

• $\texttt{1}$ $r'$ $c'$，表示一次 $\texttt{1}$ 操作，其中 $r=r'\oplus k$，$c=c'\oplus k$。
• $\texttt{2}$ $r_1'$ $c_1'$ $r_2'$ $c_2'$：表示一次 $\texttt{2}$ 操作，其中 $r_1=r_1'\oplus k$，$r_2=r_2'\oplus k$，$c_1=c_1'\oplus k$，$c_2=c_2'\oplus k$。

这里，$k$ 表示这次操作前，操作 $\texttt{1}$ 输出 $1$ 的个数，$\oplus$ 表示按位异或运算。

输出格式

输出一行一个 $\texttt{01}$ 串：对于每个 $\texttt{1}$ 操作，输出一行一个整数，表示答案。

3 4
..WK
WK..
...K
5
1 3 2
1 3 2
2 3 3 3 2
2 3 2 2 2
1 3 2

101

提示

样例解释

加密前的样例：

3 4
..WK
WK..
...K
5
1 3 2
1 2 3
2 2 2 2 3
2 2 3 3 3
1 2 3

• $1\le n,m\le 10^3$；
• $0\le q\le 10^6$。