Given a tree with $n$ nodes that satisfies the following properties:

1. All leaves are at the same depth.
2. The nodes are labeled according to a BFS order, constructed as follows:
   1. Let the root be labeled 1 and add it to a queue.
   2. Each time a node is dequeued, assign its children the next available labels in sequence, and add them to the queue in that order.

Each node has a weight, initially 0.

There are two types of operations:

• Operation 1: Add $y$ to the weight of every node in the subtree rooted at $x$.
• Operation 2: Perform a cyclic shift of the node weights, moving the weight of node $i$ to node $(i \bmod n) + 1$.

Calculate the weight of each node after $q$ operations. To avoid large output, output the XOR sum of all node weights.

Input

The first line contains two integers $n$ and $q$, representing the size of the tree and the number of operations.

The next line contains $n-1$ integers, where the $i$-th integer $fa[i+1]$ represents the parent of node $i+1$ (based on the BFS property, $fa[i] \leq fa[j]$ when $i \leq j$).

The following $q$ lines describe the operations. If the line is 1 x y, it represents Operation 1: add $y$ to the nodes in the subtree of $x$. If the line is 2, it represents Operation 2: perform the cyclic shift.

Output

Output a single integer representing the XOR sum of all node weights.

Examples

Input 1

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

Output 1

10

Note 1

The actual weights are:

9 11 6 6 5 13

The XOR sum is 10.

Constraints

For 100% of the data: $n, Q \leq 100,000$, $y \leq 10,000$.