Competitions

# Mancunian And Colored Tree

After a hectic week at work, Mancunian and Liverbird decide to go on a fun weekend camping trip. As they were passing through a forest, they stumbled upon a unique tree of n nodes. Vertices are numbered from 1 to n.

Each node of the tree is assigned a color (out of c possible colors). Being bored, they decide to work together (for a change) and test their reasoning skills. The tree is rooted at vertex 1. For each node, they want to find its closest ancestor having the same color.

#### Input

The first line contains two integers n and c (1n, c105) denoting the number of vertices in the tree and the number of possible colors.

The second line contains n - 1 integers. The i-th integer denotes the parent of the i + 1 - th vertex.

The third line contains n integers, denoting the colors of the vertices. Each color lies between 1 and c inclusive.

#### Output

Print n space-separated integers. The i-th integer is the vertex number of lowest ancestor of the i-th node which has the same color. If there is no such ancestor, print -1 for that node.

Time limit 1 second
Memory limit 128 MiB
Input example #1
5 4
1 1 3 3
1 4 2 1 2

Output example #1
-1 -1 -1 1 3