这个问题与小克里斯无关。相反,它是关于登山者的(克里斯绝对不是其中之一)。
有 n 个山丘排列在一条线上,每个山丘都是垂直线段的形式,一个端点在地面上。山丘从左到右编号为 1 到 n。第 i 个山位于位置 xi ,其顶部高度为 yi 。对于每两个小山a和b,如果从b山的山顶可以看到a山的山顶,则它们的山顶由一根绳子连接起来。形式上,如果连接两个山峰顶点的线段不与任何其他山峰相交或接触,则两个山峰的顶部是连接的。使用这些绳索,登山者可以从一座山移动到另一座山。
有 m 队登山者,每队恰好由两名成员组成。第i队的第一名和第二名登山者分别位于第i个和第bi个山头的山顶。他们想在某个山顶见面。现在,两名登山者分别按照以下过程移动:
1. 如果一个登山者位于另一个登山者已经位于或最终将到达的山顶,则前一个登山者留在该山上;
2. 否则,登山者在当前山的右侧选择一座可以通过绳索到达且最右边的山,爬上这座山并继续该过程(登山者也可以攀爬山顶低于当前山的山顶)。
对于每个登山队,确定这对登山者的会合山的编号!
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 105),即山的数量。接下来的 n 行描述了山丘。其中第 i 个包含两个空格分隔的整数 xi、yi (1 ≤ xi ≤ 107; 1 ≤ yi ≤ 1011)、第 i 个山的位置和高度。山丘按 xi 的升序排列,即 xi < xj(对于 i < j)。
下一行输入包含一个整数 m (1 ≤ m ≤ 105),即球队数量。接下来的 m 行描述了团队。其中第 i 个包含两个空格分隔的整数 ai,bi (1 ≤ ai, bi ≤ n),即第 i 队登山者所在山头的编号。 ai = bi 是可能的。
输出
在一行中输出 m 个空格分隔的整数,其中第 i 个整数是第 i 个团队成员的会议山编号。
示例
输入 #1
6 1 4 2 1 3 2 4 3 6 4 7 4 3 3 1 5 6 2 3
输出 #1
5 6 3