Each employee of the company Oceanic Airlines, except for the director, has exactly one immediate superior. To encourage the best employees and best departments, the director can issue two kinds of orders:

1. “employee x y z” — if the salary of employee x is less than y dollars, increase it by z dollars;
2. “department x y z” — if the average salary in the department headed by employee x is less than y dollars, increase the salary of each employee at this department by z dollars (the department includes employee x and all her subordinates, not necessarily immediate).

Given the salaries of all the employees of Oceanic Airlines at the beginning of a year and all the salary increase orders issued by the director during the year, find the salaries of the employees by the end of the year. You may assume that the company didn't hire any new employees and didn't fire anyone during the year.

The first line contains integers n, q, and s₀, which are the number of employees at Oceanic Airlines, the number of salary increase orders, and the director's salary at the beginning of the year (1 ≤ n, q ≤ 50 000; 0 ≤ s₀ ≤ 10⁹). The employees are numbered from 0 to n − 1; the director's number is zero. In the ith of the following n − 1 lines you are given integers p_i and s_i, which are the number of the immediate superior and the salary at the beginning of the year of the employee with number i (0 ≤ p_i ≤ i − 1; 0 ≤ s_i ≤ 10⁹). The following q lines are the director's orders given chronologically. Each order has the form “employee x y z” or “department x y z” (the notation x, y, z is explained above), where 0 ≤ x ≤ n − 1 and 1 ≤ y, z ≤ 10⁹.

Output the salaries of all employees at Oceanic Airlines at the end of the year in the ascending order of the employees' numbers.