8989: Fundamental Skills in Data Structures

“To strengthen the fundamental skills in data structures and gain a profound understanding of the essence of data structures, as well as to implement code effectively, we need to make efforts to study the profound connotation of data structures...”

The ACM Training base is having a meeting, but after listening to only two sentences, Capoo the cat falls asleep. When he wakes up, he feels at a loss facing the homework left behind. Luckily, he knows a data structure expert, which is you! In order to prevent poor Capoo from being scolded by his senior, you decide to help him complete his data structure homework.

[capoo_confused.jpg](Please imagine it, we can't display it for you due to copyright reasons. T.T)

The homework questions are as follows:

Given a tree rooted at node $1$, each node in the tree has a node weight ai∈{0,1}a_i\in \{0,1\}ai∈{0,1}. Now, you need to perform $q$ operations, which can be divided into two types:

•  $1$ $u$ $v$ $x$, which means setting the node weights of all the nodes on the simple path between $u$ and $v$ (inclusive) to $x$.
•  $2$ $u$, which means querying the number of pairs of nodes (x,y)(x,y)(x,y) in the subtree rooted at $u$ such that $x<y$ and ax⊕ay⊕alca(x,y)=0a_x \oplus a_y \oplus a_{lca(x, y)}=0ax⊕ay⊕alca(x,y)=0 holds.

Here, $\oplus$ represents the bitwise XOR operation, similar to the XOR operator (^) in C/C++.

lca(x,y)lca(x,y)lca(x,y) refers to the lowest common ancestor of nodes $x$ and $y$. For example, in Sample 3, lca(4,5)=3lca(4,5)=3lca(4,5)=3.

The first line consists of two integers, $n$ and $q$ (2≤n≤3×105,1≤q≤3×105)(2\leq n \leq 3\times 10^5,1\leq q\leq 3\times 10^5)(2≤n≤3×105,1≤q≤3×105), representing the number of nodes in the tree and the number of operations, respectively.
The second line contains $n$ integers, aia_iai (ai∈{0,1})(a_i\in\{0,1\})(ai∈{0,1}), representing the initial node weights.
The third line contains $n-1$ integers, where the $i$th integer, fif_ifi (1≤fi≤i)(1\leq f_i\leq i)(1≤fi≤i), represents the existence of an edge between the $(i+1)$th node and the fif_ifith node.
Following are $q$ lines, each representing an operation:
For each operation, the first integer of the line, $op$ $(op\in \{1,2\})$, denotes the type of operation.

• If $op=1$, then the next three integers, $u$, $v$, and $x$ (1≤u,v≤n,x∈{0,1})(1\leq u,v\leq n,x\in \{0,1\})(1≤u,v≤n,x∈{0,1}), represent the two endpoints of the covered chain and the assigned weight for that chain.
  
• If $op=2$, then the next integer, $u$ $(1\le u\le n)$, represents the root node of the subtree for which a query is required.
  

For each query, output a single line containing an integer representing the answer to that query.

For Sample 3, in the first query, after the first two coverings, the node weights of the tree become $\{0,0,0,0,1\}$, and the valid point pairs in subtree 3 are $(3,4)$.
In the second query, after the first three coverings, the node weights of the tree become $\{1,1,0,0,1\}$, and the valid point pairs in subtree 1 are $(1,3),(1,4),(2,3),(2,4),(3,4)$.