#214942. [THUPC 2026 初赛] 庭中有奇树

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）初赛。

题解等资源可在 https://gitlink.org.cn/thusaa/thupc2026pre 查看。

mej 先生的庭院里有一棵奇树。

这棵树上每个点都有一个正整数编号，且以编号为 的点为根，所有正整数都作为点的编号在这棵树上出现过。同时，编号为 的点恰好有 个子节点，并且这 个子节点的编号是连续的：记 为 号节点的子节点中编号最小的、 为最大的，则 且 ∼ 中所有数都恰好出现一次。不仅如此，对于任意的 ，都有 。

可以发现以上性质唯一确定了这棵奇树。例如， 号节点的子节点有 ， 号节点的子节点有 、， 号节点的子节点有 、、，等等。不过因为 mej 先生不喜欢无限大的树，所以他只保留了这棵树上编号在 ∼ 之间的节点。

mej 先生可以从这棵奇树上获取法力。具体来说，树上每个节点都有一个魔力值，初始时所有节点的魔力值都为 ；他可以选择一个节点 开始获取法力，此时他将会获得 的子树中（包括 ）所有节点魔力值的异或和的法力。同时他还会对这棵树进行维护，每次他会选择一个节点 和一个值 ，然后施加法术，将 的子树中所有节点的魔力值按位或上 。

现在，mej 先生一共进行了 次操作，每次操作可能是维护奇树或者获取法力。他想知道，他每次获取法力时获取的法力值是多少。

从标准输入读入数据。

第一行输入两个正整数 、（，），表示树的大小和操作次数。

接下来 行，每行先输入一个正整数 （)，表示操作类型。若 ，则再输入两个整数 、（，），表示将以 为根的子树中所有节点的魔力值按位或 ；若 ，则再输入一个正整数 ，表示查询以 为根的子树中所有节点魔力值的异或和。

输出到标准输出。

对于每次查询，输出一个整数，表示所求的异或和。

样例输入 1

11 6
1 3 931
1 4 209
1 2 28
2 1
1 8 287
2 4

样例输出 1

193
479

【样例 1 解释】

初始时所有节点的魔力值都为 。

第一次操作，将以 为根的子树中所有节点的魔力值按位或 ，所有节点的魔力值序列变为 0,0,931,0,931,931,931,0,0,0,0；

第二次操作，将以 为根的子树中所有节点的魔力值按位或 ，所有节点的魔力值序列变为 0,0,931,209,931,931,931,209,209,209,209；

第三次操作，将以 为根的子树中所有节点的魔力值按位或 ，所有节点的魔力值序列变为 0,28,959,221,959,959,959,221,221,221,221；

第四次操作，查询以 为根的子树中所有节点的魔力值的异或和，即 ；

第五次操作，将以 为根的子树中所有节点的魔力值按位或 ，所有节点的魔力值序列变为 0,28,959,221,959,959,959,479,221,221,221；

第六次操作，查询以 为根的子树中所有节点的魔力值的异或和，即 。