Mancunian And Colored Tree#3983
After a long and busy work week, the residents of Manchester and Liverpool decided to go hiking for the weekend. While walking through the forest, they came across a unique tree consisting of vertices. The vertices of the tree are numbered from to , and each one is painted in one of possible colors.
To fight off boredom, they decided to test their logical thinking. The root of the tree is vertex . For each vertex, the participants decided to find its nearest ancestor that shares the same color.
The first line contains two integers and (1 \le n, c \le 10^5): the number of vertices in the tree and the number of possible colors.
The second line contains n - 1 integers: the -th of them indicates the parent of vertex i + 1.
The third line contains integers: the colors of the vertices. Each color is an integer from to , inclusive.
Print integers in a single line: for each vertex, print the number of its nearest ancestor with the same color. If no such ancestor exists, print .
Example 1