Questo è un problema interattivo.

Il gioco "L'idraulico Mariusz" (Plumber Mariusz) è composto da $n + 1$ livelli (numerati da 0 a $n$), ciascuno dei quali ha $k$ versioni (numerate da 0 a $k - 1$). Ogni versione di ogni livello (tranne l'ultimo) termina con due tubi — il sinistro e il destro — e Mariusz deve saltare in uno di essi. Ogni tubo contiene un certo numero di monete e conduce a una delle versioni del livello successivo. Esattamente due tubi conducono a ciascuna versione di ciascun livello (tranne il livello zero); questi possono essere due qualsiasi tra i $2 \cdot k$ tubi che escono da tutte le $k$ versioni del livello precedente.

Una singola partita consiste nello scegliere una versione del livello zero e poi nello scegliere il tubo sinistro o destro $n$ volte, e il risultato della partita è il numero totale di monete raccolte negli $n$ tubi visitati. Non veniamo a sapere quante monete ci fossero in ciascun tubo né quali versioni dei livelli siano state visitate. Le monete nei tubi vengono sempre ripristinate ai loro valori iniziali, quindi tutte le partite sono indipendenti. Una partita può pertanto essere rappresentata dalla funzione:

int rozgrywka(int ver, string s), dove $\text{ver} \in [0, k - 1]$ e $s$ è una stringa di $n$ lettere L e P.

Nota che L e P corrispondono rispettivamente alle parole polacche per sinistra e destra.

Puoi effettuare fino a $300\,000$ partite di prova e conoscerne i risultati. Dopodiché riceverai fino a $10\,000$ query riguardanti delle partite. Il tuo compito è determinarne i risultati.

Ogni test è fissato prima che inizi l'interazione (cioè l'interattore non è adattivo). Un test contiene un grafo orientato pesato con $(n + 1) \cdot k$ vertici disposti in $n + 1$ strati (livelli), e $q$ query $(\text{ver}, s)$. Ogni vertice (tranne quelli nell'ultimo strato) ha due archi uscenti (sinistro e destro), ciascuno descritto da un numero di monete $c \in [1, 10^8]$ e da una versione $v \in [0, k - 1]$ a cui conduce. Ricorda che ogni vertice tranne quelli nello strato zero ha grado entrante esattamente pari a 2.

Svuotamento del buffer (Buffer flushing)

Dopo aver stampato ciascuna riga devi svuotare il buffer di output (flush), in modo che l'interattore riceva la riga di output. Ad esempio, in C++ puoi stampare una riga contenente un punto esclamativo usando cout << "!" << endl; oppure usando printf("!\n"); fflush(stdout);. In Python puoi usare print("!", flush=True). Non garantiamo un comportamento stabile dell'interattore se stampi più righe senza svuotare il buffer dopo ciascuna di esse, o se stampi molte righe senza leggere le risposte dell'interattore. Il tuo programma non può aprire alcun file.

Protocollo di interazione

L'intero flusso di comunicazione è descritto di seguito:

• Leggi la prima riga contenente due interi $n$ e $k$ ($1 \le n, k \le 20$) — ci sono $n + 1$ livelli, ciascuno con $k$ versioni.
• Fino a $300\,000$ volte, effettua una partita di prova:
  • Stampa una riga della forma ? ver s (senza virgolette), dove $\text{ver} \in [0, k - 1]$ e $s$ è una stringa di $n$ lettere L e P. Flush.
  • Leggi la riga successiva contenente il risultato della partita — un intero $x$ ($n \le x \le n \cdot 10^8 \le 2 \cdot 10^9$).
• Stampa una riga contenente un singolo carattere ! (punto esclamativo). Flush.
• Leggi la riga successiva contenente un intero $q$ ($1 \le q \le 10\,000$) — il numero di query.
• Per ciascuna delle $q$ query:
  • Leggi la riga successiva contenente un intero $\text{ver}$ e una stringa $s$ (stessi limiti di cui sopra).
  • Stampa una riga contenente il risultato della partita (un intero). Flush.

L'illustrazione mostra il primo test di esempio ($n = 2; k = 4$). Due query finali sono indicate con linee tratteggiate: rozgrywka(0, "LL") $= 20 + 3 = 23$ e rozgrywka(1, "PL") $= 9 + 10 = 19$.

Esempio

Ecco un esempio di flusso di comunicazione:

Note

Nell'allegato (scaricabile nella scheda "attachment" su QOJ) troverai delle soluzioni di esempio (errate) G.cpp e G.py che eseguono correttamente la comunicazione, ma calcolano i risultati in modo errato. La directory include inoltre: un correttore di esempio Gsoc.cpp e dei test di esempio (G0a.in, G0b.in, G0c.in, e un grande test casuale G0d.in con $n = k = 20$). Il formato dei file di test è descritto nel commento all'inizio di Gsoc.cpp.

Il correttore di esempio Gsoc.cpp differisce da quello utilizzato su QOJ. Potrebbe non validare l'input o gli argomenti della funzione di partita.

Puoi eseguire la tua soluzione usando lo script run.sh. Il comando accetta il programma compilato e il nome del file di test. Ad esempio, per eseguire i programmi di esempio sul test di esempio G0a.in:

• C++: g++ G.cpp -o G.e && ./run.sh "./G.e" G0a.in
• Python: ./run.sh "python3 G.py" G0a.in