+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- رتبه‌ی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند! رتبه‌ی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت! بیماری عجیبی در مدرسه شایع شده بود! خرچشمی! تیم پزشکی حلی‌سه (که همان تیم کامپیوتر هم هست) تصمیم گرفتند آزمونی طراحی کنند تا برای بیماران چاره‌ای بیندیشند! آزمون از $n$ برگه تشکیل شده‌است. در هر برگه **یک خط** از **حروف** نوشته شده‌‌است. نفر $i$ام باید برگه $i$ام را بخواند و حرف‌ها را **با رعایت ترتیب** در خط بعد بنویسد. در ورودی حروف برگه $i$ام در یک خط و جواب نفر $i$ام در خط بعد از آن داده می‌شود. بیماری خرچشمی به قدری عجیب است که ممکن است برای بازنویسی هر خط دو اتفاق زیر بیفتند: 1. غلط عادی: بین بعضی حرف‌ها **فاصله‌های اضافی(اسپیس اضافی)** ایجاد شود یا **فاصله های لازم ** حذف شوند! 2. غلط فاحش: تنها و تنها **یک حرف** از حروف برگه به کلی حذف شود! تیم بیوتک مدرسه تخصصی در این زمینه ندارد! لذا برگه‌ها را برای شما فرستادند تا تعداد غلط‌های فاحش(**شماره ی دو**) را به سمپاد اطلاع دهید! # ورودی در سطر اول ورودی عدد $n$ آمده‌است که نمایانگر تعداد نفرات است. در $2\times n$ سطر بعد, در سطر $2\times i$ ام خط داخل برگه $i$ ام و در سطر بعد از آن, نوشته‌ی نفر $i$ام آمده است. هیچ تضمینی نیست که در جواب ، نفرات تمام کلمه‌ها را چسبیده به هم و بدون اسپیس(space) اضافی یا با اسپیس لازم بنویسند. به زبانی دیگر فاصله‌ی حروف در جواب افراد هیچ قاعده ای ندارد! تضمین می‌شود که در جواب افراد حداکثر یک حرف نوشته نشده است! تعداد حرف ها با احتساب اسپیس‌های اضافه از $1\ 000\ 000$ بیشتر نیست. $$1 \leq n \leq 1\ 000\ 000$$ # خروجی تعداد غلط‌ها را چاپ کنید! # مثال ## ورودی نمونه ۱ 2 valaei zadeh asl valaeizadehasl Chamran C h m ran ## خروجی نمونه ۱ 1 اولین نفر درست گفته است اما دومین نفر حرف سوم را حذف کرده‌است. ## ورودی نمونه ۲ 3 pashaei zadeh pash aei zad eh salam salam salamsalam ghasemipoor gh as empoor ## خروجی نمونه ۲ 1 تنها آخرین نفر اشتباه گفته‌است.

بولوف الکی!

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

رتبه‌ی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند!

رتبه‌ی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت!

بیماری عجیبی در مدرسه شایع شده بود! خرچشمی!

تیم پزشکی حلی‌سه (که همان تیم کامپیوتر هم هست) تصمیم گرفتند آزمونی طراحی کنند تا برای بیماران چاره‌ای بیندیشند!

آزمون از $n$ برگه تشکیل شده‌است. در هر برگه یک خط از حروف نوشته شده‌‌است. نفر $i$ ام باید برگه $i$ ام را بخواند و حرف‌ها را با رعایت ترتیب در خط بعد بنویسد. در ورودی حروف برگه $i$ ام در یک خط و جواب نفر $i$ ام در خط بعد از آن داده می‌شود.

بیماری خرچشمی به قدری عجیب است که ممکن است برای بازنویسی هر خط دو اتفاق زیر بیفتند:

غلط عادی: بین بعضی حرف‌ها فاصله‌های اضافی(اسپیس اضافی) ایجاد شود یا *فاصله های لازم * حذف شوند!
غلط فاحش: تنها و تنها یک حرف از حروف برگه به کلی حذف شود!

تیم بیوتک مدرسه تخصصی در این زمینه ندارد! لذا برگه‌ها را برای شما فرستادند تا تعداد غلط‌های فاحش(شماره ی دو) را به سمپاد اطلاع دهید!

ورودی🔗

در سطر اول ورودی عدد $n$ آمده‌است که نمایانگر تعداد نفرات است. در $2\times n$ سطر بعد, در سطر $2\times i$ ام خط داخل برگه $i$ ام و در سطر بعد از آن, نوشته‌ی نفر $i$ ام آمده است. هیچ تضمینی نیست که در جواب ، نفرات تمام کلمه‌ها را چسبیده به هم و بدون اسپیس(space) اضافی یا با اسپیس لازم بنویسند. به زبانی دیگر فاصله‌ی حروف در جواب افراد هیچ قاعده ای ندارد!

تضمین می‌شود که در جواب افراد حداکثر یک حرف نوشته نشده است!

تعداد حرف ها با احتساب اسپیس‌های اضافه از $1\ 000\ 000$ بیشتر نیست. $1 \leq n \leq 1\ 000\ 000$

خروجی🔗

تعداد غلط‌ها را چاپ کنید!

مثال🔗

ورودی نمونه ۱🔗

2
valaei zadeh asl
valaeizadehasl
Chamran
C h   m ran

خروجی نمونه ۱🔗

اولین نفر درست گفته است اما دومین نفر حرف سوم را حذف کرده‌است.

ورودی نمونه ۲🔗

3
pashaei zadeh
pash aei zad eh
salam salam
salamsalam
ghasemipoor
gh as empoor

خروجی نمونه ۲🔗

تنها آخرین نفر اشتباه گفته‌است.

خیلی قهوه ای یا باج یا خوش‌خوار!

محدودیت زمان: ۰.۵ ثانیه
محدودیت حافظه: ۱۲۸ مگابایت

رتبه‌ی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند!

رتبه‌ی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت!

مدتی پیش تصمیم گرفته بودم وارد بازار عرضه‌ی کتاب کنکور شوم! و این دقیقاً پس از آن بود که قیمت‌های سرسام آورش کمرم را شکسته بود! درحال حاضر $a_1$ ‌ شیمیِ خیلی قهوه ای و $a_2$ دیفرانسیلِ باج و $a_3$ هندسه یِ خوشخوار داریم. هر بار می‌توانیم یکی از دو کار را انجام دهیم:

دو تا از یک نوع را بفروشیم.
دو تا از انواع مختلف بدهیم و یکی از نوع دیگر پس بگیریم.

اگر در آخر دقیقاً یکی از یک نوع بماند آن از کدام نوع ها می‌تواند باشد؟

ورودی🔗

در تنها خط ورودی سه عدد $a_1$ , $a_2$ , $a_3$ می آیدکه هرکدام تعداد یک نوع کتاب را معلوم می‌کند.

$0 \leq a_i \leq 1\ 000\ 000\ 000$

خروجی🔗

در تنها خط خروجی سه کلمه بنویسید و در $i$ امین کلمه معلوم کنید که آیا می‌توان طوری کار ها را انجام داد که در آخر تنها یکی از نوع $i$ بماند(و از انواع دیگر چیزی نمانده باشد). اگر ممکن بود YES، و در غیر این صورت ‍‍‍NO را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

1 1 1

خروجی نمونه ۱🔗

NO NO NO

ورودی نمونه ۲🔗

1 1 2

خروجی نمونه ۲🔗

NO NO YES

به راحتی می‌توان با این سری اعمال به یکی از نوع سوم رسید: (1,2) (3,3)

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- رتبه‌ی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند! رتبه‌ی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت! مدرسه‌ی حلی سه از $n$ دانش آموز تشکیل شده‌است. $n$ کتاب دیفرانسیل از موسسات متمایز بین آن‌ها پخش شده‌است به طوری که هر نفر یک کتاب دارد. کتابی که نفر $i$ام در اختیار دارد از موسسه‌ی $a_i$ام است. در حالی که نفر $i$ام فقط می‌تواند کتاب‌های موسسه‌ی $i$ را مطالعه کند. می‌خواهیم به هر کس کتاب متناسب او را بدهیم! برای اینکار هر بار می‌توانیم کتاب نفر $i$ ام را با نفر $j$ ام عوض کنیم اگر $j-i| \leq \frac{n}{2} + 1$| باشد. شما باید دنباله‌ای از جابه‌جایی ها بدهید که هر جابه‌جایی به صورت دو عدد $i$ و $j$ است و کتاب‌های نفر $i$ام و $j$ ام را باهم جابه‌جا می‌کند. پس از انجامِ به ترتیب جابه‌جایی ها، هر کس باید کتاب متناسب با خودش را داشته باشد(یعنی نفر $i$ام کتاب موسسه‌ی $i$ام را داشته باشد). به علت کمبود زمان تعداد جابه‌جایی ها باید کوچکتر مساوی $\frac{3 \cdot n}{2} $ باشد. # ورودی در خط اول ورودی $n$ تعداد افراد آمده است سپس در خط بعد یک جایگشت از اعداد $1$ تا $n$ به عنوان آرایه ی $a$ آمده است. $$1 \leq n \leq 200\ 000$$ $$1 \leq a_i \leq n$$ # خروجی در خط اول خروجی $q$ تعداد جابه‌جایی‌ها بیاید. سپس $q$ خط در هر کدام دو عدد $i$ و $j$ باشد که بیانگر جابه‌جایی کتاب‌های $i$ ام و $j$ ام است.با این شرط که $j-i| \leq \frac{n}{2} + 1$| و $q$ کوچکتر مساوی $\frac{3 \cdot n}{2} $ باشد. # مثال ## ورودی نمونه ۱ ``` 4 3 2 1 4 ``` ## خروجی نمونه ۱ ``` 1 3 1 ``` ## ورودی نمونه ۲ ``` 5 5 4 3 2 1 ``` ## خروجی نمونه ۲ ``` 4 1 3 3 5 1 3 2 4 ```

هر که بامش بیش درسش بیش‌تر!

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

رتبه‌ی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند!

رتبه‌ی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت!

مدرسه‌ی حلی سه از $n$ دانش آموز تشکیل شده‌است. $n$ کتاب دیفرانسیل از موسسات متمایز بین آن‌ها پخش شده‌است به طوری که هر نفر یک کتاب دارد. کتابی که نفر $i$ ام در اختیار دارد از موسسه‌ی $a_i$ ام است. در حالی که نفر $i$ ام فقط می‌تواند کتاب‌های موسسه‌ی $i$ را مطالعه کند.

می‌خواهیم به هر کس کتاب متناسب او را بدهیم! برای اینکار هر بار می‌توانیم کتاب نفر $i$ ام را با نفر $j$ ام عوض کنیم اگر $j-i| \leq \frac{n}{2} + 1$ | باشد.

شما باید دنباله‌ای از جابه‌جایی ها بدهید که هر جابه‌جایی به صورت دو عدد $i$ و $j$ است و کتاب‌های نفر $i$ ام و $j$ ام را باهم جابه‌جا می‌کند. پس از انجامِ به ترتیب جابه‌جایی ها، هر کس باید کتاب متناسب با خودش را داشته باشد(یعنی نفر $i$ ام کتاب موسسه‌ی $i$ ام را داشته باشد). به علت کمبود زمان تعداد جابه‌جایی ها باید کوچکتر مساوی $\frac{3 \cdot n}{2}$ باشد.

ورودی🔗

در خط اول ورودی $n$ تعداد افراد آمده است سپس در خط بعد یک جایگشت از اعداد $1$ تا $n$ به عنوان آرایه ی $a$ آمده است. $1 \leq n \leq 200\ 000$ $1 \leq a_i \leq n$

خروجی🔗

در خط اول خروجی $q$ تعداد جابه‌جایی‌ها بیاید. سپس $q$ خط در هر کدام دو عدد $i$ و $j$ باشد که بیانگر جابه‌جایی کتاب‌های $i$ ام و $j$ ام است.با این شرط که $j-i| \leq \frac{n}{2} + 1$ | و $q$ کوچکتر مساوی $\frac{3 \cdot n}{2}$ باشد.

مثال🔗

ورودی نمونه ۱🔗

4
3 2 1 4

خروجی نمونه ۱🔗

1
3 1

ورودی نمونه ۲🔗

5
5 4 3 2 1

خروجی نمونه ۲🔗

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- رتبه‌ی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند! رتبه‌ی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت! گزارشاتی پنهانی از تقلب‌های حلی سه‌ای ها در کنکور رسیده‌است. متن تقلب‌ها یک رشته است که متاسفانه در دست ما نیست اما از عملیات‌های رمزنگاری آن خبر داریم. هر عملیات رمز نگاری یک حرف را به حرف دیگری تبدیل می‌کند. **لازم به ذکر است که اگر حرفی وجود داشت که به هیچ حرف دیگری تبدیل نشده بود. در رشته هم هیچ تغییری نمی‌کند.** تعداد این عملیات ها $n$‌تا است. ما فقط می‌دانیم متن تقلب‌ها رشته‌ای **یکّه** است. یکّه به این معناست که اگر متن اصلی گزارش برابر رشته‌ی $s$ و متن رمز گشایی شده (که با انجام پشت سر هم عملیات‌ها بدست آمده) برابر رشته‌ی $c$‌باشد. بتوانیم از $c$ با انجام دادن **برعکس** عملیات‌ها به $s$ برسیم. انجام برعکس عملیات‌ها به این معناست که اولاً از عملیات آخر شروع کنیم و تا عملیات اول برویم و دوماً اگر در عملیاتی ما $'a'$ را به $'b'$ تبدیل کردیم در برعکس آن, $'b'$ را به $'a'$ تبدیل خواهیم کرد. برای مثال اگر این دو تبدیل ، تمام عملیات‌های ما باشند: ``` a b b c ``` این دو تبدیل(عملیات) برعکس آن خواهد بود: ``` c b b a ``` برای مثال بالا $"aa"$ یک رشته‌ی یکه به طول دو محسوب می‌شود. زیرا اگر عملیات‌های اصلی روی آن انجام شود حاصل $"cc"$ است و اگر عملیات‌های برعکس روی $"cc"$‌ اعمال شود ما دوباره به همان $"aa"$ می‌رسیم. و $"bb"$ یک رشته‌ی یکه نیست! چون اگر عملیات‌های درست روی آن اعمال شود $"cc"$ حاصل می‌شود و همانطور که گفتیم $"cc"$ در انجام دادن برعکس عملیات‌ها به $"aa"$ ختم می‌شود. می‌خواهیم ببینیم این تقلب‌ها(رشته‌های یکّه) چند حالت مختلف به طول مشخص‌شده دارند؟؟ اما از بد حادثه تعدادی از عملیات‌های پشت سر هم اشتباهاً اضافه شده است. فلذا $q$ پرسش از شما می‌شود به این شکل که برای هر پرسش سه عدد $t, l, r$ داده می‌شود و شما باید باقی مانده تعداد رشته‌های یکه به طول $t$ بر $1e9+7$ را با فرض این که عملیات‌های $l$ تا $r$ حذف شده‌اند چاپ کنید. # ورودی در خط اول ورودی عدد $n$ می‌آید. سپس در $n$ خط بعدی در هر خط یک جفت حرف می‌آید که نشان دهنده عملیات هاست. در خط $n + 2$ ام عدد $q$ می‌آید که تعداد پرسش هاست و در نهایت $q$ خط که هر کدام نشانگر یک پرسش است. $$1 \leq n,q \leq 200\ 000$$ $$1 \leq t \leq 200\ 000$$ $$1\leq l \leq r \leq n$$ تمامی کاراکتر‌های ورودی از حروف لاتین کوچک تشکیل شده‌اند. # خروجی در $q$ خط خروجی به ازای هر پرسش جواب آن را چاپ نمایید. # مثال ## ورودی نمونه ۱ ``` 2 a b b c 3 1 1 2 1 1 1 1 2 2 ``` ## خروجی نمونه ۱ ``` 26 25 25 ``` در اولین پرسش به دلیل وجود نداشتن هیچ عملیاتی می‌توان از هر حرفی استفاده کرد. در دومین پرسش نمی‌توان از $"c"$ به عنوان رشته‌ی ورودی استفاده کرد زیرا بعد از عملیات، همان $"c"$ می‌ماند و اگر مرحله برعکس عملیات را انجام دهیم تبدیل به $"b"$ خواهد شد. در سومین پرسش نیز نمی‌توان از $"b"$ به عنوان رشته‌ی ورودی استفاده کرد. ## ورودی نمونه ۲ ``` 7 c f e f c c e d f b f c f b 4 1 3 5 2 3 5 1 2 6 1 4 4 ``` ## خروجی نمونه ۲ ``` 23 529 24 23 ```

تقلب رمزی

محدودیت زمان: ۲ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

رتبه‌ی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند!

رتبه‌ی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت!

گزارشاتی پنهانی از تقلب‌های حلی سه‌ای ها در کنکور رسیده‌است. متن تقلب‌ها یک رشته است که متاسفانه در دست ما نیست اما از عملیات‌های رمزنگاری آن خبر داریم. هر عملیات رمز نگاری یک حرف را به حرف دیگری تبدیل می‌کند.

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

تعداد این عملیات ها $n$ ‌تا است.

ما فقط می‌دانیم متن تقلب‌ها رشته‌ای یکّه است. یکّه به این معناست که اگر متن اصلی گزارش برابر رشته‌ی $s$ و متن رمز گشایی شده (که با انجام پشت سر هم عملیات‌ها بدست آمده) برابر رشته‌ی $c$ ‌باشد. بتوانیم از $c$ با انجام دادن برعکس عملیات‌ها به $s$ برسیم.

انجام برعکس عملیات‌ها به این معناست که اولاً از عملیات آخر شروع کنیم و تا عملیات اول برویم و دوماً اگر در عملیاتی ما $'a'$ را به $'b'$ تبدیل کردیم در برعکس آن, $'b'$ را به $'a'$ تبدیل خواهیم کرد. برای مثال اگر این دو تبدیل ، تمام عملیات‌های ما باشند:

a b
b c

این دو تبدیل(عملیات) برعکس آن خواهد بود:

c b
b a

برای مثال بالا $"aa"$ یک رشته‌ی یکه به طول دو محسوب می‌شود. زیرا اگر عملیات‌های اصلی روی آن انجام شود حاصل $"cc"$ است و اگر عملیات‌های برعکس روی $"cc"$ ‌ اعمال شود ما دوباره به همان $"aa"$ می‌رسیم. و $"bb"$ یک رشته‌ی یکه نیست! چون اگر عملیات‌های درست روی آن اعمال شود $"cc"$ حاصل می‌شود و همانطور که گفتیم $"cc"$ در انجام دادن برعکس عملیات‌ها به $"aa"$ ختم می‌شود.

می‌خواهیم ببینیم این تقلب‌ها(رشته‌های یکّه) چند حالت مختلف به طول مشخص‌شده دارند؟؟

اما از بد حادثه تعدادی از عملیات‌های پشت سر هم اشتباهاً اضافه شده است. فلذا $q$ پرسش از شما می‌شود به این شکل که برای هر پرسش سه عدد $t, l, r$ داده می‌شود و شما باید باقی مانده تعداد رشته‌های یکه به طول $t$ بر $1e9+7$ را با فرض این که عملیات‌های $l$ تا $r$ حذف شده‌اند چاپ کنید.

ورودی🔗

در خط اول ورودی عدد $n$ می‌آید. سپس در $n$ خط بعدی در هر خط یک جفت حرف می‌آید که نشان دهنده عملیات هاست. در خط $n + 2$ ام عدد $q$ می‌آید که تعداد پرسش هاست و در نهایت $q$ خط که هر کدام نشانگر یک پرسش است.

$1 \leq n,q \leq 200\ 000$

$1 \leq t \leq 200\ 000$

$1\leq l \leq r \leq n$

تمامی کاراکتر‌های ورودی از حروف لاتین کوچک تشکیل شده‌اند.

خروجی🔗

در $q$ خط خروجی به ازای هر پرسش جواب آن را چاپ نمایید.

مثال🔗

ورودی نمونه ۱🔗

خروجی نمونه ۱🔗

26
25
25

در اولین پرسش به دلیل وجود نداشتن هیچ عملیاتی می‌توان از هر حرفی استفاده کرد.

در دومین پرسش نمی‌توان از $"c"$ به عنوان رشته‌ی ورودی استفاده کرد زیرا بعد از عملیات، همان $"c"$ می‌ماند و اگر مرحله برعکس عملیات را انجام دهیم تبدیل به $"b"$ خواهد شد.

در سومین پرسش نیز نمی‌توان از $"b"$ به عنوان رشته‌ی ورودی استفاده کرد.

ورودی نمونه ۲🔗

7
c f
e f
c c
e d
f b
f c
f b
4
1 3 5
2 3 5
1 2 6
1 4 4

خروجی نمونه ۲🔗

+ محدودیت زمان:۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- رتبه‌ی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند! رتبه‌ی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت! تبریک! شما کیک پخش‌کن جلسه‌ی کنکور شده‌اید! باید کاری برای حلی سه‌ای هایِ دوست داشتنی انجام دهید! حلی سه‌ای ها از روش‌های پیشرفته‌ی تقلب استفاده می‌کنند! یکی از این روش‌ها درخت تقلب است! به این صورت که هر نفر به یک راس متناظر می‌شود! از طرف حلی سه‌ای‌ ها(!) از شما خواسته شده که برای تقلب آسان تر کار‌های زیر را بی‌چون و چرا انجام دهید! در ابتدا یک راس به منزله‌ی مقر فرماندهی(با شماره ۱) داریم که از دیشب سر صندلی خود حاضر بوده است. هر بار یکی از این دو کار را انجام می‌دهیم: + `1 p` : طبق برنامه یک حلی سه‌ای وارد می‌شود! اگر قبل از ورود این فرد $k$ فرد سر جلسه حضور داشتند ما شماره‌‌ی $k+1$ را به آن فرد اختصاص می‌دهیم و آن را به راس شماره $p$ وصل می‌کنیم. + `d v 2` : دورترین راس از مقر فرماندهی را که با $v$ حداکثر $d$ یال فاصله دارد را پیدا می‌کنیم و آن را گزارش می‌دهیم! همانطور که معلوم است. گراف همیشه درخت باقی می‌ماند. # ورودی در خط اول ورودی $q$ تعداد کوئری‌ها می‌آید. سپس $q$ خط هر کدام همان طور که شرح داده شد آمده‌اند. $$1 \leq q \leq 200\ 000 $$ $$0 \leq d \leq 1\ 000\ 000\ 000$$ در کوئری‌ها تضمین میشود راس $p$ و $v$ در گراف وجود دارند. # خروجی به ازای هر کوئری نوع دو، جواب آن را چاپ کنید. اگر چند جواب درست وجود داشت یکی از آن‌ها را به دلخواه چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 1 1 1 1 2 2 10 1 3 2 2 10 ``` ## خروجی نمونه ۱ ``` 2 4 ``` ## ورودی نمونه ۲ ``` 9 1 1 1 1 1 2 2 3 3 1 4 2 3 4 1 4 1 6 2 4 2 ``` ## خروجی نمونه ۲ ``` 4 5 7 ```

درخت تقلب

محدودیت زمان:۲ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

رتبه‌ی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند!

رتبه‌ی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت!

تبریک! شما کیک پخش‌کن جلسه‌ی کنکور شده‌اید! باید کاری برای حلی سه‌ای هایِ دوست داشتنی انجام دهید! حلی سه‌ای ها از روش‌های پیشرفته‌ی تقلب استفاده می‌کنند! یکی از این روش‌ها درخت تقلب است! به این صورت که هر نفر به یک راس متناظر می‌شود!

از طرف حلی سه‌ای‌ ها(!) از شما خواسته شده که برای تقلب آسان تر کار‌های زیر را بی‌چون و چرا انجام دهید!

در ابتدا یک راس به منزله‌ی مقر فرماندهی(با شماره ۱) داریم که از دیشب سر صندلی خود حاضر بوده است. هر بار یکی از این دو کار را انجام می‌دهیم:

1 p : طبق برنامه یک حلی سه‌ای وارد می‌شود! اگر قبل از ورود این فرد $k$ فرد سر جلسه حضور داشتند ما شماره‌‌ی $k+1$ را به آن فرد اختصاص می‌دهیم و آن را به راس شماره $p$ وصل می‌کنیم.
d v 2 : دورترین راس از مقر فرماندهی را که با $v$ حداکثر $d$ یال فاصله دارد را پیدا می‌کنیم و آن را گزارش می‌دهیم!

همانطور که معلوم است. گراف همیشه درخت باقی می‌ماند.

ورودی🔗

در خط اول ورودی $q$ تعداد کوئری‌ها می‌آید. سپس $q$ خط هر کدام همان طور که شرح داده شد آمده‌اند. $1 \leq q \leq 200\ 000$ $0 \leq d \leq 1\ 000\ 000\ 000$ در کوئری‌ها تضمین میشود راس $p$ و $v$ در گراف وجود دارند.

خروجی🔗

به ازای هر کوئری نوع دو، جواب آن را چاپ کنید.

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

مثال🔗

ورودی نمونه ۱🔗

خروجی نمونه ۱🔗

2
4

ورودی نمونه ۲🔗

خروجی نمونه ۲🔗

4
5
7