شجره‌نامه (Family Tree)

یاسین تصمیم گرفته شجره‌نامه‌ی خانواده خود را بسازد.

او تصویر $n + 1$ نفر را در اختیار دارد. همچنین سن هر کدام از افراد را می‌داند. اما از بین این افراد فقط بزرگ خاندان را می‌شناسد.

یاسین نزد بزرگ خاندان می‌رود تا از او برای ساخت شجره‌نامه کمک بگیرد. اما بزرگ خاندان به او می‌گوید این مسخره‌بازیا چیه بچه و برای او یک سوال مطرح می‌کند تا توانایی درخت ساختنش را به چالش بکشد.

بزرگ خاندان به‌یاسین می‌گوید که برایش یک درخت ریشه‌دار بسازد. هر راس این درخت یک اندیس دارد و روی راس با اندیس $i$، عدد $a_i$ نوشته شده است. در ابتدا درخت یک راس با اندیس $0$ دارد که روی آن عدد $+\infty$ نوشته شده است.

بزرگ خاندان در $n$ مرحله، هر مرحله‌یک راس به درخت اضافه می‌کند.

او در مرحله‌ی $i$-ام عدد $p_i$ را به‌یاسین می‌گوید و سپس از او می‌خواهد راس $i$ را به‌یکی از دو نحو زیر به درخت اضافه کند:

1. راس $i$ را فرزند راس $p_i$ قرار می‌دهد؛ یعنی یک یال بین راس $i$ و $p_i$ می‌کشد.$0 \leq p_i < i$)
2. بزرگ خاندان ابتدا از یاسین می‌خواهد که پایین‌ترین جد راس $p_i$ را پیدا کند که عددش از $a_i$ کمتر نباشد.($0 \leq p_i < i$) در صورتی که $a_{p_i} \geq a_i$، راس $i$ را فرزند راس $p_i$ قرار می‌دهد؛ یعنی یک یال بین راس $i$ و $p_i$ می‌کشد. در غیر این صورت یاسین باید رئوس $v$ و $u$ را طوری پیدا کند که:
   • هر دو جد راس $p_i$ باشند. (راس $p_i$ هم یکی از اجداد خودش است.)
   • راس $v$ پدر راس $u$ باشد.
   • نامساوی $a_u < a_i \leq a_v$ و به ازای هر راس مانند $z$ که $v$ جد $z$ و $z$ جد $p_i$ باشد داریم $a_z < a_i$.
   • حال راس $i$ را وسط یال $v$ به $u$ اضافه می‌کنیم. یعنی راس $v$ پدر راس $i$ و راس $i$ پدر راس $u$ می‌شود.

در انتها بزرگ خاندان از او می‌خواهد به ازای هر راس از $1$ تا $n$ پدرش در درخت نهایی را به او بگوید. یاسین که از برآورده کردن خواسته‌های پیرمرد‌ها و درخت‌هایشان خسته شده بود از شما می‌خواهد کمکش کنید تا خود را به بزرگ خاندان ثابت کند.

در خط اول ورودی عدد $n$ می‌آید.

سپس در خط $i$-ام از $n$ خط بعدی، سه عدد $t_i$ ، $p_i$ و $a_i$ به ترتیب آمده اند.

اگر $t_i$ برابر با $1$ بود این عملیات از نوع اول و اگر برابر با $2$ بود از نوع دوم است.

در تنها خط خروجی باید $n$ عدد چاپ کنید که عدد $i$-ام باید پدر راس $i$ در درخت نهایی باشد.

• زیرمسئله اول (۷ نمره): $n \leq 5000$.
• زیرمسئله دوم (۱۲ نمره): $a_i \leq 2$.
• زیرمسئله سوم (۸۱ نمره): بدون محدودیت اضافی

• $1 \leq n \leq 10^6$
• $t_i \in \{ 1, 2 \}$
• $0 \leq p_i < i$
• $1 \leq a_i \leq n$