408041: GYM102966 E Enterprise Recognition Program

Jaime's delivery package organization is growing, the number of employees is getting bigger every month, and they bill and have earnings never seen before. Jaime decided it's time to have some hierarchy in the organization, therefore, he worked arranging the $$$N$$$ employees of his company identified with the numbers from $$$1$$$ to $$$N$$$, in such way that each employee has a manager who supervises the employee's work, the only employee who will not have a manager is Jaime. In this hierarchy, it is said that an employee $$$A$$$ reports to another employee $$$B$$$ if you can reach $$$A$$$ following the hierarchy moving through the managers starting from $$$B$$$. The reporting unit of an employee $$$A$$$ consists of all the employees $$$B$$$ such that $$$B$$$ reports to $$$A$$$, including also the employee $$$A$$$. The reporting unit of Jaime will always be the entire company (all the employees).

An organization growing is good news, and it does not mean only good news for Jaime, but for all the employees, during the last year Jaime hired a software company to develop an employee recognition program. This recognition program gives points to employees who have excelled in their work, and also it can give points to all the managerial chain of an employee if the employee has contributed significantly to the company, this is, in some cases the recognition points are earned only to an employee, in other cases the same amount of recognition points will be earned to the employee, the employee's manager, the employee's manager's manager, and so on until they reach Jaime.

Jaime has recorded all the $$$M$$$ recognition prizes the company has granted to the employees during the year, and now, he wants to answer some queries that the software he has is incapable to answer: how many recognition points employee $$$A$$$ has earned, and how many recognition points have been distributed to the entire reporting units of employee $$$B$$$. Since you have helped Jaime before, he came to you asking for help. Your task is to write a program, knowing who is the manager of each employee and the $$$M$$$ recognition prizes, to answer all of Jaime's queries.

he first line of input contains three integer numbers separated by a space, $$$N$$$, $$$M$$$, and $$$Q$$$ ($$$1 \leq N, M, Q \leq 10^6$$$), representing the number of employees in Jaime's company, the number of recognition prizes, and the number of queries Jaime wants to answer. The next line contains $$$N$$$ integer numbers separated by a space, where the $$$i$$$-th number in the line represents the id of the employee who is the manager of employee $$$i$$$, since Jaime does not have a manager, his manager in the input will have the id $$$0$$$.

The next $$$M$$$ lines contains three integer numbers separated by a space $$$m_i$$$ ($$$1 \leq m_i \leq 2$$$), $$$e_i$$$ ($$$1 \leq e_i \leq N$$$), $$$v_i$$$ ($$$1 \leq v_i \leq 10$$$), describing the $$$i$$$-th recognition prize. If $$$m_i = 1$$$, then the recognition prize of $$$v_i$$$ points was earned by the individual employee $$$e_i$$$, if $$$m_i = 2$$$ then the recognition prize of $$$v_i$$$ points was earned to the managerial chain of employee $$$e_i$$$.

The next $$$Q$$$ lines contains two integer numbers separated by a space $$$t_i$$$ ($$$1 \leq t_i \leq 2$$$) and $$$e_i$$$ ($$$1 \leq e_i \leq N$$$), each describing one of Jaimes queries. If $$$t_i = 1$$$, Jaime wants to know how many recognition points employee $$$e_i$$$ earned. If $$$t_i = 2$$$, Jaime wants to know how many recognition points were distributed to the reporting unit of employee $$$e_i$$$.

For each of Jaime's queries print a line with a single integer number, where the $$$i$$$-th line contains the answer to the $$$i$$$-th query Jaime made.

5 5 7
2 3 0 2 3
1 1 1
1 2 1
1 4 1
2 5 3
2 1 2
1 1
1 2
1 3
1 4
1 5
2 2
2 3

3
3
5
1
3
7
15