H. How Many Groups
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Jaime's company has decided to switch to a new customer service system. The system update will address, among other things, a common issue that occurs when any of the employees go on vacation. The company has N employees with IDs ranging from 1 to N, and each employee has a supervisor with ID $$$s_i$$$, except for the general supervisor. In the system, each employee belongs to a group $$$g_i$$$ and attends only support tickets assigned to the group they belong. It should be noted that if an employee is the only one in a group and goes on vacation, no one will handle the tickets for that group during their absence.

The system update will allow each employee to receive tickets not only from their own group but also from the groups to which each employee on their line of supervision belongs. The line of supervision for an employee $$$e$$$ includes their immediate supervisor, the supervisor's supervisor, and so on until reaching the general supervisor.

Upon learning about this update, many employees have complained, they claim that this update only makes it easier for supervisors to take vacations while they have more work to do. The company's management has asked for your help in measuring the workload for each employee on the new system. Given the number of employees, the supervisor for each employee, and the group they belong to, your task is to count, for each employee, how many different groups they will have to handle tickets for after the system update.

Input

The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^6$$$), the number of employees on the company.

The second line contains $$$N$$$ integer numbers separated by a space, where the $$$i$$$-th number represents the ID of the supervisor $$$s_i$$$ ($$$0 \leq s_i \leq 10^6$$$) for the employee with $$$ID = i$$$. The general supervisor is the only employee where $$$s_i = 0$$$. It is guaranteed all employees line of supervision can reach the general supervisor.

The third and last line contains $$$N$$$ integer numbers separated by a space, where the $$$i$$$-th number represents the group $$$g_i$$$ ($$$1 \leq g_i \leq N$$$) assigned on the system for the employee with $$$ID = i$$$.

Output

Output a line with $$$N$$$ integers separated by a space. The $$$i$$$-th number is the number of different groups for which the employee with $$$ID = i$$$ will have to handle tickets after the system update.

Examples
Input
6
0 1 2 3 4 5
1 1 1 1 1 1
Output
1 1 1 1 1 1
Input
6
0 1 2 3 4 5
1 2 3 4 5 6
Output
1 2 3 4 5 6
Input
6
0 1 2 3 4 5
1 2 3 3 2 6
Output
1 2 3 3 3 4
Input
9
2 3 5 3 0 7 8 5 8
1 9 9 3 2 3 2 7 5
Output
3 2 2 3 1 3 2 2 3