Kaskelen 市有 $n$ 条横向街道和 $n$ 条纵向街道，它们构成了一个矩形网格。我们将横向街道从北到南编号为 $1$ 到 $n$，将纵向街道从西到东编号为 $1$ 到 $n$。记十字路口 $(i, j)$ 为第 $i$ 条横向街道与第 $j$ 条纵向街道的交点。
由于 Kaskelen 市的交通非常繁忙，市政府决定将所有街道改为单行道。然而，这种改革也有一些弊端。首先，Kaskelen 是一个快速发展的城市，管理部门经常需要改变某些街道的方向。其次，有时可能会出现无法从城市的一部分到达另一部分的情况。
为了跟踪这些变化，请你编写一个程序来模拟这个街道系统。你需要处理三种类型的查询：
- $1 \ r_1 \ c_1 \ r_2 \ c_2$ — 检查是否可以从十字路口 $(r_1, c_1)$ 移动到十字路口 $(r_2, c_2)$。
- $2 \ r$ — 将第 $r$ 条横向街道的方向改为相反方向。
- $3 \ c$ — 将第 $c$ 条纵向街道的方向改为相反方向。
该图对应第一个样例
输入格式
每个测试包含多个测试用例。输入的第一行包含一个整数 $t(1 \le t \le 1000)$，表示测试用例的数量。接下来是各测试用例的描述。
每个测试用例的第一行包含两个整数 $n$ 和 $q(2 \le n \le 3 \cdot 10^5, 1 \le q \le 3 \cdot 10^5)$，分别表示横向/纵向街道的数量和查询的数量。
第二行包含一个长度为 $n$ 的字符串 $a$，表示横向街道的描述。如果 $a_i = \text{'L'}$，则第 $i$ 条道路的方向为从东向西。否则，如果 $a_i = \text{'R'}$，则方向为从西向东。
第三行包含一个长度为 $n$ 的字符串 $b$，表示纵向街道的描述。如果 $b_i = \text{'U'}$，则第 $i$ 条道路的方向为从南向北。否则，如果 $b_i = \text{'D'}$，则方向为从北向南。
接下来的 $q$ 行，每行包含一个查询，格式如题目描述中所述。
保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$，且所有测试用例中 $q$ 的总和不超过 $3 \cdot 10^5$。
输出格式
对于每种类型为 $1$ 的查询，如果可以从一个十字路口移动到另一个，则输出 “YES”，否则输出 “NO”。
评分
记 $S$ 为所有测试用例中 $n$ 的总和，记 $T$ 为所有测试用例中 $q$ 的总和。
| 子任务 | 附加约束 | 分值 | 必要子任务 |
|---|---|---|---|
| 0 | 样例 | 0 | |
| 1 | $S \le 10, T \le 10^4$，无第二、三类查询 | 12 | |
| 2 | $S \le 80, T \le 2 \cdot 10^5$，无第二、三类查询 | 15 | 1 |
| 3 | $a_1 = a_2 = \dots = a_n$，无第二类查询 | 14 | |
| 4 | $S, T \le 1000$，无第二、三类查询 | 16 | |
| 5 | $S, T \le 50000$，无第二、三类查询 | 22 | 1, 4 |
| 6 | 21 | 0, 2, 3, 5 |
样例
输入格式 1
1 4 4 LRRL UDDU 1 1 4 3 1 1 1 4 4 4 3 4 1 1 4 4 4
输出格式 1
YES NO YES