题目描述
最近,一个叫 _Parallelograms_ 的游戏迅速在网络上流行。游戏一开始有$N$个点,每个点的坐标互不相同。每次操作你可以选择三个不共线的点$A,B,C$,然后,画出点$D$,使得四边形$ACBD$是以$AB$为对角线的平行四边形,然后把点$C$移动到点$D$。注意这样的点$D$有且仅有一个。
虽然在一开始所有点的坐标都互不相同,但是,你可以通过若干次操作使得某些点的坐标相同。与此同时,所有点的坐标的绝对值不能超过$10^9$。
现在,请你通过最多$2500$次操作,使得最终所有点都在第一象限,或者报告不存在操作方案。请注意,你并不需要求出操作次数最少的操作方案,你只需要求出操作次数不超过$2500$且满足题目要求的方案即可。
输入输出格式
输入格式
第一行输入一个整数$N$,表示点的个数。
随后$N$行,每行两个整数$X_i,Y_i$,分别表示第$i$个点的横坐标和纵坐标。
输出格式
如果无解,输出一行 -1
。
否则,第一行输出一个整数$M$,表示操作次数。
随后$M$行,每行三个整数$A,B,C$,表示一次操作中选择的三个点的编号。点$C$按照题目描述部分所述规则变换,而点$A,B$不做任何变换。
输入输出样例
输入样例 #1
3
0 0
4 0
3 -1
输出样例 #1
1
1 2 3
输入样例 #2
4
5 0
0 5
-2 -2
-3 2
输出样例 #2
2
1 2 3
1 2 4
输入样例 #3
3
-1 -1
-2 -2
-3 -3
输出样例 #3
-1
说明/提示
【数据范围】
对于所有数据,$3\leqslant N\leqslant 400$,$-10\leqslant X_i,Y_i\leqslant 10$。