Description

以前，天依会把买来的 $n$ 个栗子排成一行，从左至右编号为：$1,2,\cdots ,n$，第 $i$ 颗栗子有甜度 $a_i$ 和咸度 $b_i$。

天依认为甜和咸应该进行均衡的搭配，所以她定义了一个完美搭配 $(i,j)$，其中 $i,j$ 是两个栗子的下标。具体的，称 $(i,j)$ 为一个完美搭配，当且仅当 $j$ 是所有满足 $i<j \leq n$ 并且 $(a_j-b_i) \times (b_j+b_i)=a_j \times b_i + a_i \times b_j$ 的 $j$ 中最小的一个。不难发现当 $i$ 一定，完美搭配唯一确定。

现在天依想知道，对于每个栗子 $i$，哪个栗子和它形成完美搭配？

Input Format

第一行一个整数 $n$，表示天依把 $n$ 个栗子排成了一行。

接下来 $n$ 行，每行两个整数 $a_i$ 和 $b_i$，分别表示第 $i$ 颗栗子的甜度和咸度。

Output Format

输出共 $n$ 行，每行一个整数，第 $i$ 行表示第 $i$ 颗栗子的完美搭配 $(i,j)$ 中的 $j$。

特殊地，如果不存在 $j$ 与 $i$ 形成完美搭配，那么第 $i$ 行输出一个 -1。

5
6 8
22 8
15 4
23 4
31 4

2
-1
4
5
-1

Hint

样例解释 #1

第一个栗子：$(22 - 8) \times (8 + 8) = 22 \times 8 + 6 \times 8$，所以输出为 $2$。

第二个栗子没有满足条件的完美搭配。

第三个栗子：$(23 - 4) \times (4 + 4) = 23 \times 4 + 15 \times 4$，所以输出为 $4$。

第四个栗子：$(31 - 4) \times (4 + 4) = 31 \times 4 + 23 \times 4$ ，所以输出为 $5$。

因为第五个栗子是最后一个栗子，所以没有满足条件的完美搭配。

数据范围

本题采用捆绑测试。

• Subtask 1（30 Points），$n \leq 10^3$。
• Subtask 2（70 Points），$n \leq 5 \times 10^4$。

对于 $100\%$ 的数据，$1 \leq n \leq 5 \times 10^4$，$1 \leq a_i \leq 10^9$，$1 \leq b_i \leq 100$。

题目背景 ( 续 )

  味道愈发的真实，栗子的香气仿佛仍绕在鼻尖……
  味道？洛天依猛然起身走出卧室隔着一道门栏，望着她。
  “你是不是傻？我现在在隔离呀，你来干什么？”有惊喜有忧虑洛天依骤然哭泣出声。
  乐正绫挠挠头，栗子的温热隔着纸袋传到手心，像寒冷日子里抱在手中的暖宝宝。
  “我回程的列车上有感染病例，我也需要被隔离了，他们问我家在哪里，我说了你的地址。”
  乐正绫剥开壳，捏了一颗放进小哭包的嘴里。
  栗子香在两人嘴角飘荡，“时间又得加长了啊……”天依微微喘着气嘟囔道，心底却是多了几分期待的快乐，其实如果有阿绫在的话，也不是不可以在房间多待段时间的。
  “啊，很抱歉呢。”乐正绫轻笑着。不知道是因为再次珍贵的时间，还是手指抚摸过天依泛红的唇角。