Fişierul intrare/ieşire:	fifty.in, fifty.out	Sursă	Finala ONIS 2016
Autor	Mihai Calancea	Adăugată de	Mihai Calancea •klamathix
Timp execuţie pe test	0.1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Fifty

În vremurile de graţie ale TopCoder-ului majoritatea restricţiilor din probleme erau egale cu 50. Din cauza asta, propunătorii găseau uneori metode neortodoxe de a cere rezolvarea a multe query-uri prin input de dimensiuni mici. Spre exemplu, să presupunem că dorim să producem multe query-uri care implică două numere naturale X şi Y. O soluţie este să oferim un şir de caractere 'a' şi 'b' şi să considerăm că fiecare subsecvenţă a sa reprezintă un query în care X este egal cu numărul de 'a'-uri din subsecvenţă, iar Y este egal cu numărul de 'b'-uri din subsecvenţă. Astfel, putem "stoca" O(N ^ 2) query-uri în spaţiu O(N).

În această problemă vi se dau M query-uri care trebuie neaparat să "apară" în input, iar voi trebuie să produceţi un şir de caractere de lungime exact N care să codeze aceste query-uri.

Spre exemplu, dacă N = 7, M = 2 iar cele două query-uri care trebuie incluse sunt X = 4, Y = 2, respectiv X = 3, Y = 3, atunci şirul "abaabab" este un răspuns valid, deoarece conţine subsecvenţele "abaaba" şi "baabab" care codifică aceste două query-uri.

Date de intrare

Fişierul de intrare fifty.in va conţine pe prima sa linie numărul T, semnificând numărul de teste. Structura unui test este următoarea: pe prima linie se vor afla numerele N şi M. Următoarele M linii vor conţine câte o pereche de numere X Y, semnificând valorile query-ului respectiv.

Date de ieşire

În fişierul de ieşire fifty.out va conţine exact T linii, fiecare conţinând un şir de caractere 'a' şi 'b' sau valoarea -1, în caz că nu există soluţie.

Restricţii

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 50
• 1 ≤ M ≤ 500
• Se acceptă orice soluţie corectă.
• Dacă nu există soluţie, se va afişa -1.

Exemplu

Cum se trimit solutii?