== include(page="template/taskheader" task_id="gardening") ==

Poveste şi cerinţă...

Azusa, vrăjitoarea munţilor, doreşte să se apuce de o activitate distractivă cu prietena ei, Laika: grădinărit. Ele vor să construiască o grădină dreptunghiulară de $N$ metri înălţime şi $M$ metri lăţime. Grădina este împărţită în pătrate de $1$ metru pe $1$ metru. Ele şi-au pus următoarea întrebare: ce flori ar trebui ele să planteze?
 
Laika are la dispoziţie $K$ tipuri diferite de flori. Azusa şi Laika vor planta câte un tip de floare în fiecare pătrat de $1$ metru pe $1$ metru. În plus, din motive estetice, grădina trebuie să satisfacă următoarele proprietăţi:
 
* Fiecare tip de floare trebuie să apară cel puţin odată în grădină.
* Pentru oricare două pătrate unde acelaşi tip de floare este plantat, trebuie să existe un drum între ele unde toate pătratele intermediare au acelaşi tip de floare. Spre exemplu, următoarele grădini *nu* sunt permise:
 
!{width:250px}problema/gardening?1.png!
!{width:200px}problema/gardening?2.png!
 
* Orice pătrat trebuie să aibă exact două pătrate adiacente în care e plantat acelaşi tip de floare. Spre exemplu, următoarele grădini *nu* sunt permise:
 
!{width:150px}problema/gardening?3.png!
!{width:100px}problema/gardening?4.png!
 
A se observa că, în restricţiile de mai sus, două pătrate sunt "adiacente" dacă şi numai dacă au o latură în comun (nu doar un colţ); şi un drum este o secvenţă de pătrate adiacente.
 
Ţi se dau $T$ valori diferite pentru $N$, $M$ şi $K$. Ajutaţi-le pe Azusa şi Laika să creeze grădini care satisfac condiţiile pentru fiecare test din input sau, dacă nu există soluţie, spuneţi-le că acest lucru este imposibil.

h2. Date de intrare

Fişierul de intrare $gardening.in$ ...

Prima linie din input conţine numărul întreg $T$. În continuare, urmează $T$ linii, fiecare descriind un test. Fiecare test consistă în trei numere întregi $N$, $M$ şi $K$.

h2. Date de ieşire

În fişierul de ieşire $gardening.out$ ...

Afişaţi răspunsurile pentru fiecare test în ordine. Pentru un test, dacă nu există soluţie, afişaţi $NO$ pe o singură linie. Altfel, mai întâi afişati $YES$ pe o singură linie, apoi afişati $N x M$ numere întregi aranjate pe $N$ linii şi $M$ coloane descriind grădina cerută. Liniile şi coloanele din output corespund liniilor şi coloanelor grădinii, fiecare număr întreg resprezentând tipul de flori plantate într-un pătrat de $1$ metru pe $1$ metru. Tipurile sunt indexate de la $1$ la $K$. Dacă sunt mai multe soluţii corecte puţeti afişa oricare din ele.

h2. Restricţii

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ N, M ≤ 200 000$.
* $1 ≤ K ≤ N x M$.
* Fie $S$ egal cu suma $N x M$ pentru toate testele dintr-un fişier pentru care există răspuns (i.e. pentru care răspunsul afişat nu este $NO$).
* $S ≤ 200 000$.
* Pentru 5 puncte, $N, M ≤ 4$.
* Pentru alte 6 puncte, $N ≤ 4$.
* Pentru alte 10 puncte, $N ≤ 6$.
* Pentru alte 18 puncte, $N = M$.
* Pentru alte 36 de puncte, $K$ este un număr între $1$ şi $N x M$ ales uniform aleator.

h2. Exemplu

h2. Exemple

table(example). |_. gardening.in |_. gardening.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5
2 2 2
2 2 1
4 4 4
4 4 2
4 6 3
| NO
YES
1 1
1 1
YES
1 1 2 2
1 1 2 2
3 3 4 4
3 3 4 4
YES
1 1 1 1
1 2 2 1
1 2 2 1
1 1 1 1
YES
1 1 1 1 1 1
1 2 2 3 3 1
1 2 2 3 3 1
1 1 1 1 1 1

|

h3. Explicaţie

h3. Explicaţii
 
Pentru primul test case, observăm ca nicio gradină de 2 pe 2 cu 2 tipuri de flori nu este corectă. Aşadar vom afisa $NO$. Celelalte grădini sunt ilustrate mai jos:

...

!{width:100px}problema/gardening?5.png!
!{width:200px}problema/gardening?6.png!
!{width:200px}problema/gardening?7.png!
!{width:300px}problema/gardening?8.png!

== include(page="template/taskfooter" task_id="gardening") ==