Description

In the past, Tianyi would line up the $n$ chestnuts she bought into a row, numbered from left to right as $1,2,\cdots ,n$. The $i$-th chestnut has sweetness $a_i$ and saltiness $b_i$.

Tianyi believes that sweetness and saltiness should be balanced, so she defines a perfect pairing $(i,j)$, where $i,j$ are the indices of two chestnuts. Specifically, $(i,j)$ is called a perfect pairing if and only if $j$ is the smallest among all $j$ satisfying $i<j \leq n$ and $(a_j-b_i) \times (b_j+b_i)=a_j \times b_i + a_i \times b_j$. It is not hard to see that for a fixed $i$, the perfect pairing is uniquely determined.

Now Tianyi wants to know, for each chestnut $i$, which chestnut forms a perfect pairing with it.

Input Format

The first line contains an integer $n$, meaning Tianyi lined up $n$ chestnuts in a row.

The next $n$ lines each contain two integers $a_i$ and $b_i$, representing the sweetness and saltiness of the $i$-th chestnut, respectively.

Output Format

Output $n$ lines in total. Each line contains one integer. The $i$-th line should output the $j$ in the perfect pairing $(i,j)$ for the $i$-th chestnut.

In particular, if there is no $j$ that forms a perfect pairing with $i$, then output -1 on the $i$-th line.

5
6 8
22 8
15 4
23 4
31 4

2
-1
4
5
-1

Hint

Sample Explanation #1

For the first chestnut: $(22 - 8) \times (8 + 8) = 22 \times 8 + 6 \times 8$, so the output is $2$.

The second chestnut has no perfect pairing that satisfies the condition.

For the third chestnut: $(23 - 4) \times (4 + 4) = 23 \times 4 + 15 \times 4$, so the output is $4$.

For the fourth chestnut: $(31 - 4) \times (4 + 4) = 31 \times 4 + 23 \times 4$, so the output is $5$.

Because the fifth chestnut is the last chestnut, it has no perfect pairing that satisfies the condition.

Constraints

This problem uses bundled testdata.

• Subtask 1 (30 Points), $n \leq 10^3$.
• Subtask 2 (70 Points), $n \leq 5 \times 10^4$.

For $100\%$ of the testdata, $1 \leq n \leq 5 \times 10^4$, $1 \leq a_i \leq 10^9$, $1 \leq b_i \leq 100$.

Background (Continued)

  The taste became more and more real, and the aroma of chestnuts seemed to still linger at the tip of her nose…
  Taste? Luo Tianyi suddenly got up and walked out of the bedroom. Across a door barrier, she looked at her.
  “Are you stupid? I’m in isolation right now. What are you doing here?” With surprise and worry, Luo Tianyi suddenly burst into tears.
  Yuezheng Ling scratched her head. The warmth of the chestnuts passed through the paper bag to her palm, like a warm pack held in the hands on cold days.
  “There was an infected case on my return train, so I also need to be isolated. They asked me where my home is, and I gave them your address.”
  Yuezheng Ling peeled the shell, pinched one, and put it into the little crybaby’s mouth.
  The chestnut fragrance drifted around the corners of their mouths. “The time has to be extended again…” Tianyi muttered with slight panting, but deep down she had a bit more happy anticipation. Actually, if A-Ling was here, it was not that bad to stay in the room a little longer.
  “Ah, I’m very sorry.” Yuezheng Ling smiled softly. She did not know whether it was because of the precious time again, or because her fingers had brushed over the corner of Tianyi’s reddened lips.

Translated by ChatGPT 5