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:
- “employee x y z” — if the salary of employee x is less than y
dollars, increase it by z dollars;
- “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 s0, 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 ≤ s0 ≤ 109). 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 pi and si, which are the number of the immediate superior
and the salary at the beginning of the year of the employee with number i (0
≤ pi ≤ i − 1; 0 ≤ si ≤ 109). 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 ≤ 109.
Output the salaries of all employees at Oceanic Airlines at the end of the
year in the ascending order of the employees' numbers.
4 3 1
employee 2 15 1
employee 3 5 1
department 0 10 1
Problem Author: Dmitry Ivankov
Problem Source: NEERC 2011, Eastern subregional contest