16349번 - Ghost leg 다국어

Ghost leg odnosno Amidakuji je drevna japanska metoda provedbe lutrije u kojoj svaki od n igrača dobiva jednu od n nagrada. Ploča za igru se sastoji of n vertikalnih linija označenih brojevima od 1 do n slijeva nadesno. Također, na ploči se inicijalno nalazi m horizontalnih prečkica. Prečke se nalaze na različitim visinama te su označene brojevima od 1 do m odozgo prema dolje. Svaka prečka povezuje dvije susjedne vertikalne linije — prečka j povezuje linije p_j i p_j + 1. (Pogledajte sliku kod donjeg primjera.)

Na vrhu vertikalne linije j se nalazi igrač broj j, a na njenom dnu nagrada broj j. Nagrada koju dobiva igrač j se odreduje na sljedeći način: krenemo od vrha linije j te se po njoj spuštamo, kada naiđemo na neku prečku obavezno prolazimo po njoj do susjedne linije te nastavljamo spuštanje. Nagrada igrača je oznaka linije na kojoj završava opisani put.

Zadana je ploča za igru te q događaja — svaki događaj je jedan od sljedećih:

• “A i”, gdje je i cijeli broj i vrijedi 1 ≤ i ≤ m — s ploče se uklanja prečka i.
• “B j”, gdje je j cijeli broj i vrijedi 1 ≤ j ≤ n — zanima nas koju nagradu trenutno dobiva igrač j.

Pronađite odgovore na sve događaje tipa B.

U prvom redu se nalaze prirodni brojevi n i m (2 ≤ n ≤ 1 000 000, 1 ≤ m ≤ 1 000 000) — broj igrača i broj prečki. U sljedećem redu nalazi se m prirodnih brojeva p₁, p₂, . . . , p_m (1 ≤ p_i ≤ n − 1) koji označavaju pozicije prečki kako je opisano u tekstu zadatka.

U sljedećem redu se nalazi broj q (1 ≤ q ≤ 1 000 000) — broj događaja. U k-tom od sljedećih q redova se nalazi opis k-tog događaja. Opis svakog događaja je oblika “A i” ili “B j” kako je opisano u tekstu zadatka. Ista prečka neće biti uklonjena više puta, a barem jedan događaj će biti tipa B.

U j-ti red ispišite odgovor na j-ti po redu događaj tipa B.

Slika prikazuje inicijalnu ploču. Igrač broj 1 će proći po prečki broj 2 pa zatim po prečki broj 5 i dobiti nagradu broj 3.