(Живот у граду) Знаш да мораш да преживиш
(Живот у граду) Мораш да одржиш тај сан живим
(Живот у граду) Где све је бесплатно
(Живот у граду) Зар не можеш да видиш

Горе је наведен ауторов слободни превод текста песме „Живот у граду“, која је изворно песма за други ниво, „Радикални град“, у игрици Соник Р из 1997. Музичке критичаре и аналитичаре широм света је годинама бунило тачно значење речи. Међутим, данас је дан када се коначно открива шта се крило иза ових вешто написаних стихова - песма се односи на државно такмичење из информатике средњих школа 2023. године нове ере. Заиста, наведени град се очигледно односи на Крагујевац, преживљавање на избегавање бучних Крагујевачких концерта, сан је ништа друго него 300 поена на такмичењу, док је интерпретација шта је тачно то све бесплатно, и чин опажања истог једноставна и оставља се као вежба читаоцу.

Поставка је следећа. Такмичари долазе у Крагујевац, на државно такмичење. Као што то често бива са градовима у информатичким задацима, Крагујевац може замислити као матрицу димензија \(N\times M\) . Такмичари улазе у град на поље \((1,1)\), док се такмичење одржава у пољу \((N,M)\). Како такмичење ускоро креће, нема времена за губљење, тако да такмичари морају да стигну до такмичења тако што у сваком потезу пређу на поље директно десно или директно испод тренутног.

Међутим, у неким пољима се одржавају концерти. Многи би саветовали младим такмичарима да се клоне ових поља, али како је ово прво такмичење из информатике ван Београда у ко зна колико времена, они су одлучили да морају да искусе сваки део локалне културе и самим тим посете тачно \(K\) поља са концертима. Ваш циљ је да вашим колегама такмичарима кажете да ли је ово могуће и (у неким подзадацима), уколико јесте, дате пример таквог пута.

Опис улаза

У првој линији стандардног улаза налазе се два цела броја \(T\), број тест примера и \(Z\) који је једнак нула уколико дати тест пример не захтева реконструкцију, а \(1\) уколико захтева. Сваки тест пример је следећег формата: У првом реду налазе се \(3\) цела броја \(N\), \(M\) и \(K\). У \(i\)-том од наредних \(N\) редова се по \(M\) целих бројева, где је \(j\)-ти једнак \(1\) уколико се одржава концерт на пољу \((i,j)\), а једнак \(0\) у супротном. ## Опис излаза За сваки од \(T\) тест примера је потребно у првом реду исписати “DA” (без наводника), уколико је могуће испунити услове задатка, а “NE” (без наводника) уколико није. Даље, уколико је \(Z=1\) и одогвор је био “DA”, потребно је исписати ниску од \(M+N-2\) караткера, где је \(i\)-ti карактер \(S\) уколико такмичари треба да иду на доле, а уколико треба да иду десно, караткер треба да буде \(D\). Уколико постоји више решења исписати било које. ## Ограничења - \(1 \leq T \leq 10\) - \(1 \leq N,M \leq 1.500\) - \(0 \leq K \leq 3.000\) ## Подзадаци - (8 поена): \(N,M\leq 10\) - (6 поена): Сва поља са концертима формирају подматрицу и \(Z=0\) - (10 поена): Сва поља са концертима формирају подматрицу - (13 поена): \(N,M\leq 150\), \(Z=0\) - (13 поена): \(N,M\leq 150\) - (11 поена): \(K=0\) - (20 поена): \(Z=0\) - (19 поена): Без додатних ограничења ## Пример

Улаз

3 1
3 3 1
000
000
100
3 3 2
001
010
100
3 4 0
0011
1000
1100

Излаз

DA
SSDD
NE
DA
DSDDS

Објашњење

У првом примеру се одржава само један концерт у Крагујевцу, и то у доњем левом углу. Да би га такмичари посетили, морају прва два потеза да иду на доле, а затим да продуже до места такмичења са 2 потеза десно (како је \(Z=1\) потребно је исписати и конструкцију пута). У другом не постоји начин да посете две концерта, па је одговор “NE”.