有一棵有根树，根为 $1$ ，点有点权。

现在有 $m$ 次操作，操作有 $3$ 种：

$1\ x\ y\ w$ ，将 $x$ 到 $y$ 的路径上的点点权加上 $w$ (其中 $w=\pm{1}$ )；

$2\ x\ y$ ，询问在 $x$ 到 $y$ 的路径上有多少个点点权 $>0$ ；

$3\ x$ ，询问在 $x$ 的子树里的点有多少个点点权 $>0$ 。

输入格式

第一行三个数 $n,m,T$ ，表示树的结点个数，操作个数，和是否加密。

接下来 $n-1$ 行，每行 $2$ 个数 $x\ y$，表示结点 $x$ 和 $y$ 之间有一条边。

接下来一行 $n$ 个数，第 $i$ 个数表示结点 $i$ 的初始点权。

接下来 $m$ 行，每行格式见题目描述。

如果 $T=1$ ，则这 $m$ 行读入的每个 $x,y$ 都需要异或 $last\_ans$ 才能得到真实的输入，其中 $last\_ans$ 表示上一次询问操作的答案，如果不存在上一次询问操作则为 $0​$ 。

输出格式

对于每个询问操作，输出一行表示答案。

样例一

input

5 5 0
1 2
1 3
3 4
3 5
1 0 0 0 0
2 2 5
3 3
1 2 5 1
2 2 5
3 3

output

1
0
4
2

限制与约定

• 对于所有数据，$1 \le n \le 10^5$ ，$1 \le m \le 10^5$ ，$-10^9 \le$ 点权 $\le 10^9$ ，
• $subtask1(3pts):n,m \le 5000$ 。
• $subtask2(10pts):$ 给定的树是一条链。
• $subtask3(15pts):T=0$ ，且不存在操作 $3​$ 。
• $subtask4(15pts):T=0$ 。
• $subtask5(10pts):n,m \le 50000$ 。
• $subtask6(47pts):$ 没有额外的限制。

时间限制：$\texttt{2s}$

空间限制：$\texttt{512MB}$

下载

样例数据下载