- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
رادزینکا دوبرامیل ویچشسلافوویچ (Rodzyanko Dobromil Vyacheslavovich) که یک فرد تنبل طماع است، باید شیر بخرد. رادزینکا را صبح مادرش بیدار کرد به مزرعه فرستاد تا برای صبحانه شیر تازه بیاورد. اما او چون تنبل است به فروشگاه رفته و در حال خرید شیر پاکتی است. در کنار فروشگاه یک نانوایی بوده و صف آن نیز بسیار بلند است به طوری که $10^9$ نفر در صف آن قرار دارند. متاسفانه مغازه‌دار در فروشگاه شیر پاکتی نداشت و به انبار رفت تا بیاورد. برای همین رادزینکا باید مدتی منتظر بماند و از روی بیکاری جایگاه هر شخصی را در صف نانوایی یادداشت کرد.
از آنجایی که صف نانوایی طولانی است و بعضی از افراد مثل رادزینکا پیرژامه مامان‌دوز پوشیده‌اند و خیابان پر از آدم است، بعضی از افراد تصمیم می‌گیرند که تا آبرویشان نرفته، به خانه بروند و لباس مناسب پوشیده و به صف برگردند. برای همین تمام افرادی که پشت این آدم‌ها بودند، یک عدد به جلو آمده و جایگاهشان یک عدد کمتر می‌شود. متاسفانه زمانی که این افراد به صف برمی‌گردند، جای قبلیشان یادشان نیامده و به یک جای جدید در صف می‌روند. در ضمن تا وقتی که نفر قبلی که به خانه رفته، به صف برنگردد، نفر جدیدی از صف خارج نمی‌شود. در همین حین، رادزینکا تمام جابه‌جایی‌ها را یادداشت می‌کند؛ یعنی به ازای هر شخصی که از صف خارج شده و به آن برمی‌گردد، برایش یادداشت می‌کند که زمانی که رادزینکا وارد فروشگاه شد در چه جایگاهی بود و موقع بازگشت جلوی نفر چندم صف قرار گرفت. فقط دقت کنید که بعضی از افراد امکان دارد که چندبار به خانه رفته و برگردند چرا که کندذهن اند و وقتی به خانه می‌روند یادشان می‌رود که لباسشان را عوض کنند و فکر می‌کنند که آمده‌اند خانه تا آب بخورند. برای همین دوباره با همان پیرژامه مامان‌دوز به صف برمی‌گردند.
متاسفانه رادزینکا گیج شده‌است. (قبلا گیج نبود) او الان می‌خواهد یک سری اطلاعات به دست بیاورد و برای این کار از شما کمک گرفته‌است. او تمام اطلاعاتی را که از جابه‌جایی‌ها یادداشت کرده به شما می‌دهد و از شما دو نوع اطلاعات می‌خواهد:
در نوع اول او از شما می‌خواهد که به او بگویید که شخصی که الان در جایگاه $x$ از صف قرار دارد، هنگام ورود رادزینکا به فروشگاه در کدام جایگاه قرار داشته است.
در نوع دوم او از شما می‌خواهد که به او بگویید که شخصی که در زمان ورود رادزینکا به فروشگاه در جایگاه $x$ قرار داشت، الان در چه جایگاهی از صف قرار دارد.
ورودی
در سطر اول ورودی $q$ آمده است که نمایانگر تعداد جابه‌جایی‌ها است. سپس در هر خط توصیف یک جابه‌جایی آمده است:
هر جابه‌جایی شامل دو عدد $z$ و $y$ است. عدد اول نمایانگر این است که شخصی که در زمان ورود رادزینکا به فروشگاه از صف خارج شده، قبل از خارج شدن و عدد دوم نمایانگر جایگاه شخصی است که شخص از صف خارج شده بعد از بازگشت از خانه به جلوی او رفته است. جابه‌جایی‌ها به ترتیب زمانی آمده است.
سپس درس سطر بعدی یک عدد $n$ آمده است که نمایانگر تعداد درخواست‌های رادزینکا از شما است. سپس در هر خط توصیف یک درخواست آمده است: ابتدا یک حرف انگلیسی می‌آید که نشان می‌دهد که درخواست رادزینکا از نوع اول است یا دوم. حرف $L$ نمایانگر درخواست نوع اول و حرف $P$ نمایانگر درخواست از نوع دوم است. سپس $x$ آمده است که توضیحات این ورودی در قسمت توضیحات انواع درخواست آمده است. $$ 1\le q,n \le 50\ 000 $$ $$ 1 \le x,z,y \le 1\ 000\ 000\ 000 $$
خروجی
خروجی باید شامل $n$ خط باشد که در خط i، باید جواب درخواست i آمده باشد.
مثال
ورودی نمونه ۱
2
6 3
9 6
8
L 1
L 2
L 3
L 4
P 1
P 2
P 3
P 4
خروجی نمونه ۱
1
2
9
6
1
2
5
6
ورودی نمونه ۲
5
7 2
2 7
9 7
10
1 100005
99995 9
L 1
P 2
L 2
P 7
L 7
P 9
P 10
P 99999
L 100000
خروجی نمونه ۲
10
3
1
5
4
4
1
100000
99999
ارسال پاسخ برای این سؤال