T566569 「PA Mashup #1」商旅

一个长为 $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}$ 操作，输出一行一个整数，表示答案。 特别地，输出可能为空。

#### 样例解释 加密前的样例： ```plain 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$。