## DMOPC '16 Contest 2 P3 - Queries

View as PDF

Points: 7
Time limit: 0.6s
Memory limit: 64M

Author:
Problem types

You receive queries with the form of . Find a sequence of size , formed with a's and b's where you must "find" each query. A query is found if you can find a substring with a's and b's.

#### Input Specification

On the first line you will find the number of testcases, .
For each testcase, you will find on the first line and .
On the next lines, you will find the queries with the space-separated integers and .

#### Output Specification

For each testcase, print a sequence which respects the requirement. If you can't find a sequence, print -1.

#### Sample Input

1
7 2
4 2
3 3

#### Sample Output

abaabab