Majstorija

Toată lumea știe că Mars este un călător de talie mondială. Iar numai călătorilor de talie mondială li se întâmplă neplăceri. De data aceasta, comisarul experimentat s-a pierdut pe o insulă plină de competitori înfocați.

Pentru a fi vizibil și pentru ca şi Comisia să-l salveze de pe insulă cu elicopterul oficial, el trebuie să deseneze pe nisip o matrice de dimensiuni N \times M. În fiecare căsuță a acestei matrici va desena fie cifra 0, fie cifra 1.

Totuși, nu este chiar atât de simplu. Pentru a justifica consumul de combustibil al elicopterului, matricea lui Mars trebuie să îndeplinească următoarele condiții:

• pe rândul i (pentru i=1,2,\ldots,N), suma numerelor trebuie să fie divizibilă cu i
• pe coloana j (pentru j=1,2,\ldots,M), suma numerelor trebuie să fie divizibilă cu j
• fiecare rând și fiecare coloană trebuie să conțină cel puțin o unitate.

Ajutați-l pe Mars spunându-i dacă este posibil să deseneze o astfel de matrice și, dacă este posibil, dați-i un exemplu de orice matrice de acest tip. În caz contrar, va trebui să citească obiecţiile concurenților supărați.

Descrierea intrării

În prima linie a intrării standard este dat un număr natural

T – numărul de exemple de test.

În următoarele T linii ale intrării standard sunt date două numere naturale N și M - numărul de rânduri şi coloane ale matricii în acest exemplu de test.

Descrierea ieșirii

Pentru i (pentru i = 1,2,\ldots, T) exemplu de test:

• dacă nu există matricea cerută, se afișează -1

• în caz contrar, se afișează orice matrice care îndeplinește condițiile problemei.

Exemplul 1

Intrare

2

1 6

4 4

Ieșire

-1

1 1 1 1

1 0 0 1

1 0 1 1

1 1 1 1

Explicație

Se poate demonstra că nu există nicio matrice de dimensiuni N= 1, M = 6, care să îndeplinească condițiile problemei.

În al doilea exemplu, când N = M = 4, putem observa că suma numerelor este:

• pe primul rând egală cu 4, ceea ce este divizibil cu unu;

• pe al doilea rând egală cu 2, ceea ce este divizivil cu doi;

• pe al treilea rând egală cu 3, ceea ce este divizibil cu trei;

• pe al patrulea rând egală cu 4, ceea ce este divizibil cu patru.

De asemenea, putem calcula că suma numerelor este:

• pe prima coloană egală cu 4, ceea ce este divizibil cu unu;

• pe a doua coloană egală cu 2, ceea ce este divizibil cu doi;

• pe a treia coloană egală cu 3, ceea ce este divizibil cu trei;

• pe a patra coloană egală cu 4, cee ace este divizibil cu patru.

Astfel, am găsit o matrice care îndeplinește condițiile.

Restricții

• 1 \leq T \leq 3

• 1 \leq N\cdot M \leq 1.000.000.

Exemplele de test sunt împărțite în patru grupuri disjuncte:

• în exemplele de test care valorează 10 puncte, este valabil că NM \leq 20.

• în exemplele de test care valorează 10 puncta, este valabil NM \leq 30.

• în exemplele de test care valorează 25 puncte, este valabil că NM \leq 45.

• în exemplele de test care valorează 55 puncte, nu există restricții suplimentare.