Problem Description

Recently, a game called Parallelograms has quickly become popular on the Internet. At the beginning of the game, there are $N$ points, and the coordinates of all points are pairwise distinct. In each operation, you can choose three non-collinear points $A,B,C$, and then draw a point $D$ such that the quadrilateral $ACBD$ is a parallelogram with $AB$ as a diagonal, and then move point $C$ to point $D$. Note that there is exactly one such point $D$.

Although initially all points have distinct coordinates, you may make some points share the same coordinates after several operations. At the same time, the absolute values of all coordinates must not exceed $10^9$.

Now, please use at most $2500$ operations to make all points end up in the first quadrant, or report that no valid sequence of operations exists. Note that you do not need to find a sequence with the minimum number of operations. You only need to output a sequence with no more than $2500$ operations that satisfies the requirements.

Input Format

The first line contains an integer $N$, representing the number of points.
The next $N$ lines each contain two integers $X_i,Y_i$, representing the $x$-coordinate and $y$-coordinate of the $i$-th point.

Output Format

If there is no solution, output one line -1.

Otherwise, the first line outputs an integer $M$, representing the number of operations.
The next $M$ lines each contain three integers $A,B,C$, representing the indices of the three points chosen in one operation. Point $C$ is transformed according to the rule described in the Description section, while points $A,B$ are not changed.

3
0 0
4 0
3 -1

1
1 2 3

4
5 0
0 5
-2 -2
-3 2

2
1 2 3
1 2 4

3
-1 -1
-2 -2
-3 -3

-1

Hint

Constraints

For all testdata, $3\leqslant N\leqslant 400$, $-10\leqslant X_i,Y_i\leqslant 10$.

Source

This problem is from COCI 2016-2017 CONTEST 7 T5 PARALELOGRAMI. With the original testdata settings, the full score is $140$ points.

Translated and organized by Eason_AC.

Thanks to mutton for providing the SPJ for this problem. If you have hack data, please send a private message to mutton.

Translated by ChatGPT 5