У каждого сотрудника авиакомпании Oceanic Airlines, кроме директора, есть ровно один непосредственный начальник. Чтобы поощрять отличившихся сотрудников и целые отделы, директор авиакомпании может издавать два типа приказов:

1. «employee x y z» — если зарплата сотрудника x меньше y долларов, то повысить её на z долларов;
2. «department x y z» — если средняя зарплата в отделе под началом сотрудника x меньше y долларов, то повысить зарплату каждого сотрудника в этом отделе на z долларов (отдел включает самого сотрудника x и всех его подчинённых, не обязательно непосредственных).

Зная размер зарплаты всех сотрудников Oceanic Airlines на начало года и все приказы о её повышении, отданные директором в течение года, определите величину зарплат сотрудников на конец года. Можно считать, что в течение этого года авиакомпания не приняла на работу и не уволила ни одного сотрудника.

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

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