You are in the business of creating and decorating miniature trees for wealthy clients, and your friend has told you of a client that is looking for a certain type of tree. Specifically, they want a tree with coloured baubles, but each layer of baubles must be all the same colour, and different to the colours in the other layers.

You do a quick survey of some of your inventory to see which trees are suitable. Each tree is given with a single root node (bauble) as well as numerous other nodes which each have a different node as their parent. Additionally, each node has an integer representing its colour. For each tree, determine whether or not it meets the criterion of the client, that is, that every node some distance away from the root is the same colour, and that all layers have distinct colours from each other.

Input

The first line contains a single integer ~n\ (1 \leq n \leq 10^6)~, the number of baubles in the tree. Each bauble is labelled ~0~ through to ~n-1~.

The next line contains integers ~n~ integers given as ~c_i\ (1 \leq c_i \leq 10^9)~, the colour of the ~i~th bauble.

The next line contains integers ~n-1~ integers given as ~p_i\ (0 \leq p_i \leq n-1, p_i\neq i)~, the parent of the ~i~th node. Since the root node has no parent, the first (index ~0~) integer in this line refers to the parent of the second overall (index ~1~) node.

Output

Output whether or not the given tree follows the above criteria: that all nodes any given distance from the root have the same colour, distinct to the different layers. If it does fit the criteria, output "Valid", otherwise output "Invalid".

Example

Input 1

5
1 3 2 2 3
2 0 0 2

Output 1

Valid

The tree given can be illustrated as below:

The nodes are numbered by their index, and the colours are assigned as ~1~ to red, ~2~ to green, and ~3~ to yellow. It can be seen that the properties are satisfied for this tree.

Input 2

4
1 2 3 3
0 0 1

Output 2

Invalid

The tree given can be illustrated as below:

The nodes and colours are similarly assigned. It can be seen that the nodes in the layer one down from the root have different colours - green and yellow - so the criteria is not satisfied.