Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Minden nagyszünetben a fiúk legfontosabb témája a labdarúgó-világbajnokság. Történetünk három főhőse (Lázár, Martin és Ulrik) esetén sincs ez másképp. Ők mindennap megvitatják, hogy ki a legjobb játékos, a legjobb válogatott, és természetesen, hogy ki fog győzni. Amikor az a kérdés merül fel, hogy ki lesz a győztes, hatalmas vita bontakozik ki. Annak érdekében, hogy eldöntsék, melyikük tudja megjósolni legjobban a mérkőzések eredményét, megbeszélték, hogy fogadást kötnek.
Mindegyikük szeretné előrelátni a következő \(N\cdot M\) mérkőzés gólkülönbségeit. Az előrejelzések áttekinthetősége érdekében, Ulrik mindenki számára \(N\times M\) méretű táblázatot készített, ahova be tudják írni a jóslataikat. Tehát az \((i,j)\) (\(1\le i\le N\), \(1\le j\le M\)) mezőbe fogják beírni, hogy milyen gólkülönbséget látnak elő az \((M*(i-1)+j)\)-dik mérkőzésre (előzetesen rögzítik, hogy melyik csapat az „első”, így a gólkülönbség értéke negatív szám is lehet.
Viszont Lázár és Ulrik nem tudnak egy nagy titkot, mégpedig azt, hogy Martint nem különösebben érdekli a foci! Ő nem nézte meg a világbajnokság egyetlen mérkőzését sem, csak jól látja elő a dolgokat, és lelkesen bólogat. Így most, amikor valamit valóban meg kell jósolnia, komoly problémába ütközik. Szerencsére bele tudott kukkantani a barátai táblázatába, és látta Lázár jóslatát az \(l_{i,j}\) mátrixban és Ulrikét az \(u_{i,j}\) mátrixban. Előfordulhat, hogy Martinnak lövése sincs a focihoz, viszont jól ismeri a barátait, és tudja, hogy Lázár biztosan alábecsüli a gólkülönbséget (Lázár mindig a legbiztosabb opciókat választja, míg Ulrik biztosan túlértékeli (gyakran magával ragadja az izgalom). Ezért Martin eldöntötte, hogy, amikor az \(m_{i,j}\) mátrixba beírja az előrejelzését, arra érvényes, hogy \(l_{i,j}\le m_{i,j}\le u_{i,j}\). Azonban, hogy érdekesebbé tegye a jóslatok írását, eldöntötte, hogy ezt a játékká fogja átalakítani: a kezdésnél a táblázatát csupa nullás számokkal töltötte fel. Ő egy mozdulattal \(1\)-gyel tudja egy sor minden értékét megnövelni, vagy egy oszlop minden elemét \(1\)-gyel csökkenteni. Érdekli, hogy ezen műveletek segítségével tud-e olyan jóslatot készíteni, amelyre érvényes, hogy: \(l_{i,j}\le m_{i,j}\le u_{i,j}\), és a ti feladatotok, hogy segítsetek neki ebben.
A szabványos bemenet első sorában a \(T\) szám található, amely a tesztpéldák számát jelöli. Ezt követi minden tesztpélda leírása: az első sorban két egész szám található: \(N\) és \(M\). A következő \(N\) sorban \(M\) egész szám áll, amelyek Lázár jóslatát jelölik ‒ \(l_{i,j}\) mátrix. A további \(N\) sorban pedig \(M\) egész szám található, amelyek Ulrik jóslatát jelölik ‒ \(u_{i,j}\) mátrix.
Minden példa esetén egy választ kell adni, új sorban. Amennyiben Martin nem tud olyan jóslatot adni, amely megfelel a a feladat feltételeinek, csak annyit kell kiírni, hogy „NE” (idézőjelek nélkül). Ellenkező esetben azt kell kiíratni, hogy „DA” (idézőjelek nélkül), majd a következő \(N\) sorban \(M\) számot kell kiíratni, amelyek Martin előrejelzését jelölik. Amennyiben több megoldás is létezik, mindegy melyiket íratod ki.
2
2 2
1 -2
0 -3
4 0
1 -2
2 2
0 0
0 1
0 0
0 1DA
1 -2
1 -2
NEAz első esetben, ha a műveletet mindkét sorra elvégezzük egyszer, valamint elvégzünk három műveletet a második oszlopra, akkor a leírt mátrixot kapjuk eredményül, amely eleget tesz az egyenlőtlenségeknek, és így érvényes megoldás jelenik meg. A második esetben bizonyítható, hogy nem létezik megoldás.
A tesztpéldák öt diszjunkt csoportba vannak sorolva: