La camera dei cestini

Per aiutarti con questo task, abbiamo preparato delle tracce di soluzione, che includono solo le parti di lettura dell'input e scrittura dell'output (da tastiera e su schermo). Puoi decidere se leggere/scrivere su file decommentando le opportune righe di codice.

• Scarica la traccia in C: cestini.c
• Scarica la traccia in C++: cestini.cpp
• Scarica la traccia in C#: cestini.cs
• Scarica la traccia in Go: cestini.go
• Scarica la traccia in JavaScript: cestini.html
• Scarica la traccia in Java: cestini.java
• Scarica la traccia in Pascal: cestini.pas
• Scarica la traccia in Python: cestini.py
• Scarica la traccia in VisualBasic: cestini.vb

Descrizione del problema

Tommaso ha $N$ oggetti e $M$ cestini in camera. Ogni oggetto è rappresentato da una lettera dell'alfabeto maiuscola, da $\texttt{A}$ a $\texttt{Z}$. I cestini sono numerati da $0$ a $M - 1$. Ogni cestino ha una capacità illimitata e vi è un ordine fra gli elementi al suo interno: l'elemento in posizione $0$ è sul fondo, quello in posizione $1$ si trova subito sopra, e così via.

Inizialmente, tutti gli oggetti si trovano in ordine nel cestino $0$, e il loro ordine è dato da una stringa $S$ di lunghezza $N$. Il primo carattere di $S$ rappresenta l'oggetto in posizione $0$, e così via. Tuttavia, quando è annoiato, Tommaso passa il tempo spostando gli oggetti fra i cestini! In particolare, sposta l'oggetto dalla cima di un cestino alla cima di un altro cestino.

Aiuta Tommaso a tenere traccia degli oggetti nella sua camera, stando sempre pronto a dirgli qual è l'oggetto in una certa posizione di un certo cestino, gestendo i suoi $Q$ spostamenti e domande.

Dati di input

La prima riga del file di input contiene un intero $T$, il numero di casi di test. Seguono $T$ casi di test, numerati da $1$ a $T$. Ogni caso di test è preceduto da una riga vuota.

Ogni caso di test è composto come segue:

• la prima riga contiene gli interi $N$, $M$ e $Q$;
• la seconda riga contiene la stringa $S$;
• le $Q$ righe successive contengono la descrizione di uno spostamento o di un controllo:
  • s $a$ $b$ indica uno spostamento: l'oggetto in cima al cestino $a$ è stato spostato in cima al cestino $b$ (è garantito che il cestino $a$ contiene almeno un oggetto al momento dello spostamento);
  • c $a$ $b$ indica un controllo: Tommaso vuole sapere qual è il $b$-esimo oggetto dal fondo nel cestino $a$ (è garantito che il cestino $a$ contiene almeno $b + 1$ oggetti al momento del controllo).

Dati di output

Il file di output deve contenere la risposta ai casi di test che sei riuscito a risolvere. Per ogni caso di test che hai risolto, il file di output deve contenere una riga con la dicitura:

Case #t: ans ...

dove t è il numero del caso di test (a partire da $1$) e ans è una stringa che rappresenta le risposte ai controlli di Tommaso. L'$i$-esimo carattere della stringa è una lettera maiuscola che rappresenta la risposta all'$i$-esimo controllo.

Assunzioni

• $T = 10$, nei file di input che scaricherai saranno presenti esattamente $10$ casi di test.
• $2 \le N \le 300\,000$.
• $2 \le M \le 500\,000$.
• $1 \le Q \le 300\,000$.
• La stringa $S$ ha lunghezza $N$ ed è costituita da lettere maiuscole dell'alfabeto inglese.
• $0 \le a, \, b < M$, $a \neq b$ per ogni spostamento.
• Per ogni spostamento, c'è almeno un oggetto nel cestino $a$.
• $0 \le a < M$, $0 \le b < N$ per ogni controllo.
• Per ogni controllo, il cestino $a$ contiene almeno $b + 1$ oggetti.

Esempi di input/output

---

Input:

2

3 3 2
ABC
s 0 1
c 1 0

4 3 6
BCBA
s 0 1
c 1 0
s 0 2
s 1 2
c 2 1
c 0 0

---

Output:

Case #1: C
Case #2: AAB

---

Spiegazione

Nel primo caso di esempio, l'oggetto $\texttt{C}$, in cima al cestino $0$, viene spostato in cima al cestino $1$.

Nel secondo caso di esempio:

• l'oggetto $\texttt{A}$ viene spostato dal cestino $0$ al cestino $1$;

• uno degli oggetti $\texttt{B}$ viene spostato dal cestino $0$ al cestino $2$;
• l'oggetto $\texttt{A}$ viene spostato dal cestino $1$ al cestino $2$.