Место
Рашад обожает автомобили и, наконец, открыл свой собственный автозавод! На заводе трудятся N сотрудников, у каждого из которых есть ровно один начальник (за исключением Рашада, который является начальником всех по умолчанию). Рашад имеет номер 1, а остальные сотрудники пронумерованы от 2 до N. Каждый сотрудник может изменять зарплату всех своих подчиненных (как непосредственных, так и тех, кто ниже в иерархии). Задача Рашада — предотвращать злоупотребления этой властью, поэтому время от времени он хочет знать зарплату конкретного сотрудника. Он просит вас создать программу, которая поможет ему отслеживать изменения зарплат, учитывая последовательность команд, описанных в разделе ввода.
Ввод:
Первая строка ввода содержит два положительных целых числа, разделенных пробелом: N (1 ≤ N ≤ 500 000), количество сотрудников, и M (1 ≤ M ≤ 500 000), количество изменений зарплат и запросов зарплат.Следующие N строк содержат информацию о сотрудниках 1, 2, ..., N (соответственно): начальная зарплата и идентификатор его непосредственного начальника. Примечание: у Рашада нет начальника, поэтому его строка будет содержать только его начальную зарплату.
Следующие M строк содержат одну из следующих команд:
p A X - сотрудник A увеличивает (или уменьшает, если X отрицательное) зарплату всех своих подчиненных на величину X (-10 000 ≤ X ≤ 10 000);
u A - Рашад хочет узнать зарплату сотрудника A.
Вывод:
Для каждого запроса типа ‘2’ во входных данных выведите одну строку с текущей зарплатой данного сотрудника.