Светско првенство у фудбалу је главна тема свих дечачких прича на великом одмору, па је тако и за тројицу јунака овог задатка - Лазара, Момира и Угљешу. Они сваки дан дискутују о томе ко је најбољи играч, најбоља репрезентација и најбитније, ко ће да победи. Међутим, када се постави питање победника настају огромне несугласице. Да би одлучили ко заиста најбоље предвиђа резултате утакмица, договорили су се да направе опкладу.

Свако од њих жели да предвиди гол-разлику у наредних \(N\cdot M\) мечева. Зарад прегледности предвиђања, Угљеша је направио свима таблице димензије \(N\times M\) где ће они уписивати своја предвиђања. Наиме, у пољу \((i,j)\) (\(1\le i\le N\), \(1\le j\le M\)) ће написати коју гол-разлику предвиђају у \((M*(i-1)+j)\)-тој утакмици (унапред су фиксирали који тим је “први”, тако да гол-разлика може бити и негативна).

Међутим, тајна коју Лазар и Угљеша не знају је да Момира баш и не интересује фудбал! Он није одгледао ниједну утакмицу светског првенства, само је јако добар у измишљању и климању главом. Зато сад кад треба да заправо предвиди сам нешто, упао је у озбиљан проблем. Срећом, успео је да вирне својим пријатељима у табеле и видео Лазарова предвиђања у матрици \(l_{i,j}\), а Угљешина у матрици \(u_{i,j}\). Момир можда не зна ништа о фудбалу, али зна своје пријатеље, тако да зна да ће Лазар сигурно потценити гол разлику (Лазар увек иде на најсигурније опције), док ће их Угљеша сигурно преценити (Угљешу често понесе узбуђење). Стога, Момир је одлучио да кад напише његова предвиђања у матрицу \(m_{i,j}\) важи \(l_{i,j}\le m_{i,j}\le u_{i,j}\). Међутим, како би му ово писање предикција било интересантније, он је одлучио да претвори то у игру. Наиме, на почетку је уписао у своју табелу све нуле. Он ће у једном потезу или да повећа све вредности у неком реду за \(1\), или да смањи све вредности у некој колони за \(1\). Интересује га да ли је могуће помоћу ових операција да направи предвиђања за која ће важити \(l_{i,j}\le m_{i,j}\le u_{i,j}\), а ваш задатак је да му помогнете у томе.

Опис улаза

У првој линији улаза се налази број \(T\) који представља број тест примера. Даље следи опис сваког тест примера: У првом реду се налазе два цела броја \(N\) и \(M\). У наредних \(N\) редова се налазе по \(M\) целих бројева који представљају Лазарева предвиђања - матрицу \(l_{i,j}\). У наредних \(N\) редова се налазе по \(M\) целих бројева који представљају Угљешина предвиђања - матрицу \(u_{i,j}\).

Опис излаза

За сваки пример треба дати одговор, и то одвојен новим редом. Уколико није могуће да Момир направи своја предвиђања да испуњавају услове задатка, потребно је само исписати “NE” (без наводника). У супротном треба исписати “DA” (без наводника) и у наредних \(N\) редова исписати по \(M\) бројева који представљају Момирова предвиђања. Уколико постоји више решења, исписати било које. ## Пример ### Улаз

2
2 2
1 -2
0 -3
4 0
1 -2
2 2
0 0
0 1
0 0
0 1

Излаз

DA
1 -2
1 -2
NE

Објашњење

У првом случају ако применимо операцију на оба реда по једном, као и три операције на другу колону, добијамо исписану матрицу, а она испуњава тражене неједнакости, па је валидно решење исписано. У другом случају је могуће доказати да не постоји решење.

Ограничења

• \(1 \leq T \leq10\)
• \(1\leq N\leq 300\)
• \(-2\times10^9\le l_{i,j}\le u_{i,j}\le2\times10^9\)

Тест примери су подељени у пет дисјунктних група:

• У тестовима вредним 15 поена: \(N,M\le10\) и \(u_{i,j}-l_{i,j}\le1\) за свако \(1\le i\le N\), \(1\le j\le M\)
• У тестовима вредним 10 поена: важи \(l_{i,j}=u_{i,j}\) за свако \(1\le i\le N\), \(1\le j\le M\)
• У тестовима вредним 15 поена: важи \(l_{i,j}=u_{i,j}\) за сва поља када је \(i=1\) или \(j=1\).
• У тестовима вредним 15 поена: важи \(l_{i,j}=u_{i,j}\) за сва поља где су \(i\) и \(j\) исте парности.
• У тестовима вредним 45 поена: нема додатних ограничења