The physicist Dongdong is currently studying an energy field. There are $n$ particles in this energy field, and each particle has two properties: mass $m$ and coupling coefficient $c$.

Dongdong discovered that each particle in this energy field has two poles, a North pole (N) and a South pole (S). When two particles meet, they follow the principle of "like poles repel, opposite poles attract," meaning only the N pole of one particle can be connected to the S pole of another. When the N pole of particle $a$ (with mass $m_a$ and coupling coefficient $c_a$) is directly connected to the S pole of particle $b$ (with mass $m_b$ and coupling coefficient $c_b$), a coupling energy of $m_a m_b (c_a - c_b)$ is generated.

Please solve the following two problems:

1. Among the $n$ particles in the energy field, which two particles produce the maximum energy when directly connected?
2. Dongdong has invented a method to select any $k$ particles $p_1, p_2, \dots, p_k$, connect the N pole of $p_i$ to the S pole of $p_{i+1}$ ($1 \le i < k$), and connect the N pole of $p_k$ to the S pole of $p_1$, where $p_1, p_2, \dots, p_k$ are all distinct. $k$ can be any value from $1$ to $n$. If this method is used, which particles should be selected to obtain the maximum total energy?

Input

The first line contains an integer $n$, representing the number of particles.

The next $n$ lines each contain two real numbers. The two real numbers on the $(i+1)$-th line represent the mass $m_i$ and the coupling coefficient $c_i$ of the $i$-th particle ($0 < m_i, c_i < 10^5$).

Output

The first line contains two integers $a$ and $b$, representing that connecting the N pole of particle $a$ to the S pole of particle $b$ yields the maximum energy.

The second line contains an integer $k$, representing the number of particles needed to obtain the maximum energy for the second problem.

The third line contains $k$ integers, representing $p_1, p_2, \dots, p_k$, the optimal solution for the second problem.

Examples

Input 1

4
1.0 2.0
3.0 1.0
5.0 4.0
2.0 2.0

Output 1

3 2
3
1 3 2

Note

For the first problem, connecting the N pole of the third particle to the S pole of the second particle yields an energy of $5 \times 3 \times (4 - 1) = 45$.

For the second problem, connecting particles $1, 3, 2$ in sequence yields an energy of $1 \times 5 \times (2 - 4) + 5 \times 3 \times (4 - 1) + 3 \times 1 \times (1 - 2) = 32$.

Constraints

• $10\%$ of the data: $n \le 8$
• $20\%$ of the data: $n \le 15$
• $40\%$ of the data: $n \le 1\,000$
• $50\%$ of the data: $n \le 5\,000$
• $100\%$ of the data: $n \le 50\,000$

Subtasks

This problem may have multiple solutions. If the energy produced by your solution has an absolute or relative error less than $10^{-5}$ compared to the reference answer, you will receive full marks for that part. Otherwise, you will receive no marks.

Each of the two questions accounts for $50\%$ of the score. If the format or result of either question is incorrect, you will receive no marks for that question. If one question is correct, you will receive $50\%$ of the marks for that test case; if both are correct, you will receive $100\%$ of the marks.