魔法森林里有一颗大树，下面经常有小孩召开法。
大树可以看做一个有 n 个节点，n−1 条边的无向连通图。大树的每个节点都有若干瓶矿泉水，初始第 i 个节点有 ai 瓶矿泉水。
麦杰斯住在大树顶端，有一天他想改造一下大树，方便他巨大多喝水之后可以垃圾分类矿泉水瓶。
麦杰斯喜欢二进制运算，所以他会有以下三种操作：

1. 将树上与一个节点 x 距离为 1 的节点上的矿泉水数量 +1。这里树上两点间的距离定义为从一点出发到另外一点的最短路径上边的条数。
2. 在一个节点 x 上喝掉 v 瓶水。
3. 询问树上与一个节点 x 距离为 1 的所有节点上的矿泉水数量的异或和。

麦杰斯共有 m 次操作，他希望你在每次 3 操作后告诉他答案。

第一行两个正整数 n,m，分别表示树的节点个数和麦杰斯的询问个数。
第二行到第 n 行，每行两个整数表示有一条连接这两个节点的边。
第 n+1 行 n 个整数，第 i 个整数表示初始第 i 个节点上的矿泉水数量。
第 n+2 行到第 n+m+1 行，每行先读入一个整数 opt 表示操作类型。
如果 opt=1 或 3 ，接下来读入一个整数 x 表示麦杰斯操作的节点标号。
否则接下来读入两个整数 x,v 表示麦杰斯操作的节点标号和他喝的水的数量。

对于每一个 3 操作，输出一行一个整数表示答案。

对于 30% 的数据，满足 n≤10³，m≤10³。
对于 60% 的数据，满足 n≤10⁵，m≤10⁵。
对于另外 10% 的数据，存在一个点满足所有点到该节点的距离 ≤1。
对于 100% 的数据，满足 1≤n≤5×10⁵，1≤m≤5×10⁵，0≤ai≤10⁵，1≤x≤n，opt∈{1,2,3}。
保证任意时刻每个节点的矿泉水数非负。
温馨提示：矿泉水瓶不是干垃圾也不是湿垃圾，而是可回收垃圾。

数据结构 Trie