组织者为晚宴订购了一个大蛋糕。他们订购的蛋糕上有 $n$ 根蜡烛，编号从 $0$ 到 $n - 1$。已知这些蜡烛位于平面上的不同点，且任意三根蜡烛不在同一直线上，任意四根蜡烛不构成梯形（即没有两边平行的四边形）。

为了确保每个人都能分到一块蛋糕，组织者希望预先设计一种将蛋糕切成尽可能多块的方法。不幸的是，你不知道蜡烛在蛋糕上的具体位置，了解蛋糕形状的唯一途径是通过电子邮件与糕点店联系。

在一条消息中，你可以请求称量不超过四个三角形块，这些三角形的顶点位于蜡烛处：

• 你提供两个三角形列表 left 和 right，总共包含不超过四个三角形。这些三角形可能会相交、共享公共蜡烛，甚至重合。
• 糕点店将根据请求的列表从蛋糕的多个副本中切下这些三角形块，并将 left 中的块放在左天平上，将 right 中的块放在右天平上。
• 你将收到称量结果。我们认为一块的重量等于其面积。因此，你将得知哪一个三角形列表的总面积更大，或者它们的面积是否相等。

经过多次称量后，你必须找到一种切割蛋糕的方法。每一块必须是一个顶点位于蜡烛处的凸多边形。多边形的顶点必须按顺时针或逆时针的遍历顺序给出。任意两块不得在内部相交。你必须返回一个总面积尽可能大的分块列表。此外，在某些组别中，还要求最大化分块的数量。

实现细节

这是一个不同寻常的问题。它采用带有评测器的测试格式，你只需要实现 solve 函数。该函数将由评测程序（评测器）调用，函数的返回值将被视为问题的解。

特别地，这意味着你提交的代码不得包含输入或输出。你的代码不得包含 main 函数。如有必要，你可以实现任意数量的辅助函数、结构体、类和全局变量，但所有代码必须位于同一个文件中。

你必须实现以下函数：

std::vector<std::vector<int>> solve(int n);

函数 solve 接收一个整数 $n$ —— 蜡烛的数量。

在 solve 的实现中，你可以使用由评测器实现的 compare 函数：

int compare(const std::vector<Triangle>& left, const std::vector<Triangle>& right);

该函数接收两个非空的三角形列表，总大小不超过 4。如果 left 中三角形的总面积小于 right 中三角形的总面积，则返回 $-1$；如果面积相等，则返回 $0$；否则返回 $1$。如果请求不正确或超过了请求次数限制，程序将自动终止。

要访问 compare 函数，你的代码第一行必须包含以下头文件：

#include "triangles.h"

在该文件中，compare 函数中使用的 Triangle 结构体定义如下：

struct Triangle {
    int i, j, k;
    Triangle() = default;
    Triangle(int i_, int j_, int k_) : i(i_), j(j_), k(k_) {}
};

该结构体描述了一个三角形块，参数 $i, j, k$ 描述了构成该三角形顶点的蜡烛索引。单个三角形块的顶点索引必须不同，但它们可以在多个三角形中重复。

你不需要在提交的代码中包含 Triangle 结构体的定义；它将自动从头文件中获取。

所有参数（请求中的蜡烛索引以及你返回的结果）均采用 0-索引。

你的 solve 函数应使用 compare 函数来找到一种将蛋糕划分为凸多边形的方法，使得任意两块在内部不相交，且总面积最大化，并尽可能最大化分块数量。

solve 函数应返回一个分块列表。每一块由一个 std::vector<int> 结构描述，包含构成该凸多边形的蜡烛索引。蜡烛必须按多边形边界的遍历顺序（顺时针或逆时针）列出。任意两块不得在内部相交。你必须返回一个总面积尽可能大的分块列表，在某些组别中，还要求在保持总面积最大化的前提下最大化分块数量。

在评测器的一次运行中，评测程序将恰好调用一次 solve 函数。评测器是非自适应的，这意味着蜡烛的位置是预先固定的，不依赖于 solve 函数的实现。

测试

你将获得一个解决方案模板 triangles.cpp 以及一个头文件 triangles.h，其中包含 solve 和 compare 函数的定义。为了方便测试，你将获得一个评测器文件 grader.cpp。该文件实现了从标准输入读取数据、调用 solve 函数并将 solve 函数的结果输出到标准输出的功能。在测试系统中，评测器可能会有所不同。

在 C++ 中编译你的代码 triangles.cpp，请使用以下命令：

g++ -std=c++20 grader.cpp triangles.cpp -o grader

执行此命令后，将创建一个名为 grader 或 grader.exe 的可执行文件，你可以运行它来输入指定格式的测试数据。

输入格式

评测器按以下格式读取测试数据： 第一行包含一个整数 $n$ ($4 \le n \le 10\,000$) —— 蜡烛的数量。 接下来的 $n$ 行，每行包含两个整数 $x_i, y_i$ ($-10^9 \le x_i, y_i \le 10^9$) —— 第 $i$ 根蜡烛的坐标。

输出格式

评测器输出 solve 函数的结果 —— 找到的分块列表。 第一行打印找到的多边形数量（solve 函数返回的向量大小）。 在接下来的行中，对于每个多边形（solve 返回向量中的一个元素），首先打印多边形的大小，然后打印构成该多边形顶点的蜡烛索引行（solve 返回值中每个 std::vector<int> 的元素）。每个多边形必须是凸的，且其顶点必须按遍历顺序（顺时针或逆时针）列出。任意两个多边形不得在内部相交。

在 grader.cpp 文件中，有一个变量 verbose，初始设置为 0。通过增加其值，评测器将输出关于你的解及其请求的更详细信息。

样例

样例 1

输入格式 1

4
1 2
1 4
0 0
3 -1

输出格式 1

3
3
0 1 2
3
0 2 3
3
0 1 3

样例 2

输入格式 1

5
-1 -1
4 4
4 -2
1 2
-2 2

输出格式 1

1
4
0 4 1 2

样例 3

输入格式 1

6
2 2
0 -2
-1 3
-2 0
7 0
2 -3

输出格式 1

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

说明

在第一个样例中，函数调用序列可能如下所示： 首先调用 solve(4)。 从 solve 函数中调用： compare({Triangle(0, 1, 2)}, {Triangle(1, 2, 3)}) 在函数执行期间，比较了顶点为 0, 1, 2 的三角形与顶点为 1, 2, 3 的三角形的大小。由于第一个三角形小于第二个，函数返回 $-1$。 接下来，从 solve 函数中调用： compare({Triangle(1, 2, 3)}, {Triangle(0, 1, 2), Triangle(0, 1, 3)}) 响应返回 1，因为顶点为 1, 2, 3 的三角形面积大于顶点为 0, 1, 2 的三角形与顶点为 0, 1, 3 的三角形的总面积。 接下来，从 solve 函数中调用： compare({Triangle(1, 2, 3)}, {Triangle(0, 1, 2), Triangle(2, 3, 0), Triangle(0, 1, 3)}) 响应返回 0。 最终，solve 函数返回 {{0, 1, 2}, {0, 2, 3}, {0, 1, 3}} —— 描述了将蛋糕划分为总面积最大且内部不相交的凸多边形的方法。

在第一和第三个样例中，找到的切割方法具有最大可能的分块数量，因此在要求最大化的组别中，此类答案被认为是正确的。在第二个测试中，分块数量不是最大可能的，因此在不要求最大化的组别中，此类答案被认为是正确的，但在要求最大化的组别中将获得 0 分。

子任务

测试由 11 个组组成。

• 如果你的解对 compare 进行了错误的调用或返回了不满足强制条件的答案，该测试将获得 0 分。
• 在每个测试中，你的解最多允许进行 $2 \cdot 10^6$ 次 compare 函数调用。如果超过限制，该测试将获得 0 分。
• 在某些组别中，要求最大化答案中的分块数量。在这些组别中，如果分块数量不是最大可能的，该测试将获得 0 分。

如果测试未违反上述任何条件，则该测试的答案被视为正确。设该测试组的总分为 $p$。

• 如果该组不使用公式评估，则测试得分为 $p$。
• 否则，如果该组使用公式评估，设 $q$ 为你的解进行的 compare 调用次数。则测试得分为 $p \cdot \frac{20n}{\max(q, 20n)}$。

在第 6-9 组中，所有点均从正方形 $[-10^9, 10^9] \times [-10^9, 10^9]$ 中随机且独立地选择。 在第 3-4 组中，除 $(10^9, -10^9), (-10^9, 10^9), (10^9, 10^9)$ 外的点均从顶点为 $(10^9, -10^9), (-10^9, 10^9), (10^9, 10^9)$ 的三角形中随机且独立地选择。 在这些组中，仅保留所有点互不相同、任意三点不共线且任意四点不构成梯形的随机测试。