Star Ruler's Tree Query

The Star Ruler possesses a celestial disk that can be abstracted as a rooted tree with root node \(1\). Each node \(i\) in the tree has two stars: a red star and a blue star with brightness values \(\text{Red}_i\) and \(\text{Blue}_i\) respectively.

For every node \(x\), determine how many nodes in its subtree (excluding \(x\) itself) satisfy both of the following conditions:

• \(\text{Red}_y \leq \text{Red}_x\)
• \(\text{Blue}_y \leq \text{Blue}_x\)

Output the answers for the nodes in increasing order of their indices. To reduce output size, if the answer for a node is \(0\), you may omit printing it.

inputFormat

The input is given in the following format:

 n
 Red_1 Red_2 ... Red_n
 Blue_1 Blue_2 ... Blue_n
 p_2
 p_3
 ...
 p_n

Here, \(n\) is the number of nodes. The second line contains \(n\) integers representing the red star brightness values for nodes \(1\) to \(n\). The third line contains \(n\) integers representing the blue star brightness values. The next \(n-1\) lines each contain an integer \(p_i\) (for \(i=2,3,\ldots,n\)) where \(p_i\) is the parent of node \(i\). It is guaranteed that the tree is rooted at node \(1\).

outputFormat

For every node whose answer is non-zero, output a line with two space-separated integers: the node number and its answer. The nodes should be processed in increasing order of their indices. If a node's answer is \(0\), it does not need to be output.

sample

3
3 1 2
3 2 1
1
1

1 2