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

دیشب پس از قهرمانی تیم $1$ در مسابقات آسیایی کبدی یک فاجعه‌ی باور نکردنی رخ داد! صبح امروز کشف شد نوشته زیر جام مسابقات که نام قهرمان مسابقات بر روی آن ثبت می شود، تغییر کرده است. پلیس قبل از رسانه‌ای شدن موضوع تمام مظنونین به ارتکاب این دسیسه را دستگیر کرد و مورد بازجویی قرار داد. در طول بازجویی از مظنونی که به حضور در موزه‌ی نگه‌داری جام در لحظه‌ی $t$ اعتراف کرده بود، این جمله شنیده شد: «تیم $a$ صدبار شرف داره به تیم $b$!» کارآگاهان خبره از این جمله چنین برداشت کردند که در لحظه‌ی حضور مظنون در موزه، در صورتی که نام قهرمان $a$ ثبت شده باشد، مظنون آن را به $b$ تغییر داده است.

همچنین کارآگاهان در طول بررسی‌ها به بعضی اطلاعات تکمیلی نیاز دارند. آن‌ها می‌خواهند بدانند با توجه با اعترافات فعلی، نام قهرمان در لحظه‌ی $t$ چه چیزی بوده است؟

شما $q$ پرسمان در پیش رو دارید. هر کدام یا نتیجه‌ی یک بازجویی است که در اختیار شما قرار می‌گیرد، و یا یک پرسش است که شما باید به آن پاسخ بدهید.

ورودی

در سطر اول ورودی عدد طبیعی $q$، تعداد پرسمان‌ها آمده است.

در هریک از $q$ سطر بعد، نتیجه‌ی یک بازجویی به شکل ‍‍‍‍t a b ~ و یا یک پرسش به شکل t ? آمده‌است. تمام زمان‌های آمده در ورودی متمایزند.

دقت کنید در ابتدا نام تیم $1$ زیر جام نوشته شده‌ است.

$$1\le q \le 200\ 000$$

$$1\le t \le 10^9$$

$$1\le a, b \le 200\ 000$$

خروجی

برای هر پرسش، جواب را در سطری جداگانه چاپ کنید.

زیرمسئله‌ها

مثال

ورودی نمونه

7
? 10
~ 5 2 3
? 8
~ 1 1 2
? 11
~ 3 2 4
? 6

خروجی نمونه

1
1
3
4

۲۴امین دوره‌ المپیاد کامپیوتر - آزمون چهارم - ۱۳۹۳/۰۶/۱۲