Funni酱喜欢看星星。
天空中有$$$n$$$颗星星,可以看作笛卡尔坐标平面上的点。第 $$$i$$$ 颗恒星的坐标为 $$$(x_i, y_i)$$$。保证所有 $$$x_1, x_2, \ldots, x_n$$$ 成对不同,并且所有 $$$y_1, y_2, \ldots, y_n$$$ 成对不同。星星按照输入中给出的顺序从 $$$1$$$ 到 $$$n$$$ 进行编号。
Funni-chan 想要将这些星星中的一些配对连接起来形成一个星座。
她将星座的基本单位定义为由三颗恒星两两连接形成的三角形。三角形称为 和谐 如果存在一个轴对齐的矩形,使得三角形的所有三个顶点都位于矩形的边界上。
Funni-chan 对星座施加了以下约束:
- 星座中的每个三角形都必须是 和谐.
- 星座中任意两个三角形的内部必须不相交。请注意,三角形的边界不被视为其内部的一部分。
在这些限制下,Funni-chan 希望她的星座包含尽可能多的三角形。你的任务是找到这个最大数字并构建一个有效的星座来实现它。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 2\cdot 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — 星星的数量。
接下来的 $$$n$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$-10^9\le x_i, y_i \le 10^9$$$) — 第 $$$i$$$ 颗恒星的坐标。保证所有 $$$x_i$$$-s 成对不同,并且所有 $$$y_i$$$-s 成对不同。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
在每个测试用例的第一行,您应该打印一个整数 $$$m$$$ ($$$0\le m\le 2\cdot n$$$) — 星座中三角形的最大可能数量。
接下来是 $$$m$$$ 行,每行包含三个不同的正整数 $$$a_i$$$、$$$b_i$$$ 和 $$$c_i$$$ ($$$1 \le a_i, b_i, c_i \le n$$$),表示构成第 $$$i$$$ 个三角形的三颗星的索引。
示例
输入复制
28-10 1-2 65 108 -9-1 -23 00 31 -888 8-5 3-4 15 710 10-3 5-8 -10-7 -1
输出复制
86 5 86 8 41 6 57 1 62 7 13 2 73 7 63 6 422 3 86 2 3
注意
示例的第一个测试用例如下图所示:
示例的第二个测试用例如下所示: