K. 数据结构基本功
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

"为了打好数据结构基本功，深入理解数据结构精神，贯彻落实代码实现工作，我们需要努力学习数据结构的深刻内涵……"

ACM训练基地在开会，可是只听了两句之后猫猫虫就睡了过去，醒来的他面对留下的课后作业感到不知所措，幸运的是，他认识一个数据结构大神，那就是你！为了不让可怜的猫猫虫被学长责罚，你决定帮助他完成数据结构作业。

作业题目如下：

给定一棵以$$$1$$$号点为根节点的树，树上每个点有点权$$$a_i\in \{0,1\}$$$，接下来你需要进行$$$q$$$次操作，操作共分为两种：

  • $$$1$$$ $$$u$$$ $$$v$$$ $$$x$$$，代表将树上的一条以$$$u,v$$$为端点的简单路径上所有点的点权设为$$$x$$$。
  • $$$2$$$ $$$u$$$，代表查询以$$$u$$$为根节点的子树内满足$$$x \lt y, a_x \oplus a_y \oplus a_{lca(x, y)}=0$$$的点对$$$(x,y)$$$的数目。

其中$$$\oplus$$$代表按位异或，即C语言中的位运算符^。

$$$lca(x,y)$$$指$$$x$$$和$$$y$$$两个点的最近公共祖先，如样例3中，$$$lca(4,5)=3$$$。

Input

第一行两个整数$$$n,q(2\leq n \leq 3\times 10^5,1\leq q\leq 3\times 10^5)$$$，代表树上点数和操作数。

第二行$$$n$$$个整数$$$a_i(a_i\in\{0,1\})$$$，代表初始点权。

第三行$$$n-1$$$个整数，第$$$i$$$个整数为$$$f_i(1\leq f_i\leq i)$$$，代表第$$$i+1$$$个点和第$$$f_i$$$个点之间有一条边。

接下来$$$q$$$行，每行为一个操作：

对于每个操作，每行第一个整数为$$$op(op \in\{1,2\})$$$，代表操作类型。

  • 若$$$op=1$$$，则随后三个整数$$$u,v,x(1\leq u,v\leq n,x\in \{0,1\})$$$，代表覆盖的链的两个端点，以及这条链被覆盖为的权值。
  • 若$$$op=2$$$，则随后一个整数$$$u(1\leq u\leq n)$$$代表需要查询的子树根节点。
Output

对于每个询问，输出一行一个整数代表这次询问的答案。

Examples
Input
2 1
0 0
1
2 1
Output
1
Input
3 3
0 0 1
1 1
2 1
1 1 2 1
2 1
Output
1
0
Input
5 5
1 0 0 1 1
1 1 3 3
1 5 4 1
1 2 4 0
2 3
1 2 1 1
2 1
Output
1
5
Note

对于样例3，第一次询问时，经过前两次覆盖之后的树点权为$$$\{0,0,0,0,1\}$$$，子树3中合法的点对为$$$(3,4)$$$。

第二次询问时，经过前三次覆盖之后的树点权为$$$\{1,1,0,0,1\}$$$，子树1中合法的点对为$$$(1,3),(1,4),(2,3),(2,4),(3,4)$$$ 。