给定一个平面上的一组 n 个向量。对于每个向量,您可以将其任何坐标乘以 -1。因此,每个向量 vi = (xi, yi) 可以变换为以下四个向量之一:
- vi1 = (xi, yi),
- vi2 = ( - xi, yi),
- vi3 = (xi, - yi),
- vi4 = ( - xi, - yi)。
您应该从集合中找到两个向量,并确定其中哪个坐标应乘以 -1,以便所得向量之和的绝对值尽可能小。更正式地说,您应该选择两个向量 vi, vj (1 ≤ i, j ≤ n, i ≠ j) 和两个数字 k1, k2 (1 ≤ k1, k2 ≤ 4),使得表达式 |vik1 + vjk2| 的值是最小的。
输入
第一行包含一个整数 n (2 ≤ n ≤ 105)。然后 n 行包含向量作为整数对“xi yi”(- 10000 ≤ xi, yi ≤ 10000),每行一对。
输出
在第一行打印四个空格分隔的数字“i k1 j k2”——问题的答案。如果有多个变体的总和绝对值最小,则可以打印其中任何一个。
示例
输入 #1
5 -7 -3 9 0 -8 6 7 -8 4 -5
输出 #1
3 2 4 2
输入 #2
5 3 2 -4 7 -6 0 -8 4 5 1
输出 #2
3 4 5 4
注意
两个向量 v = (xv, yv) 和 u = (xu, yu) 之和为向量 s = v + u = (xv + xu, yv + yu)。
向量 v = (x, y) 的绝对值为数字 $$|v| = \sqrt{x^2 + y^2}$$。
在第二个示例中,有几个有效答案,例如:
(3 1 4 2), (3 1 4 4), (3 4 4 1), (3 4 4 3), (4 1 3 2), (4 1 3 4), (4 2 3 1).