Fişierul intrare/ieşire:	seif.in, seif.out	Sursă	Stelele Informaticii 2007-2008, Clasele 11-12
Autor	Andrei Grigorean	Adăugată de	Adrian Diaconu •DITzoneC
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Seif

Miruna a ajuns intr-o mare incurcatura. Deoarece urma sa aiba examen la algoritmi si structuri de date, s-a hotarat sa dea o spargere in apartamentul profesorului sau pentru a pune mana pe subiecte. La inceput s-a descurcat bine, insa acum se afla in fata seifului ce pastreaza mult ravnitele subiecte de examen. Pentru a trece de acest ultim obstacol, Miruna trebuie sa introduca un cod secret. Ea a aflat din surse sigure ca acest cod are lungimea mai mare sau egala decat un numar K. Deasemenea, a mai facut rost din biroul profesorului de 2 siruri de litere mari ale alfabetului de lungimi N si M. Miruna banuieste ca parola secreta ce deschide seiful este un subsir comun al celor 2 siruri, cat mai mare lexicografic.

Cerinta

Stiind cele 2 siruri si numarul K, aflati subsirul comun de lungime mai mare sau egala cu K cat mai mare lexicografic.

Date de intrare

Pe prima linie a fisierului de intrare seif.in se gaseste un numar intreg T, reprezentand numarul de teste. Fiecare test este compus din 3 linii: pe prima linie se gaseste un numar intreg K, iar urmatoarele 2 linii contin sirurile de caractere.

Date de iesire

Fisierul de iesire seif.out va contine T linii, pe fiecare linie aflandu-se subsirul cautat pentru fiecare test in parte.

Restrictii

• 1 ≤ T ≤ 10
• 1 ≤ N, M ≤ 1000
• 0 ≤ K ≤ min(N, M)
• Un sir (x₁,x₂...x_N) este mai mare din punct de vedere lexicografic decat un alt sir (y₁,y₂...y_M) daca exista o pozitie p astfel incat x_p > y_p si x₁ = y₁, x₂ = y₂ ... x_p-1 = y_p-1.
• Pentru datele de test exista intotdeauna solutie

Exemplu

Cum se trimit solutii?