题目描述

给定一棵 $n$ 个点的树，每个点有两个点权 $a_i,b_i$，定义 $f(S)$ 为包含点集 $S$ 的最小连通块，接下来有 $q$ 次操作，每次操作形如：

• 操作一：给定 $l,r,v$，令 $S$ 为 $[l,r]$ 中所有数构成的集合，对所有 $i\in f(S)$，将 $a_i$ 加上 $v\times b_i$。
• 操作二：给定 $x$，查询 $a_x$ 的值。
• 操作三：给定 $x$，查询 $1\sim x$ 路径上所有点的 $a$ 值之和。

答案对 $2^{32}$ 取模。

强制在线。

输入格式

第一行两个数 $n,q$，表示树的大小和操作次数。

第二行 $n$ 个数，表示序列 $a$。

第三行 $n$ 个数，表示序列 $b$。

接下来 $n-1$ 行，每行两个数 $x,y$ ，表示树的一条边。

接下来 $q$ 行，每行先输入一个数 $op$，若 $op=1$，则接下来输入三个数 $l,r,v$ 表示操作一，若 $op=2$，则接下来输入一个数 $x$ 表示操作二，若 $op=3$，则接下来输入一个数 $x$ 表示操作三。

你需要将操作一中的 $l,r,v$ 、操作二中的 $x$ 和操作三中的 $x$ 异或上上一次查询操作的答案 $lasans$，特别地，若这次操作前不存在查询操作，则 $lasans=0$。

输出格式

对于每个操作二和操作三，输出一行表示答案对 $2^{32}$ 取模后的结果。

4 5
2 3 4 5 
5 3 2 1 
3 1
3 2
2 4
2 4
1 6 1 4
2 4
1 3 6 2
3 3

5
2
2

提示

对于 $100\%$ 的数据，$1\le n\le 8\times 10^5,1\le q\le 3\times 10^5,0\le l,r,v,x,a_i,b_i<2^{32}$。

保证 $l,r,v,x$ 解密后满足 $1\le l\le r\le n,0\le v<2^{32},1\le x\le n$。

记 $cnt_1$ 为 $op=1$ 的操作数量，$cnt_2$ 为 $op=2$ 的操作数量，$cnt_3$ 为 $op=3$ 的操作数量，保证 $\max(cnt_1,cnt_2,cnt_3)\le 0.6q$。