Halftime Changes

Task

You are given a tree with $N$ nodes, with root in node $1$, and two arrays $A$ and $B$, having $N$ elements, indexed from $1$ to $N$.

It is guaranteed that each level of the tree contains at most $100$ nodes.

You have to select some nodes $Y$ for which it is possible to choose:

• a subset $S(Y)$ of nodes on the path from the root to $Y$; S(Y) can be empty
• a node $X(Y)$ that is a proper ancestor of both $Y$ and all the nodes from $S(Y)$.

Such as the following condition holds:

A proper ancestor of $V$ is any node $U$ such that node $U$ is an ancestor of node $V$ and $U$ is not the same node as $V$.

Before solving the problem, just like Nea' Gigi, the owner of FCSB, often makes miraculous changes at halftime, you are allowed to make changes. You can change at most $K$ elements of the array $A$. The changed values are at least $1$ and at most $10^7$.

Take note that $K$ is not given in the input. In the description of the subtasks it is specified the value of $K$ depending on $N$.

After the changes are made and the nodes are selected as specified in the above statement, let $M$ be the number of selected nodes $Y$.

You will be scored based on how large the number $M$ is.
Note: You are not required to find the maximum possible value of $M$. You will get the points for a subtask if $M$ meets the condition specified in the subtask description.

Input data

The first line contains the number $N$. The second line contains $N-1$ values, where the $i$-th value represents the parent of node $i+1$. The third line contains $N$ integers, representing the array $A$. The last line contains $N$ integers, representing the array $B$.

Output data

The first line contains the elements of the array $A$ after the changes, in order from $1$ to $N$. The second line contains an integer $M$, representing the number of nodes $Y$ that satisfy the given condition. The following $M$ lines contains data about chosen nodes $Y$.
Each of these $M$ lines has the following format:

• The node $Y$ which satisfies the condition.
• The chosen proper ancestor node $X(Y)$.
• The size of the selected subset $S(Y)$ of nodes (can be $0$).
• The nodes in the subset $S(Y)$ (if any).

The values on the same line in the output are separated by a single space.

Constraints and clarifications

• $1 \leq N \leq 400 \ 000$
• $1\leq A_i, B_i \leq N, (1 \leq i \leq N)$
• The solution is not unique and you will be scored according to the subtasks description.

Example

stdin

6
1 1 2 2 3
3 2 1 2 3 2
1 5 2 3 2 5

stdout

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

Explanation

In the array $A$, $3$ changes were made for positions $1$, $2$, and $3$.

The number of nodes $Y$ that satisfy the condition after the changes is $M=3$.

For example, one of the selected nodes is $Y=2$, $X(2) = 1$ and the subset $S(Y)$ has 1 node, $S(2) = \{2\}$. It can be observed that $A[1] - A[2] = 10 - 5 = 5 = B[2]$.

Another selected node is $Y=5$, $X(5) = 1$ and the subset $S(Y)$ has 2 nodes, $S(5) = \{2, 5\}$. It can be observed that $A[1] - (A[2] + A[5]) = 10 - (5 + 3) = 2 = B[5]$.