Nim

著名游戏设计师 vfleaking 最近迷上了 Nim 游戏。

普通的 Nim 游戏由两名玩家进行。游戏开始时有 $n$ 堆石子，每名玩家每回合可以从任意一堆中取走任意正整数颗石子，也可以将该堆全部取完。无法继续取石子的一方失败。

为了寻找合适的初始局面，vfleaking 准备了 $n$ 堆石子，编号为 $1,2,\ldots,n$，并在石子堆之间连接了 $n-1$ 条边。图中不存在自环和重边，且任意两堆石子之间都恰好存在一条路径。

接下来，vfleaking 会进行以下两类操作：

• 选择两堆石子 $v,u$，询问以从 $v$ 到 $u$ 的路径上的所有石子堆作为 Nim 游戏的初始局面时，先手是否存在必胜策略；
• 将第 $v$ 堆石子的数量修改为 $k$。

请你编写程序，回答所有询问。

输入格式

第一行包含一个整数 $n$，表示石子堆的数量。

第二行包含 $n$ 个整数，其中第 $i$ 个整数表示第 $i$ 堆石子的数量。

接下来 $n-1$ 行，每行包含两个整数 $v,u$，表示石子堆 $v$ 与石子堆 $u$ 之间有一条边直接相连。

接下来一行包含一个整数 $q$，表示操作的数量。

接下来 $q$ 行，每行描述一个操作：

• Q v u：询问以从 $v$ 到 $u$ 的路径上的所有石子堆作为 Nim 游戏的初始局面时，先手是否存在必胜策略；
• C v k：将第 $v$ 堆石子的数量修改为 $k$。

输出格式

对于每个 Q 操作输出一行。如果先手存在必胜策略，输出 Yes；否则输出 No。

样例输入

5
1 3 5 2 5
1 5
3 5
2 5
1 4
6
Q 1 2
Q 3 5
C 3 7
Q 1 2
Q 2 4
Q 5 3

样例输出

Yes
No
Yes
Yes
Yes

数据范围

• 对于全部数据，$1\le n\le 5\times 10^5$，$1\le q\le 5\times 10^5$；
• 在任意时刻，每堆石子的数量均满足 $0\le k\le \mathrm{INT\_MAX}$；
• 对于 $30\%$ 的数据，石子堆构成一条链，使用递归深度优先搜索可能会导致栈溢出；其他数据使用深度优先搜索预计不会发生栈溢出。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

5
1 3 5 2 5
1 5
3 5
2 5
1 4
6
Q 1 2
Q 3 5
C 3 7
Q 1 2
Q 2 4
Q 5 3

输出

Yes
No
Yes
Yes
Yes