Given $n$ pairs $(a_i, b_i)$, define $f(i, j, k) = a_i b_j + a_j b_k + a_k b_i$.

We need to sort these $n$ pairs such that for any three consecutive pairs $i, i+1, i+2$ after sorting, the condition $f(i, i+1, i+2) \ge f(i+2, i+1, i)$ holds. Construct such an ordering.

Input

• $n$
• $a_1 \ b_1$
• $\dots$
• $a_n \ b_n$

Output

If a solution exists, output a permutation of $1 \sim n$ in a single line; otherwise, output $-1$.

Examples

Input 1

3
10 70
30 40
50 60

Output 1

2 3 1

Note 1

After sorting, we get $(30, 40), (50, 60), (10, 70)$. $f(1, 2, 3) = 5700$, $f(3, 2, 1) = 4700$.

Input 2

4
99 99
11 11
88 88
55 55

Output 2

2 4 3 1

Constraints

$3 \le n \le 1000$, $1 \le a_i, b_i \le 10^9$.

Subtasks