Jeroen 为西北电气资源公司 (NWERC) 经营着一家仓库存储设施。当客户向 NWERC 下订单时，订单会被传送到仓库。Jeroen 的任务是找到订购的产品，将它们装入箱子，并运送给客户。

NWERC 有一项不同寻常的仓库政策：产品没有按任何特定顺序排列，而是散落在各处。然而，Jeroen 能够完成他的工作，因为每件产品都使用 RFID 技术进行追踪。具体来说，每件产品在进入仓库时都会被分配一个无线 RFID 芯片，仓库天花板上的传感器用于自动追踪这些产品。

默认情况下，每个传感器的范围为 $r$ 个单位——也就是说，它可以读取位于其 $r$ 个单位距离内（直线距离）的任何 RFID 芯片。然而，如果传感器和产品之间的线段与 $x$ 面墙相交或接触，则传感器在该方向上的范围会减少 $x$ 个单位。此外，由于其他传感器的干扰，传感器可能无法读取 RFID 芯片，因此仓库中任意一对传感器之间的距离保证至少为 $r$ 个单位。你还可以假设没有任何传感器或产品被放置在墙上。

Jeroen 现在想确定对于每件产品，哪些传感器可以读取其 RFID 芯片。你能帮帮他吗？

样例输入中传感器、墙壁和产品的示意图。

输入格式

第一行包含一个正整数：测试用例的数量，最多为 100 个。每个测试用例包含：

• 一行包含四个整数 $s$ ($1 \le s \le 250\,000$)，$r$ ($1 \le r \le 20$)，$w$ ($0 \le w \le 10$) 和 $p$ ($1 \le p \le 10\,000$)，其中 $s$ 表示传感器数量，$r$ 表示每个传感器的范围，$w$ 表示墙壁数量，$p$ 表示产品数量。
• $s$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($-10\,000 \le x_i, y_i \le 10\,000$)。每一行代表一个位于 $(x_i, y_i)$ 的传感器。保证任意一对传感器之间的距离至少为 $r$ 个单位。
• $w$ 行，每行包含四个整数 $bx_i, by_i, ex_i$ 和 $ey_i$ ($-10\,000 \le bx_i, by_i, ex_i, ey_i \le 10\,000$)。每一行代表一堵墙，应视为从 $(bx_i, by_i)$ 到 $(ex_i, ey_i)$ 的线段。该线段的长度为正。
• $p$ 行，每行包含两个整数 $px_i$ 和 $py_i$ ($-10\,000 \le px_i, py_i \le 10\,000$)。每一行代表一个位于 $(px_i, py_i)$ 的产品。

输出格式

对于每个测试用例：

• 输出 $p$ 行，每行代表一个产品，顺序与输入中的顺序一致。每行应包含一个整数 $t$，表示可以追踪该产品的传感器数量；随后是 $t$ 个有序对，表示相应的传感器位置。如果有多个传感器，应按 $x$ 坐标升序排序。如果多个传感器具有相同的 $x$ 坐标，则应按 $y$ 坐标升序排序。

样例

输入 1

1
4 3 4 7
0 0
-1 3
2 3
11 5
-4 -1 5 -1
3 4 6 1
11 4 11 3
12 5 12 8
1 1
0 -2
4 4
11 2
13 5
13 7
14 5

输出 1

3 (-1,3) (0,0) (2,3)
1 (0,0)
0
0
1 (11,5)
0
0