- محدودیت زمان: ۳ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ابوالفضل یک قاب مربعی خیلی خیلی بزرگ بر روی کاغذ دارد. رومینا در هر مرحله نخی محکم را از نقطهای از ضلع سمت چپ به نقطهای در ضلع پایینی قاب وصل می‌کند. در این میان ممکن است در بعضی از مراحل ابوالفضل گلوله‌ای را از بخشی از ضلع چپ رها کند و قاب را با کاغذ پشت آن به صورت ایستاده درآورد.
در این حالت جاذبه گلوله را به سمت پایین می‌کشد و هر جا روی نخی قرار بگیرد، روی آن سر می‌خورد. ممکن است در حین سر خوردن به نخ دیگری گیر کند و به بن‌بست برسد، در این صورت همانجا می‌ماند. در غیر این صورت آنقدر می‌رود تا به ضلع پایینی قاب برسد. می‌خواهیم قبل از متوقف شدن گلوله، به ما بگویید که آیا گلوله به ضلع پایینی می‌رسد یا خیر. همچنین اگر جواب بله است، در کدام نقطه متوقف می‌شود. به نمونه‌های ورودی برای فهم بهتر سر خوردن توجه کنید.
ورودی
در خط اول ورودی عدد طبیعی $q$ می‌آید. سپس پس در هر یک از $q$ خط بعدی، در هر خط یکی از دو نوع پرسمان زیر می‌آید.
-
1 y x: در نوع یک، رومینا یک نخ از نقطهای با فاصله $y$ از گوشه پایین چپ قاب، در ضلع سمت چپ به نقطه‌ی با فاصله $x$ از گوشه پایین چپ قاب، در ضلع پایین اضافه می‌کند. تضمین می‌شود در این دو نقطه قبلا هیچ نخی وصل نشده بوده است. -
2 y: در نوع دوم، ابوالفضل گلوله را از نقطهای با فاصله $y$ از گوشه پایین چپ قابل، در ضلع سمت چپ رها می‌کند. تضمین می‌شود هیچ نخی از این نقطه وصل نشده است.
$$ 1 \leq q \leq 10^6 $$ $$ 1 \leq x, y \leq 10^9 $$
خروجی
به ازای تمام عملیات‌های نوع دوم، در صورتی که گلوله به ضلع پایینی می‌رسد بگویید به کدام نقطه از ضلع پایینی می‌رسد و اگر بین دو نخ گیر می‌کند، -1 را چاپ کنید.
مثال‌ها
ورودی نمونه ۱
5
1 4 1
1 2 3
2 1
2 3
2 5
خروجی نمونه ۱
0
-1
3
در شکل زیر، مسیر توپ‌ها نشان داده شده است.
ورودی نمونه ۲
9
2 6
1 7 5
2 6
1 4 4
2 6
1 1 6
2 6
1 2 9
2 6
خروجی نمونه ۲
0
0
4
-1
-1
ارسال پاسخ برای این سؤال