#215181. [UOI 2022 II Stage] 树

克索尼亚有一棵以顶点 为根、包含 个顶点的有根树，每个顶点上写有一个数字。在第 个顶点上写有数字 。

回忆一下，树是一种无环连通图。有根树是指在树中选择一个顶点作为根。

在有根树中，顶点 的祖先是指从 到根路径上的所有顶点（不包括顶点 本身）。顶点 的子树是指所有以 为祖先的顶点集合，包括顶点 本身。

集合 的 XOR 和定义为数字 ，其中 是按位异或操作，在 Pascal 语言中记为 xor，在 C++/Java/Python 语言中记为 ^。

对于数字集合 ，考虑其所有可能子集的 XOR 和构成的集合。称此集合为 。

克索尼亚的朋友不断问她这样的问题——“如果考虑顶点 的子树中所有数字的集合（记为 ），那么集合 中按升序排列的第 个数是什么？”也就是说，如果取出顶点 子树中的所有数字，考虑它们所有子集的 XOR 和，那么在得到的集合中，按升序排列的第 个数是什么？如果不存在这样的数（即 ），则克索尼亚回答数字 。请注意， 是一个集合，而不是多重集。也就是说，如果一个数字出现多次，只应计入一次。

此外，克索尼亚的朋友有时会请她更改树中的一个数字。

第一行包含两个整数 (, ) —— 分别表示树中的顶点数量和测试组编号。

接下来的 行，每行包含两个整数 ()。这表示树中顶点 和 之间有一条边。保证该图是一棵树。

下一行包含 个整数 () —— 表示树顶点上初始数字的数组 。

下一行包含一个整数 () —— 表示查询的数量。

接下来的 行，每行描述一个查询。

更改树中数字的查询格式为 (, )。此类查询表示现在第 个顶点上的数字变为 。

另一种类型的查询格式为 (, )。此类查询需要找出集合 中按升序排列的第 个数，其中 是顶点 子树中的数字集合， 是其所有子集 XOR 和构成的集合。如果 ，则输出 。

对于每个第二类查询，在一个单独的行中输出答案。

样例输入 1

5 0
1 2
1 5
2 3
2 4
4 2 3 1 2
7
2 2 4
2 1 2
2 2 3
1 3 4
2 5 1
2 2 8
2 1 5

样例输出 1

3
1
2
0
7
4

样例说明

第一个样例的解释。顶点旁的数字表示 。

:::align{center} :::

在第一个查询中，考虑顶点 的子树。它包含数字 。

。

在第二个查询中，考虑整个子树。。

更改一个数字后，树的状态如下：

:::align{center} :::

现在，顶点 的子树中包含数字 。

。

评分细则

• （6 分）： 。
• （16 分）： 。
• （18 分）： 。
• （7 分）： 在所有第二类查询中，。
• （13 分）： 没有更改数字的查询。
• （11 分）： 所有 是 2 的幂。
• （29 分）： 无额外限制。

翻译由 DeepSeek V3 完成