\documentclass[12pt]{article}
\input{structure.tex}
\fancyhead[R]{
	\begin{minipage}{\textwidth}
		\raggedleft
		\includegraphics[width=2cm]{./logo2.png}
	\end{minipage}
}
\renewcommand{\bottomtitlespace}{2cm}

\usepackage{graphbox}
\newcommand{\pic}[1]{%
	\includegraphics[align=c,scale=0.15]{gardening-images/#1.png}
}

\begin{document}

\renewcommand{\tl}{$0.2$ сек.}
\renewcommand{\ml}{$1024$ MB}
\problem{Задача TS1. ГРАДИНАРСТВО}
\addauthor{Автор: Велислав Гърков (заета)}{2026}{08}{28}
\renewcommand{\header}{
	НАЦИОНАЛНА ШКОЛА ПО ИНФОРМАТИКА\\
	КОНТРОЛНО СЪСТЕЗАНИЕ\\
	Габрово, 28 август 2026 г.\\
	9 – 10 клас
}

Азуса иска да се забавлява с приятелката си Лайка, като се занимават с градинарство. Те искат да направят правоъгълна градина, $N$ метра дълга и $M$ метра широка. Градината е разделена на малки квадратчета с размери от $1$ метър на $1$ метър. Въпросът е: какви цветя трябва да засадят?

Лайка е намерила $K$ различни видове цветя. Азуса и Лайка ще засадят по един вид цветя във всяко малко квадратче. Освен това, поради естетически причини, градината трябва да отговаря на следните ограничения:

\begin{enumerate}
	\item Всеки вид цвете трябва да се появи поне веднъж в градината.
	\item За всеки два квадрата, където е засаден един и същ вид цветя, трябва да съществува пътека между тях, където всички междинни квадратчета имат този вид цветя. Например, следните градини \textbf{не} са позволени:
	\begin{center}
		\pic{1}
		\hspace{1.5cm}
		\pic{2}
	\end{center}
	\item Всяко квадратче трябва да има точно две съседни квадратчета, засадени със същия вид цветя. Например, следните градини \textbf{не} са позволени:
	\begin{center}
		\pic{3}
		\hspace{1.5cm}
		\pic{4}
	\end{center}
\end{enumerate}

Забележете, че в предишните ограничения две квадратчета са „съседни“, тогава и само тогава, когато имат обща страна (не само връх); а пътят е редица от съседни квадратчета.

Дадени са $T$ различни стойности за $N$, $M$ и $K$. Напишете програма \textbf{\texttt{gardening}}, за да помогнете на Азуса и Лайка да създадат градини, които отговарят на условията за всеки тестов случай --- или им кажете, че е невъзможно да се направи това.

\subsection{Вход}
Първият ред на входа съдържа цялото число $T$. Следват $T$ реда, всеки от които описва тестов случай. Всеки тестов случай се състои от три цели числа $N$, $M$ и $K$.

\subsection{Изход}
Изведете отговорите за всеки тестов случай според последователността им във входа. За тестов случай, за който не съществува решение, изведете \texttt{NO} на един ред. В противен случай първо изведете \texttt{YES} на един ред и след това изведете $N \times M$ цели числа, подредени в $N$ реда и $M$ стълба, описващи градината. Редовете и стълбовете в изхода съответстват на редовете и стълбовете в градината, като всяко цяло число съответства на малко квадратче. Целите числа представляват видовете цветя, засадени в квадратите, където видовете са номерирани от $1$ до $K$. Ако има няколко правилни решения, може да изведете което и да е от тях.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
    \item $1 \le T \le 100~000$
	\item $1 \le N, M \le 500$.
	\item $1 \le K \le N \times M$.
	\item $S \le 200~000$, където $S$ е сумата от стойностите на $N \times M$ за всички тестови случаи, за които съществува отговор (т.е, за които изходът не е \texttt{NO}).
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|X[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{\makecell{Необходими\\подзадачи}} & $N$ & $M$ & \textbf{Други ограничения}\\
		\hline
		$0$ & $0$ & $-$ & $-$ & $-$ & Примерът. \\
		\hline
		$1$ & $5$ & $-$ & $\le 4$ & $\le 4$ & \SetCell[r=3]{}{--} \\
		\hline
		$2$ & $6$ & $0-1$ & $\le 4$ & $-$ & \\
		\hline
		$3$ & $10$ & $0-2$ & $\le 6$ & $-$ & \\
		\hline
		$4$ & $18$ & $-$ & \SetCell[r=3,c=2]{}{$\le 500$} & & $S \le 200~000, N = M$ \\
		\hline
		$5$ & $39$ & $-$ & & & $S \le 200~000$. $K$ е избрано равномерно случайно между $1$ и $N \times M$. \\
		\hline
		$6$ & $22$ & $0-5$ & & & -- \\
		\hline
	\end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.}
\end{table}
\FloatBarrier

\subsection{Пример}
\begin{table}[H]
	\begin{tblr}{|l|l|X[j]|}
		\hline
		\textbf{Вход} & \textbf{Изход} & \textbf{Обяснение на примера} \\
		\hline
		\texttt{\makecell[lt]{5 \\
				2 2 2 \\
				2 2 1 \\
				4 4 4 \\
				4 4 2 \\
				4 6 3}}
		&
		\texttt{\makecell[lt]{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}}
		&
		{За първия тестов случай не е възможна градина с размер $2$ на $2$ с $2$ вида цветя. Така извеждаме \texttt{NO}. Другите градини са изобразени по-долу:\\
		\pic{5}   \pic{6}   \pic{7}\\
		\pic{8}} \\
		\hline
	\end{tblr}
\end{table}
\FloatBarrier


\end{document}
