AT_awtf2024_e Colorful Stamps

你需要解决 $ T $ 个测试用例中的一个问题。 有一个 $ N \times N $ 的棋盘。第 $ i $ 行第 $ j $ 列的格子记作格子 $ (i,j) $。初始时，所有格子都是无色的。 你拥有 $ N^2 $ 种不同的印章。对应每个整数对 $(h, w)$，其中 $1 \leq h, w \leq N$，都有一个大小为 $ h \times w $ 的印章，简称印章 $(h, w)$。所有印章的颜色各不相同。 “使用印章 $(h, w)$”这一操作指的是： - 选择一个位置 $(a, b)$，满足 $1 \leq a \leq N-h+1$ 和 $1 \leq b \leq N-w+1$。然后用印章 $(h, w)$ 的颜色覆盖格子 $(i, j)$，其中 $a \leq i \leq a+h-1$ 和 $b \leq j \leq b+w-1$。若一个格子已被涂上其他颜色，将被新颜色覆盖。 你的目标是通过每个印章使用一次，使得最终棋盘上每个格子的颜色都不相同。 你已经使用了 $K$ 个印章，第 $i$ 个使用的印章为 $(H_i, W_i)$，其位置为 $(A_i, B_i)$。 请展示一种方案，利用剩余的 $N^2 - K$ 个印章实现目标。请注意，题干保证输入的每个测试用例都能通过恰当的方法完成任务。

输入通过以下格式提供： > $T$ $case_1$ $case_2$ $\ldots$ $case_T$ 每个测试用例格式如下： > $N$ $K$ $H_1$ $W_1$ $A_1$ $B_1$ $H_2$ $W_2$ $A_2$ $B_2$ $\ldots$ $H_K$ $W_K$ $A_K$ $B_K$

对于每个测试用例，输出以下格式的方案： > $h_1$ $w_1$ $a_1$ $b_1$ $h_2$ $w_2$ $a_2$ $b_2$ $\ldots$ $h_{N^2-K}$ $w_{N^2-K}$ $a_{N^2-K}$ $b_{N^2-K}$ 这表示（除了已经使用的 $K$ 个印章外），第 $i$ 个使用的印章是 $(h_i, w_i)$，其位置是 $(a_i, b_i)$。

- $1 \leq T$ - $2 \leq N \leq 400$ - $0 \leq K < N^2$ - $1 \leq H_i, W_i \leq N$ - $1 \leq A_i \leq N-H_i+1$ - $1 \leq B_i \leq N-W_i+1$ - $(H_i, W_i) \neq (H_j, W_j)$ 当 $i \neq j$ - 所有测试用例中 $N^2$ 的总和不超过 $160,000$ - 输入保证可以通过某种方法实现目标 - 所有输入均为整数 ### 样例解释 以第一个测试用例为例。（包括已经使用的 $K$ 个印章在内）如果我们用 $i$ 表示第 $i$ 次使用印章后的颜色变化，棋盘的状态变化如下： ``` .. -> 11 -> 11 -> 31 -> 31 .. (2,2,1,1) 11 (1,2,2,1) 22 (2,1,1,1) 32 (1,1,2,1) 42 ``` 注意，输出示例为了便于阅读在测试用例之间添加了额外的换行符，但这不是必须的（当然加上也可以）。 **本翻译由 AI 自动生成**