\documentclass[12pt]{article}
\input{structure.tex}
\renewcommand{\bottomtitlespace}{2cm}

\begin{document}

\renewcommand{\tl}{$2$ сек.}
\renewcommand{\ml}{$256$ MB}
\problem{Задача GT31. КИЛИМИ}
\addauthor{Автор: Александър Гатев}{2026}{05}{10}
\renewcommand{\header}{
	ТРЕНИРОВЪЧНО СЪСТЕЗАНИЕ\\
	НА РАЗШИРЕНИЯ НАЦИОНАЛЕН ОТБОР\\
	София, 6 май 2026 г.\\
	Група G
}

Даден е правоъгълен под с размери $N$ на $M$ метра. Подът е съставен от $N\times M$ дъски, всяка с размери $1 \times 1$, така че може да се разглежда като правоъгълна таблица с $N$ реда и $M$ колони, чиято номерация започва от $1$. Дадени са и $K$ килима, които се намират върху този под. Всеки килим покрива определен правоъгълен участък от пода, определен чрез четворка числа $(a_i,b_i,c_i,d_i)$. Такъв килим покрива клетките от таблицата с номер на реда между $a_i$ и $b_i$ включително и с номер на колоната между $c_i$ и $d_i$ включително. Възможно е килимите да се застъпват. Искаме да махнем някой от тях, но за да не се наруши цялостната естестика, за всеки килим търсим кои дъски ще бъдат открити. Напишете програма \texttt{\textbf{carpets}}, която за всеки килим намира дъските покрити единствено от него.

\subsection{Вход}
От първия ред на стандартния вход се въвеждат числата $N$, $M$ и $K$. От следващите $K$ реда се въвеждат по $4$ числа, описващи килимите. 
 
\subsection{Изход}
За всеки килим на отделен ред изходът трябва да е в следния формат:

$ cnt_i : (x_1,y_1) (x_2,y_2) ... (x_{cnt_i},y_{cnt_i}) $

Тук $cnt_i$ е броят на дъските покрити само от $i$-тия килим, а след него е изреден списъкът от конкретните дъски описани с ред и колона. Дъските трябва да са подредени първо по възходящ ред на номера на реда и после по възходящ ред на номера на колоната.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
    \item $1 \leq N,M \leq 2000$
	\item $1 \leq K \leq 10^6$
	\item $1\leq a_i \leq b_i\leq N$
	\item $1\leq c_i\leq d_i\leq M$
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|}
	\hline
	\textbf{Подзадача} & \textbf{Точки} & \textbf{Ограничения}\\
	\hline
	$0$ & $0$ & Примерът от условието. \\
	\hline
	$1$ & $9$ & $N,M,K\leq 50$ \\ 
	\hline
        $2$ & $22$ & $N,M\leq 500, K\leq 10^5$\\ 
       	\hline 
        $3$ & $23$ & {Отговорът за всеки килим е или 0, или най-горната \\лява дъска, която покрива. $K\leq 10^5$} \\ 
        \hline
        $4$ & $24$ & $N\leq 50$ \\ 
        \hline 
        $5$ & $22$ & $-$ \\ 
        \hline 
	\end{tblr}
    
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея.}
\end{table}
\FloatBarrier

\pagebreak

\subsection{Пример}
\begin{table}[H]
	\begin{tblr}{|l|l|X[j]|}
    		\hline
    		\textbf{Вход} & \textbf{Изход} \\
    		\hline
    		\texttt{\makecell[lt]{6 6 3 \\
            1 3 1 3 \\
            2 2 3 6 \\
            3 5 2 5}}
    		& 
    		\texttt{\makecell[lt]{6 : (1,1) (1,2) (1,3) (2,1) (2,2) (3,1) \\
            3 : (2,4) (2,5) (2,6) \\
            10 : (3,4) (3,5) (4,2) (4,3) (4,4) \\ (4,5) (5,2) (5,3) (5,4) (5,5)}}  \\
    		\hline
	\end{tblr}
\end{table}
\FloatBarrier
	
\end{document}
