Yer
Rəşad avtomobillərə böyük maraq göstərir və nəhayət öz avtomobil zavodunu açmağa nail olub! Zavodda N işçi çalışır və hər birinin dəqiq bir rəhbəri var (Rəşaddan başqa - o, avtomatik olaraq hər kəsin rəhbəridir). Rəşad 1 nömrəsi ilə təyin olunur, digər işçilər isə 2-dən N-ə qədər nömrələnir. Hər bir işçi, tabeliyində olanların maaşını artıra və ya azalda bilər (həm birbaşa tabeliyində olanlar, həm də iyerarxiya ağacında daha aşağıda olanlar). Rəşadın vəzifəsi belə gücün sui-istifadəsinin qarşısını almaqdır, buna görə də o, zaman-zaman müəyyən bir işçinin maaşını öyrənmək istəyir. Sizdən maaş dəyişikliklərini izləyən bir proqram yazmağınızı xahiş edir, giriş bölməsində təsvir olunan əmrlər ardıcıllığı verilir.
Giriş:
Girişin ilk sətri iki boşluqla ayrılmış müsbət tam ədəd N (1 ≤ N ≤ 500 000), işçilərin sayı və M (1 ≤ M ≤ 500 000), maaş dəyişiklikləri və maaş sorğularının sayı. Növbəti N sətir işçilər haqqında məlumatı ehtiva edir 1, 2, ..., N (müvafiq olaraq): başlanğıc maaşı və onun birbaşa rəhbərinin identifikatoru. Qeyd: Rəşadın rəhbəri yoxdur, ona görə də onun sətri yalnız başlanğıc maaşını ehtiva edəcək.
Növbəti M sətir aşağıdakılardan birini ehtiva edir:
p A X - işçi A bütün tabeliyində olanların maaşını X məbləğində artırır (və ya mənfi X halında azaldır) (-10 000 ≤ X ≤ 10 000);
u A - Rəşad işçi A-nın maaşını bilmək istəyir.
Çıxış:
Çıxışda girişdəki hər bir ‘2’ sorğusu üçün bir sətir olmalıdır - verilmiş işçinin cari maaşı.