题目描述

你需要解决 $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

输入 #1

4
2 2
2 2 1 1
1 2 2 1
2 0
3 3
3 3 1 1
3 2 1 2
2 3 1 1
5 15
5 5 1 1
4 5 2 1
5 4 1 1
4 4 2 1
3 5 3 1
2 5 4 1
1 5 4 1
5 3 1 1
3 4 3 1
2 4 3 1
4 3 2 1
1 4 4 1
3 3 3 1
2 3 4 1
1 3 5 1

输出 #1

2 1 1 1
1 1 2 1

2 2 1 1
2 1 1 1
1 2 1 1
1 1 1 1

2 2 1 2
3 1 1 2
1 3 2 1
1 2 2 1
2 1 1 2
1 1 1 2

5 2 1 1
4 2 1 1
3 2 1 1
5 1 1 1
2 2 1 1
4 1 1 1
1 2 1 1
3 1 1 1
2 1 1 1
1 1 1 1

说明/提示

• $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

注意，输出示例为了便于阅读在测试用例之间添加了额外的换行符，但这不是必须的（当然加上也可以）。