U laboratoriji se generiše lanac DNK nad alfabetom {A, C, G, T}. Nad trenutnim lancom X primenjuje se n operacija. Postoje dve operacije:

• K — operacija kopije: X^′ ← X ∘ X
• C — operacija komplementa: X^′ ← X ∘ comp(X)

Ovde je comp(⋅) komplementiranje po standardnim parovima: A ↔︎ T, C ↔︎ G, a operator ∘ označava nadovezivanje nizova.

Za početni lanac s i n operacija odrediti koji se nukleotid nalazi na k-toj poziciji nakon što su sve operacije primenjene. Pozicije se broje od 0.

Ulaz

Sa standardnog ulaza učitava se broj operacija n (1 ≤ n ≤ 60), tražena pozicija k (0 ≤ k < |s|⋅2ⁿ ≤ 10⁹), i početni DNK lanac s (1 ≤ |s| ≤ 2 ⋅ 10⁵), karakteri su iz skupa {A, C, G, T}).

U sledećem redu nalazi se n operacija, karaktera razdvojenih razmacima, K ili C.

Izlaz

Ispisati jedan karakter iz skupa {A, C, G, T} — sadržaj na k-toj poziciji nakon svih operacija.

Primer

Ulaz

3 13 AT
K C K

Izlaz

A

Objašnjenje

Kada primenimo, redom, operacije K, C i K na dnk lanac AT dobijamo lanac ATATTATAATATTATA.

Primer

Ulaz

2 9 CGA
C C

Izlaz

C

Objašnjenje

Kada primenimo operaciju C dva puta na dnk lanac CGA, dobijamo lanac CGAGCTGCTCGA.