Fişierul intrare/ieşire:	shopping.in, shopping.out	Sursă	Junior Challenge 2020
Autor	Alexa Tudose	Adăugată de	Comisia •JuniorChallenge2020
Timp execuţie pe test	0.2 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Shopping

Kokalaru47 a intrat într-o nouă încurcătură! Prietenul său, Marele Anonim, şi-a cumpărat de curând o permutare p de o frumuseţe nemaiauzită. Curios din fire, Kokalaru47 vrea să afle permutarea, însă Marele Anonim i-a zis doar că are lungimea N şi a decis să nu dezvăluie în mod direct alte informaţii. În schimb, îi va răspunde la mai multe întrebări.

Într-o întrebare, Kokalaru47 îi dă Marelui Anonim două stringuri A şi B de lungime N. Marele Anonim creează apoi alte două stringuri C = A_p1A_p2A_p3...A_pN şi D = B_p1B_p2B_p3...B_pN. În final, Marele Anonim răspunde la întrebare cu lungimea prefixului maximal comun dintre C şi D în care există cel mult o nepotrivire.

Înainte de a-i pune Marelui Anonim o întrebare, Kokalaru47 trebuie să cumpere ingredientele pentru întrebarea respectivă. El merge, aşadar, la Magazinul de Stringuri şi achizitionează 2N litere mici ale alfabetului englez (N pentru stringul A şi N pentru stringul B). Se ştie că litera care apare pe pozitia c în alfabet costă c-1 parai. De asemenea, ingredientele folosite la o întrebare nu pot fi refolosite la o altă întrebare ulterioară.

Cerinţă

Ajutaţi-l pe Kokalaru47 să afle permutarea misterioasă fară să-şi depăşească bugetul de P parai.

Interacţiune

Prima dată se va citi valoarea T, ce reprezintă numărul testelor ce trebuie rezolvate. Pentru fiecare test, se va citi apoi N, reprezentând lungimea permutării căutate.

Programul vostru poate pune apoi întrebări sub forma "? A B", unde A si B sunt stringuri de lungime N. Aceste intrebari vor fi scrise in stdout. Răspunsul la o întrebare va putea fi citit din stdin.

Când aţi găsit permutarea căutată, afişaţi "! p₁p₂p₃...p_N

Restricţii

• ... ≤ ... ≤ ...

Exemplu

Explicaţie

...

Cum se trimit solutii?