There are $$$n$$$ employees at Odoo numbered from $$$1$$$ to $$$n$$$, each employee has exactly $$$1$$$ manager, except for the head with the number $$$1$$$ who has no manager. So they form a rooted tree.
We call employee $$$a$$$ a subordinate of another employee $$$b$$$ if either $$$b$$$ is the manager of $$$a$$$, or the manager of $$$a$$$ is a subordinate of employee $$$b$$$. In particular, subordinates of the head are all other employees of the company.
You will be given very sensitive information: An integer array $$$A$$$ of size $$$n$$$ where $$$A_i$$$ is the salary of the $$$i_{th}$$$ employee at Odoo $$$(1 \le i \le n)$$$.
For the following $$$q$$$ years, at the beginning of the year, one lucky employee $$$u$$$ is picked alongside an integer value denoted as $$$x$$$. For that employee, their salary will be multiplied by $$$x$$$. Also, for all subordinates of $$$u$$$ their salary will be multiplied by $$$x$$$ as well.
An employee is happy at some year if their salary was divisible by $$$k$$$ in that year. You will be given the value of $$$k$$$ and your goal is to print $$$n$$$ integers where the $$$i_{th}$$$ integer $$$(1 \leq i \leq n)$$$ is the first year at which employee number $$$i$$$ was happy.
If one employee was happy initially print $$$0$$$ and if they were never happy print $$$-1$$$.
The first line contains $$$3$$$ integers $$$n$$$, $$$k$$$, $$$q$$$, $$$(1 \leq n, q \leq 2*10^{5})$$$ $$$(1 \leq k \leq 10^{9})$$$
The second line contains $$$n$$$ integers $$$A_1, A_2, .. , A_n$$$ $$$(1 \le A_i \le 10^{9})$$$
The third line contains $$$n - 1$$$ integers $$$P_2, P_3, .. , P_n$$$ where $$$P_i$$$ is the manager of employee number $$$i$$$. $$$(1 \le P_i \le n)$$$
Then $$$q$$$ lines follow, The $$$i_{th}$$$ line contains two integers $$$u_i$$$ and $$$x_i$$$ $$$(1 \le u_i \le n) (1 \le x_i \le 10^{9})$$$
Print $$$n$$$ integers, the answer to the problem
5 4 41 2 3 4 61 1 2 22 33 21 22 7
-1 3 3 0 3
9 10 84 6 7 4 9 10 8 7 96 6 6 7 1 1 7 18 23 59 73 65 26 22 106 10
-1 7 4 8 -1 0 -1 -1 -1
