Laiko ribojimas: 1s

Atminties ribojimas: 32MB

Duomenų failas: kvkripto.in

Rezultatų failas: kvkripto.out

Jei norite pateikti savo sprendimą - prisijunkite.

Kvadratinis kodas

Linas ir Martynas yra labai gerai draugai. Būdami gerais draugais, jie dažnai susirašinėja laiškais. Siekdami, kad jų pokalbio niekas nenugirstų, jie sumanė visus laiškus užkoduoti. Laiško dekodavimas vyksta labai paprastu būdu:

  • Iš matematikos sąsiuvinio iškerpamas kvadratas M, turintis N^2 mažesnių kvadratėlių (tokį patį kvadratą turi ir kodavęs žmogus);
  • Šiame kvadrate iškerpamos \\frac{N^2}{4} skylutės;
  • Šis kvadratas padedamas ant užkoduotos žinutės;
  • Per skylutes matomos raidės užrašomos prie dekoduoto teksto (skylučių turinys skaitomas nuo viršau į apačią iš kairės į dešinę);
  • Kvadratas M pasukamas 90 laipsniu kampu pagal laikrodžio rodyklę;
  • Skaitymo procesas kartojamas dar 3 kartus;
  • Iš galutinio rezultato pašalinami visi pertekliniai tarpai.

Tad, pavyzdžiui, jeigu užkoduotas tekstas atrodo taip (taškais žymimi tarpai):

o.do
.ng.
grmn
o.i.

O iškirptasis kvadratas yra (* žymi skylutes):

.*..
*.*.
....
*...

Taip priklausomai nuo pradinės kvadrato M padėties galima dekoduoti keturis skirtingus tekstus:

  • od morning go
  • orning good m
  • ng good morni
  • good morning

Iš šių tekstų dekoduotojas išsirenka tą, kuris yra labiausiai panašus į įskaitoma tekstą, t.y. "good morning". Įskaitomu tekstu laikomas tas, kurio visi žodžiai yra žinomi Linui ir Martynui. Esant keliems geriems tekstams, iš jų geriausiu išrenkamas tas, kuris yra leksikografiškai mažesnis. Šis lyginimas vyksta imant dviejų žinučių žodžius lygiagrečiai ir ieškant pirmos žodžių poros, kurios elementai skirtingi. Šių skirtingų žodžių leksikografinė tvarka nurodys pačių žinučių tvarką.

Neseniai Linas gavo nauja žinutę iš Martyno ir nori ją kiek įmanoma greičiau dekoduoti. Kadangi jis nenori perrinkinėti visų variantų, jis kreipėsi į jus pagalbos :)

Pradiniai duomenys

Pirmoje pradinių duomenų eilutėje bus nurodytas skaičius T (1\\leqT\\leq100), nurodantis testų kiekį. Kiekvieną testą sudarys skaičius N (N\\vdots2,2\\leqN\\leq50). Kitose eilutėse bus pateikti du kvadratai, sudaryti iš N eilučių ir N simbolių. Pirmasis kvadratas bus kodas, o antrasis M. Galiausiai testas bus pabaigtas skaičiumi Q (1\\leqQ\\leq100), po kurio bus nurodyti visi Linui ir Martynui žinomi žodžiai (kiekvienas žodis bus nurodytas atskiroje eilutėje ir nei vieno žodžio ilgis neviršys 20).

Rezultatai

Kiekvienam testui reikės išvesti po eilutę pavidalo "Case #t: r", kur t yra testo numeris (nuo 1 iki T), o r atkoduotas pranešimas (arba simbolį "-", jei pranešimo atkoduoti neįmanoma).

Pavyzdžiai

Pradiniai duomenys Rezultatai 
1
4
o.do
.ng.
grmn
o.i.
.*..
*.*.
....
*...
2
good
morning
 
Case #1: good morning