Minimum Sum

2000ms

262144K

Description:

You are given a set of n vectors on a plane. For each vector you are allowed to multiply any of its coordinates by -1. Thus, each vector v_i = (x_i, y_i) can be transformed into one of the following four vectors:

v_i¹ = (x_i, y_i),
v_i² = ( - x_i, y_i),
v_i³ = (x_i, - y_i),
v_i⁴ = ( - x_i, - y_i).

You should find two vectors from the set and determine which of their coordinates should be multiplied by -1 so that the absolute value of the sum of the resulting vectors was minimally possible. More formally, you should choose two vectors v_i, v_j (1 ≤ i, j ≤ n, i ≠ j) and two numbers k₁, k₂ (1 ≤ k₁, k₂ ≤ 4), so that the value of the expression |v_i^k₁ + v_j^k₂| were minimum.

Input:

The first line contains a single integer n (2 ≤ n ≤ 10⁵). Then n lines contain vectors as pairs of integers "x_i y_i" ( - 10000 ≤ x_i, y_i ≤ 10000), one pair per line.

Output:

Print on the first line four space-separated numbers "i k₁ j k₂" — the answer to the problem. If there are several variants the absolute value of whose sums is minimum, you can print any of them.

Sample Input:

Sample Output:

3 2 4 2

Sample Input:

Sample Output:

3 4 5 4

Note:

A sum of two vectors v = (x_v, y_v) and u = (x_u, y_u) is vector s = v + u = (x_v + x_u, y_v + y_u).

An absolute value of vector v = (x, y) is number $\text{[math]}$ .

In the second sample there are several valid answers, such as:

(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).

Informação

Provedor Codeforces

Código CF120J