Програмчлалын олимпиадын бодлогын архив

2008 оны Бээжингийн олимпын билетийг олж авахад маш хэцүү болжээ. Зохион байгуулагчид бүх тасалбарыг ивээн тэтгэгчид, найз нөхөд болон ар гэрийнхэндээ тарааж орхижээ. Иймд ихэнх хүмүүс олимпыг зурагтаараа үзэхээс өөр аргагүй болсон байна.
Медалийн төлөөх тоглолтын цөөн хэдэн тасалбар үлдсэн байсан ба үүнээс болж кассны үүдэнд урт дараалал үүссэн.
Хөгжөөн дэмжигчдийг ирсэн дарааллаар нь бүхэл тоогоор дугаарласан. Эхний хүн нэг гэсэн дугаартай, дараагийн хүн хоёр гэсэн дугаартай гэх мэт.
Хөгжөөн дэмжигчид өмнөх өдрийн шөнөөс эхлэн дараалалд зогссон тул тэнд байсан ганц ариун цэврийн өрөөг хэрэглэж байсан. Ариун цэврийн өрөөнөөс ирсэн хүн буцаад яг байсан байрандаа орох албагүй. Мөн дарааллаас хамгийн ихдээ ганц хүн л байхгүй байж болно(ариун цэврийн өрөө явсан).
Тэр шөнийн турш N ширхэг хүн ариун цэврийн өрөөг хэрэглэсэн байна. Энэ тохиол бүрийг A, B бүхэл тоонуудаар дараах байдлаар илэрхийлнэ: А дугаартай хүн дарааллаас түр гарч, буцаж ирэхдээ В дугаартай хүний урд зогссон. Өглөө нь тасалбар борлуулах ажлын хүрээнд дараах хоёр төрлийн асуултууд тавигдсан: "P X" - Х дугаартай хүн аль байрлалд байгааг олох, "L X" - X дугаартай байрлалд ямар дугаартай хүн байгааг олох.
Дарааллын эхэнд байгаа хүн 1-р байрлалд, түүний дараа байгаа хүн 2-р байрлалд байгаа гэх мэтээр байрлалыг дугаарлана.
Ариун цэврийн өрөөг хэрэглэсэн тухай мэдээллийг ашиглан өгөгдсөн асуултуудад хариулах програм бич.

Input

Эхний мөрөнд ариун цэврийн өрөөг хэрэглэсэн ний тоо болох N бүхэл тоо өгөгдөнө(2 ≤ N ≤ 50 000).
Дараагийн N ширхэг мөрөнд ариун цэврийн өрөөг хэрэглэсэн тохиолдол бүрийн тухай мэдээлэл A, B хоёр бүхэл тоо хэлбэрээр өгөгдөнө (1 ≤ A, B ≤ 10⁹).
Дараагийн мөрөнд асуултуудын ний тоо болох Q бүхэл тоо байрлана (1 ≤ Q ≤ 50 000).
Дараагийн Q ширхэг мөрөнд асуулт бүр зайгаар тусгаарлагдсан нэг тэмдэгт (том "P" үсэг эсвэл том "L" үсэг) болон нэг бүхэл тоо хэлбэрээр өгөгдөнө(1 ≤ X ≤ 10⁹).

Output

Гаралт нь нийт Q ширхэг мөрнөөс тогтно. i-р мөрөнд i-р асуултын хариулт болох R бүхэл тоо байрлана.
Хэрэв харгалзах асуулт нь "P X_i" хэлбэртэй байсан бол R нь Х_i дугаартай хүний эцсийн байрлал байна.
Хэрэв харгалзах асуулт нь "L X_i" хэлбэртэй байсан бол R нь Х_i-р байрлалд байгаа хүний дугаар байна.

Example

Input:

2
6 3
9 6
8
L 1
L 2
L 3
L 4
P 1
P 2
P 3
P 4

Output:

1
2
9
6
1
2
5
6

Input

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

Output

10
3
1
5
4
4
1
100000
99999