平凡的测试数据

【题目描述】

树链剖分可以干什么？

“可以支持在树中快速修改一个点信息，快速询问一条链信息”

LCT可以干什么？

“可以支持树链剖分支持的特性，并且支持快速链接两个棵树，或者断开某条边”

那我现在要出一道关于树的题目，一开始有n个点，每个点自成一颗树，所以现在有n棵树。每个点有一个权值。有以下这些操作类型：

连接操作：1 a b，连接a和b，使a成为b的儿子结点，a一定是某个树的根节点。这样就把两棵树连接到一起，此时a以及所有后代的根节点均为b所在树的根节点。

询问操作：2 a，询问a到树根路径上的所有点（包括自己和根）的权值异或和。

恩...但是由于我懒，所以还没有造数据，请你帮我写个标程让我用来造数据吧。

【输入格式】

第一行两个整数n和m，表示有n个点和m个操作。

接下有一行n个整数，第i个整数表示第i个点的权值。

接下来m行，每行包含一个操作1 a b或者2 a，操作具体含义见题目描述。

【输出格式】

对于每个询问操作，输出一行，表示从a到根路径上所有点的权值异或和。

【样例输入】

5 8
1 2 3 4 5
2 2
1 2 1
2 2
1 4 3
1 3 2
2 3
1 5 1
2 5

【样例输出】

2
3
0
4

【样例解释】

样例中每个节点权值与标号相同；

第一个询问中2的根节点是自己，所以第一个询问2节点的答案为2；

第二个询问中2的根节点是1，路径为2-1，所以答案为2 xor 1 = 3；

第三个询问中3到根节点的路径为3-2-1，所以答案为3 xor 2 xor 1 = 0；

第四个询问中5到根节点的路径为5-1，所以答案为5 xor 1 = 4；

【数据范围与约定】

对于40%的数据1 <= n,m <= 1000；

对于90%的数据1 <= n <= 100000, 1 <= m <= 200000；

对于100%的数据1 <= n <= 300000， 1 <= m <= 500000；

所有节点的权值均为正整数且在int范围内。

大样例