题目背景

（背景改编自 百度贴吧/南北组备用吧/呆萌南北日常/F9023，作者 落墨成白）

数据已修复。

  一天又一天，每到深夜房间里又只余下手机屏幕的亮光，洛天依总会有一种与世界割离的失落感。
  闷在被子里孤独的想哭的日子里，她开始想念起哪些忙于工作带着一点点畏惧、忐忑和烦恼的小日子。
  毒辣的阳光，想出门的心，不想被晒黑的小心思交织在一起，占据心间的便是这些复杂的小情绪。
  如果可以还行要一份水果拼盘，阿绫总说她不能贪凉，所以趁着阿绫大意的时候把双手浸入打满水的水桶中，瞄着阿绫那无可奈何的眼神，心情舒爽啊。
  每到深夜回想起来仍会觉得回味无穷，可孤单一人时将水龙头拧开胳膊冲刷而过的冰凉感却寻不着那时的快乐。
  都说对生活选择短暂遗忘时，就会收获一丁点儿的快乐。
  可是为什么脑海里的那些场景却越发清晰？
  以往每逢休假，暖暖的阳光隔着玻璃照进来，阿绫就躺在摇椅上，她便可以赖在阿绫怀里软软的趴着，一个中午的就这么过去了，宛如养成系手游般堪是消磨时间的良方。
  还有街角那家糖炒栗子，拉着阿绫站在店铺门前看着油亮的栗子在翻炒机理跳着舞，被炸开的缝里透出诱人的气息。
  缠着阿绫买上几斤装好，恼人的阿绫却不肯给她，只是无比淡定地从袋子里捞出一粒，轻轻一捏，板栗便爆开了，轻轻一掰，栗子肉完完整整地出现在她的面前。这时她只需要张嘴，阿绫只会宠溺的将栗子喂到她的嘴里，只需看见她眯眼满足的表情，阿绫也会露出开心的笑。
  不禁泛起苦笑，自己还有一套对栗子的深入研究呢——

题目描述

以前，天依会把买来的 $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$，哪个栗子和它形成完美搭配？

输入格式

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

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

输出格式

输出共 $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

提示

样例解释 #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$。

题目背景 ( 续 )

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