[old] Majstorija

Mindenki tudja, hogy Mars világutazó, és azt is tudjuk, hogy csak a világutazókkal történnek balesetek. Ezúttal egy tapasztalt bizottsági tag egy dühös versenyzőkkel teli szigeten tévedt el.

Annak érdekében, hogy könnyedén látható legyen, és hogy a Bizottság a hivatalos helikopterével ki tudja menteni a szigetről, a homokba egy N \times M méretű mátrixot kell rajzolnia. A mátrix minden mezőjébe vagy 0-t, vagy 1-et írhat.

Azonban a helyzet mégsem ilyen egyszerű. Hogy indokolt legyen a helikopter üzemanyag-felhasználása, Mars mátrixának az alábbi feltételeket kell teljesítenie:

• az i-edik sorban (ahol i=1,2,\ldots,N) a számok összege osztható kell hogy legyen i-vel;
• a j-edik oszlopban (ahol j=1,2,\ldots,M) a számok összege osztható kell hogy legyen j-vel;
• minden sorban és minden oszlopban legyen legalább egy darab 1-es.

Segítsetek meghatározni Marsnak, hogy lehetséges-e ilyen mátrixot rajzolni, és ha igen, adjatok meg egy tetszőleges példát egy ilyen mátrixra. Ellenkező esetben kénytelen lesz a dühös versenyzők panaszleveleit olvasni.

Bemenet leírása

A szabványos bemenet első sorában egy természetes T szám szerepel, amely a tesztesetek számát jelöli.

A szabványos bemenet következő T sorának mindegyikében két természetes szám (N és M) található – az adott tesztesetben szereplő mátrix sorainak és oszlopainak száma.

Kimenet leírása

Az i-edik (ahol i = 1,2,\ldots, T) tesztesetre:

• ha nem létezik a keresett mátrix, írjatok ki -1-et;
• ellenkező esetben írjatok ki bármilyen mátrixot, amely kielégíti a feladat feltételeit.

1. példa

Bemenet

2
1 6
4 4

Kimenet

-1
1 1 1 1
1 0 0 1
1 0 1 1
1 1 1 1

A példa magyarázata

Bizonyítható, hogy nem létezik olyan N= 1, M = 6 méretű mátrix, amely kielégíti a feladat feltételeit.

A második példában, amikor N = M = 4, láthatjuk, hogy a számok összege:

• az első sorban 4, amely osztható eggyel
• a második sorban 2, amely osztható kettővel
• a harmadik sorban 3, amely osztható hárommal
• a negyedik sorban 4, amely osztható néggyel

Továbbá kiszámíthatjuk, hogy a számok összege:

• az első oszlopban 4, amely osztható eggyel
• második oszlopban 2, amely osztható kettővel
• a harmadik oszlopban 3, amely osztható hárommal
• a negyedik oszlopban 4, amely osztható néggyel

Így találtunk egy mátrixot, amely kielégíti a feltételeket.

Korlátozások

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

A tesztpéldák négy diszjunkt csoportba vannak sorolva:

• A 10 pontot érő tesztpéldákban: érvényes, hogy NM \leq 20.
• A 10 pontot érő tesztpéldákban: érvényes, hogy NM \leq 30.
• A 25 pontot érő tesztpéldákban: érvényes, hogy NM \leq 45.
• Az 55 pontot érő tesztpéldákban: nincsenek további korlátozások.