为了支持唱k的花销，小凯应聘了BridgeBridge公司。这个公司位于神奇的死亡搁浅世界，在这里只要有材料和开罗尔打印机就可以打印任何物品，并且，由于神秘的冥滩之力的影响，材料不能简单叠加，多个材料组合打印，他们的价值将是他们的异或和*，特别的，为了防止有人把材料挥霍一空，打印机无法组合出价值为0的物品。山姆是BridgeBridge里的传奇送货员，他抱着B不停地在户外捡垃圾、亲切的访问米尔人的基地和大战BT，并将获得的材料送往各个城市。现在，我们将他要去送材料的城市群看成一棵树的结构，树的根结点是1号城市——主结市，并且作为父亲的城市可以使用儿子城市的所有材料，这个使用权是可传递的，也就是说祖先城市可以使用所有子孙城市的材料。
作为Bridge员工的码农小凯，会收到两种信息：
1. 山姆向城市x运送了价值y的材料，所以现在城市x多了一种价值y的材料。
2. 领导要求小凯算出当前城市x利用所有能使用的材料，可以组合出的不同价值的第k小价值是多少，如果没有第k小就回答−1。
现在，小凯去唱k了，把他的任务交给了你，你要帮他完成计算第k小的工作。
简化题意：
给一棵有n个结点的以1为根的树T，每个点是一个集合。
m 个操作分为两种：
1.向一个点的集合里加入一个数
2. 查询树的一棵以u为根的子树，求子树u的所有集合组成的并的集合中，能组合出的不同的非零异或和第k小是多少，如果没有第k小，输出−1。
*异或：0⊕0=0,0⊕1=1,1⊕0=1,1⊕1=0,n个数的异或和：⊕i=1nai,异或具有交换律。
多组数据，第一行一个整数T表示有T组数据。
每组数据第一行两个整数n,m满足1≤n,m≤1e51≤n,m≤1e5且∑i=1Tn≤2e5,∑i=1Tm≤2e5
接下来n−1行每行两个整数u,v表示树上有一条u连向v的边,树以1为根.
接下来mm行每行一个操作三个数op,x,y满足1≤op≤2,1≤x≤n,1≤y≤1e9
op=1表示操作1，向结点xx的集合里添加数y
op=2表示操作2，询问以xx为根的子树的所有结点集合的并组成的集合中，非零的第y小的异或和是多少
输入数据较多，为防止读入引发的超时，请最好只使用关闭同步流的cin/cout
2
5 7
1 2
1 3
2 4
2 5
1 1 1
2 1 1
1 4 2
2 1 3
1 2 4
2 1 6
2 2 2
4 5
1 2
2 3
3 4
1 2 1
2 1 2
1 3 2
1 4 3
2 1 11
3
6
4
-1
1
第一组数据中，山姆首先向1号城市送了价值1的材料，那么1号城市能使用的材料集合是1,然后询问1号城市能组合出的第1小价值，是1。然后山姆向4号城市运送了价值2的材料，那么1号城市能使用的材料集合是1,2然后询问1号城市能组合出的第3小价值那么是1⊕2=3。山姆再向2号城市送了价值4的材料。然后询问1号城市能组合出第6小的价值，此时11号城市能使用的材料集合是1，2，4,那么第66小的价值是2⊕4=6 ，然后询问2号城市能组合出第2小的价值，2号城市能使用的材料集合是2,4,那么第2小的价值是4。
第二组数据中，山姆首先向2号城市送了价值1的材料，那么11号城市能使用的材料集合是1,然后询问1号城市能组合出的第2小价值，因为只能组合出一种价值，所以不存在第2小的价值，输出−1。然后又向3号城市送了2，向4号城市送了3，最后询问1号城市的第1小价值，此时1号能用1,2,3 但是因为不能组合出 0，所以第1小还是1。