ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1890. Деньги из воздуха

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
У каждого сотрудника авиакомпании Oceanic Airlines, кроме директора, есть ровно один непосредственный начальник. Чтобы поощрять отличившихся сотрудников и целые отделы, директор авиакомпании может издавать два типа приказов:
  1. «employee x y z» — если зарплата сотрудника x меньше y долларов, то повысить её на z долларов;
  2. «department x y z» — если средняя зарплата в отделе под началом сотрудника x меньше y долларов, то повысить зарплату каждого сотрудника в этом отделе на z долларов (отдел включает самого сотрудника x и всех его подчинённых, не обязательно непосредственных).
Зная размер зарплаты всех сотрудников Oceanic Airlines на начало года и все приказы о её повышении, отданные директором в течение года, определите величину зарплат сотрудников на конец года. Можно считать, что в течение этого года авиакомпания не приняла на работу и не уволила ни одного сотрудника.

Исходные данные

В первой строке записаны целые числа n, q и s0 — количество сотрудников Oceanic Airlines, количество приказов о повышении зарплаты и зарплата директора на начало года (1 ≤ n, q ≤ 50 000; 0 ≤ s0 ≤ 109). Сотрудники занумерованы целыми числами от 0 до n − 1, директор имеет номер ноль. Далее следует n − 1 строка, в i-й из них записаны целые числа pi и si — номер непосредственного начальника сотрудника с номером i и его зарплата на начало года (0 ≤ pii − 1; 0 ≤ si ≤ 109). Далее идут q строк, описывающие приказы в том порядке, в котором их отдавал директор. Каждый приказ имеет вид «employee x y z» или «department x y z» (обозначения x, y, z описаны ранее). 0 ≤ xn − 1; 1 ≤ y, z ≤ 109.

Результат

Перечислите зарплаты всех сотрудников Oceanic Airlines на конец года. Сотрудников следует описывать в порядке возрастания их номеров.

Пример

исходные данныерезультат
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
Автор задачи: Дмитрий Иванков
Источник задачи: NEERC 2011, Четвертьфинал Восточного подрегиона