有一棵有根树，根为 $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}$