Given a rooted tree with $n$ vertices, labeled $1, 2, \dots, n$, where vertex $1$ is the root. Define the directed neighborhood $N(x, y)$ as the set of vertices in the subtree rooted at $x$ that are at a distance less than $y$ from $x$, where $1 \le x \le n$ and $0 \le y \le n$ are integers.

Given $m$ directed neighborhoods $N(x_i, y_i)_{i=1}^m$, you start from $N(1, 0)$ (which, by definition, is an empty set). You must reach each of the given directed neighborhoods using at most $5m$ operations. The available operations are:

1. Move from the current directed neighborhood $N(x, y)$ to $N(x', y')$ such that $N(x, y) \subseteq N(x', y')$.
2. Undo the last operation 1, returning to the state before the most recent un-undone operation 1, and mark that operation 1 as undone.
3. Declare that the current directed neighborhood is $N(x_i, y_i)$, provided the current neighborhood is indeed $N(x_i, y_i)$.

The cost of operation 1 is the difference in the number of elements between the neighborhood after the move and the neighborhood before the move. Operations 2 and 3 have no cost. Operation 2 can only be performed if there is an un-undone operation 1. Operation 3 must be performed exactly once for each $1 \le i \le m$.

You must ensure that the total cost of all operations does not exceed $2.5 \times 10^9$.

Input

The input is read from standard input.

The first line contains two integers $n$ and $m$.

The next line contains $n-1$ integers, representing the parents $f_2, \dots, f_n$ of vertices $2, 3, \dots, n$ respectively. It is guaranteed that the parent's index is less than the child's index.

The next $m$ lines each contain two integers $x_i$ and $y_i$, representing each given directed neighborhood.

Output

The output is written to standard output.

The first line contains an integer $m'$, the number of operations performed.

The next $m'$ lines describe each operation in order:

Operation 1 is represented as 1 x' y'.

Operation 2 is represented as 2.

Operation 3 is represented as 3 i.

Examples

Input 1

8 4
1 1 1 2 2 2 5
2 1
1 1
6 0
1 2

Output 1

16
1 2 1
3 1
2
1 6 0
3 3
2
1 1 1
1 1 1
3 2
2
1 1 2
1 1 2
3 4
2
2
2

Subtasks

For $100\%$ of the data, $1 \le n, m \le 10^6$, $1 \le f_i \le i-1$, $1 \le x_i \le n$, and $0 \le y_i \le n$. All values are integers.