\textbf{Данную задачу можно решать только на языке программирования C++.}

Организаторы Закрытой олимпиады школьников по программированию решили заказать большой торт на вечерний банкет. Для этого они заказали торт с $n$ свечками, пронумерованными от $0$ до $n-1$. Известно, что свечки находятся в различных точках на плоскости, никакие три свечки не лежат на одной прямой, никакие четыре свечки не образуют трапецию (четырехугольник с двумя параллельными сторонами).

Чтобы всем достался кусочек торта, организаторы хотят заранее построить способ разрезать торт на максимальное число кусочков. К сожалению, вам неизвестно расположение свечек на торте, а единственный доступный способ узнать, как выглядит торт --- переписка с кондитерской по электронной почте.

В одном сообщении вы можете попросить взвесить не более четырех треугольных кусочков, с вершинами в свечках:

\begin{itemize}
\item Вы предоставляете два списка треугольников \texttt{left} и \texttt{right}, суммарно содержащих не более четырех треугольников. Треугольники могут пересекаться, содержать общие свечки и даже совпадать.
\item В кондитерской вырежут треугольные кусочки в соответствии с запрошенными списками из нескольких копий торта и положат кусочки из \texttt{left} на левую чашу весов, кусочки из \texttt{right} на правую чашу весов.
\item Вам отправят результат взвешивания. Будем считать, что вес кусочка равен его площади. В результате вы узнаете, в каком из списков треугольников суммарная площадь больше, или что площади совпадают.
\end{itemize}

После нескольких взвешиваний вы должны найти способ разрезать торт. Каждый кусочек должен быть выпуклым многоугольником с вершинами в свечках. Вершины кусочка должны быть перечислены в порядке обхода по или против часовой стрелки. Любые два кусочка не должны пересекаться по внутренним точкам. Вы должны вернуть список кусочков, суммарная площадь которых максимально возможная. Также в некоторых группах требуется максимизировать число кусочков.

\SolutionFormat

Это необычная задача. Она имеет формат тестирования с грейдером, где вам необходимо реализовать только функцию \texttt{solve} с решением. Эта функция будет вызвана тестирующей программой жюри (грейдером), и возвращаемое значение функции будет принято как решение задачи.

В частности, это означает, что в отправленном вами коде \textbf{не должно быть ввода или вывода}. Ваш код \textbf{не должен} содержать функцию \texttt{main}. При необходимости вы можете реализовать произвольное количество вспомогательных функций, структур, классов и глобальных переменных, но весь код вашего решения должен находиться в одном файле.

Вы должны реализовать следующую функцию:

\begin{verbatim}
std::vector<std::vector<int>> solve(int n);
\end{verbatim}

Функция \texttt{solve} принимает на вход единственное число $n$~--- количество свечек.

В реализации функции \texttt{solve} вы можете использовать функцию \texttt{compare}, которую реализует грейдер:

\begin{verbatim}
int compare(const std::vector<Triangle>& left, const std::vector<Triangle>& right);
\end{verbatim}

Данная функция принимает на вход два непустых списка треугольников суммарного размера не более $4$. В качестве результата она возвращает $-1$, если суммарная площадь треугольников в \texttt{left} меньше суммарной площади треугольников в \texttt{right}, $0$, если площади равны и $1$, иначе. Если сделать некорректный запрос или исчерпать лимит на количество запросов, то программа автоматически завершит свою работу.

Для того, чтобы получить доступ к функции \texttt{compare} в решении, первой строчкой вашего кода нужно подключить заголовочный файл следующей строчкой:

\begin{verbatim}
#include "triangles.h"
\end{verbatim}

В этом же файле определена используемая в функции \t{compare} структура \t{Triangle}:

\begin{verbatim}
struct Triangle {
    int i, j, k;

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

Данная структура описывает один треугольный кусочек, параметры \t{i}, \t{j} и \t{k} описывают номера свечек, образующих вершины треугольного кусочка. Номера свечек должны быть различными для одного треугольного кусочка, но могут повторяться в нескольких треугольниках.

\textbf{В код отправляемого решения вам не надо включать определение структуры \t{Triangle}, оно будет автоматически браться из заголовочного файла.}

Все параметры (индексы свечек в запросах, а также в возвращаемом вами результате) задаются в \textbf{0-индексации}.

Ваша функция \texttt{solve} с помощью вызовов функции \texttt{compare} должна найти любое разбиение торта на выпуклые кусочки, в котором любые два кусочка не пересекаются по внутренним точкам, суммарная площадь кусочков максимальна, и, возможно, количество кусочков максимально. 

Функция \t{solve} должна вернуть список кусочков, на которые разбивается торт. Каждый кусочек описывается структурой \t{std::vector<int>}, состоящей из свечек, образующих выпуклый многоугольник. Свечки должны быть перечислены \textbf{в порядке следования по границе многоугольника} (по часовой стрелке или против часовой стрелки). Любые два кусочка не должны пересекаться по внутренним точкам. Вы должны вернуть список кусочков, суммарная площадь которых максимально возможная, а в некоторых группах дополнительно требуется максимизировать количество кусочков, при этом сохраняя условие на максимальную возможную суммарную площадь.

За один запуск грейдера \textbf{жюри сделает ровно один вызов функции} \texttt{solve}. \textbf{Грейдер не является адаптивным}, то есть положения свечек фиксируются заранее и не зависят от реализации функции \texttt{solve}.

\Testing

Вам предоставлен шаблон решения \texttt{triangles.cpp}, а так же заголовочный файл \texttt{triangles.h}, содержащий определение функций \texttt{solve} и \texttt{compare}. Для удобства тестирования вам предоставлен грейдер --- файл \texttt{grader.cpp}. В этом файле реализован ввод входных данных со стандартного потока ввода, запуск функции \texttt{solve} и вывод на стандартный поток вывода возвращаемого значения функции \texttt{solve}. В тестирующей системе грейдер может отличаться.

Чтобы скомпилировать ваш код \texttt{triangles.cpp} на языке C++, используйте команду

\begin{verbatim}
g++ -std=c++20 grader.cpp triangles.cpp -o grader
\end{verbatim}

После выполнения данной команды будет создан исполняемый файл грейдера \texttt{grader} или \texttt{grader.exe}, в зависимости от вашей операционной системы, запустив который можно ввести тест в формате, указанном далее.

Если компиляция через команды вызывает у вас трудности, для локального тестирования вы можете скопировать реализацию функции \texttt{solve} в файл \texttt{grader.cpp} (ее необходимо вставить перед функцией \t{main}) и запустить файл \texttt{grader.cpp}. При этом перед отправкой решения в тестирующую систему вам нужно будет оставить только реализацию функции \texttt{solve}, \textbf{не забыв подключить заголовочный файл в начале кода} (это делается с помощью добавления строки \t{\#include "triangles.h"} в начало сдаваемого вами кода). Если вы используете какие либо библиотеки языка C++, их подключение также необходимо добавить в начало отправляемого кода.

\newpage

В случае получения вердикта ошибка компиляции, убедитесь, что \textbf{в отправляемом вами коде не содержится функции \t{main}, а также не содержатся определения функции \t{compare} и структуры \t{Triangle}}. Функцию \t{compare} и структуру \t{Triangle} вы можете только использовать в отправляемом вами коде.