You are given a tree that represents a hierarchy in a company, where the parent of node u is their direct manager.
Each employee is assigned a project, and multiple employees can be assigned to the same project. When it is time for the presentation of the ith project, all employees u that are assigned that project and their direct and indirect managers must attend the presentation (u and their manager and their manager's manager and so on until the CEO).
Find for each project the number of people attending its presentation.
The first line of input is n and m (1 ≤ m ≤ n ≤ 106), the number of employees and the number of projects, respectively.
The second line of input contains n integers ai (1 ≤ ai ≤ m), where ai is the project assigned to the ith employee. It is guaranteed that each project has at least one employee assigned to it.
The third line of input contains n integers pi (0 ≤ pi ≤ n), where pi is the direct manager of the ith employee. If pi = 0, then the ith employee is the CEO and does not have a manager. It is guaranteed that there is only one CEO, and this CEO is a direct or indirect manager of all other employees.
Output m integers, where the ith integer is the number of people attending the presentation of the ith project.
## Input
The first line of input is n and m (1 ≤ m ≤ n ≤ 106), the number of employees and the number of projects, respectively.The second line of input contains n integers ai (1 ≤ ai ≤ m), where ai is the project assigned to the ith employee. It is guaranteed that each project has at least one employee assigned to it.The third line of input contains n integers pi (0 ≤ pi ≤ n), where pi is the direct manager of the ith employee. If pi = 0, then the ith employee is the CEO and does not have a manager. It is guaranteed that there is only one CEO, and this CEO is a direct or indirect manager of all other employees.
## Output
Output m integers, where the ith integer is the number of people attending the presentation of the ith project.
[samples]
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ with $ 1 \le m \le n \le 10^6 $.
Let $ A = (a_1, a_2, \dots, a_n) $, where $ a_i \in \{1, \dots, m\} $ is the project assigned to employee $ i $.
Let $ P = (p_1, p_2, \dots, p_n) $, where $ p_i \in \{0, 1, \dots, n\} $ is the direct manager of employee $ i $, and $ p_i = 0 $ iff employee $ i $ is the CEO.
Let $ T = (V, E) $ be a tree with vertex set $ V = \{1, \dots, n\} $, and edge set $ E = \{ (i, p_i) \mid p_i \ne 0 \} $, rooted at the unique CEO.
For each employee $ u \in V $, let $ \text{Ancestors}(u) $ denote the set of nodes on the unique path from $ u $ to the root (including $ u $).
**Constraints**
1. Each project $ j \in \{1, \dots, m\} $ has at least one assigned employee: $ \exists i \in \{1, \dots, n\} $ such that $ a_i = j $.
2. The graph $ T $ is a tree with exactly one root (CEO) and $ n-1 $ edges.
**Objective**
For each project $ j \in \{1, \dots, m\} $, compute:
$$
f(j) = \left| \bigcup_{\substack{i=1 \\ a_i = j}}^n \text{Ancestors}(i) \right|
$$
Output $ f(1), f(2), \dots, f(m) $.