ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

NEERC 2011, Eastern subregional contest

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Money out of Thin Air

Time limit: 1.0 second
Memory limit: 64 MB
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.

Input

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 ≤ pii − 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 ≤ xn − 1 and 1 ≤ y, z ≤ 109.

Output

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

Sample

inputoutput
4 3 1
0 10
0 10
1 10
employee 2 15 1
employee 3 5 1
department 0 10 1
2
11
12
11
Problem Author: Dmitry Ivankov
Problem Source: NEERC 2011, Eastern subregional contest
To submit the solution for this problem go to the Problem set: 1890. Money out of Thin Air