给定一棵包含 $n$ 个节点的树。树的节点编号从 $1$ 到 $n$。第 $i$ 个节点的颜色为 $col_i$。

你需要执行 $m$ 次操作。每次操作为以下两种之一：

• “1 $x$ $y$” ($1 \le x, y \le n$)：将第 $x$ 个节点的颜色修改为 $y$。
• “2 $a$ $b$ $c$ $d$” ($1 \le a, b, c, d \le n$)：令 $f(u, v)$ 表示从 $u$ 到 $v$ 的简单路径上出现的不同颜色的数量。你需要回答 $f(a, b) > f(c, d)$ 是否成立。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 4$)，表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 500\,000, 1 \le m \le 10\,000$)，分别表示节点数和操作数。

第二行包含 $n$ 个整数 $col_1, col_2, \dots, col_n$ ($1 \le col_i \le n$)，表示每个节点的初始颜色。

接下来的 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示 $u_i$ 号节点和 $v_i$ 号节点之间的一条双向边。

接下来的 $m$ 行描述了上述格式的操作，但为了强制在线处理，部分参数经过了加密。

令 $cnt$ 为在该测试用例中你之前回答为“Yes”的查询次数。注意，在每个新的测试用例中，$cnt$ 应重置为 $0$。对于每次操作，$x, y, a, b, c$ 和 $d$ 均经过加密：它们的实际值分别为 $x \oplus cnt, y \oplus cnt, a \oplus cnt, b \oplus cnt, c \oplus cnt$ 和 $d \oplus cnt$。在上述表达式中，符号“$\oplus$”表示按位异或运算。同时请注意，题目描述中给出的约束仅适用于解密后的对应参数，加密后的值不受这些约束限制。

保证对于每次查询，$f(a, b) \ge 2f(c, d)$ 或 $f(c, d) \ge 2f(a, b)$ 总是成立。

输出格式

对于每次查询，输出一行。如果 $f(a, b) > f(c, d)$ 为真，输出“Yes”。否则，输出“No”。

样例

输入 1

1
8 4
1 2 1 4 1 3 3 2
1 2
2 3
3 4
3 5
1 6
6 7
6 8
2 1 4 3 5
2 7 6 5 9
1 4 9
2 2 4 7 6

输出 1

Yes
No
Yes