请注意该题的内存限制较为特殊。

Adamant 是一位著名的数学和编程博客作者。有一天，他终于觉得写了太多的博客，是时候去户外接触一下大自然（触碰草地）了。

Adamant 的草坪上生长着 $n$ 株草。这些草的编号从 $1$ 到 $n$。我们可以在二维平面上画出草坪和草：地面是直线 $y = 0$，草垂直向上生长。每株草可以用两个数字 $x$ 和 $y$ 来描述，意味着它可以被看作是从 $(x, 0)$ 到 $(x, y)$ 的一条垂直线段。

为了触碰草地，Adamant 将移动他的手 $m$ 次。每次他将手从坐标 $(x_1, y_1)$ 沿直线路径移动到坐标 $(x_2, y_2)$。如果线段 $(x_1, y_1) - (x_2, y_2)$ 与第 $i$ 株草所定义的线段（或其端点）相交，我们就说他的手触碰到了第 $i$ 株草。

你的任务是：对于 Adamant 的每一次移动，判断他是否触碰到了任何草。如果答案是肯定的，你还需要找出他触碰到的任意一株草的编号。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 8 \times 10^5$)。

接下来 $n$ 行中的第 $i$ 行包含两个整数 $x, y$ ($1 \le x, y \le 10^9$)，描述编号为 $i$ 的草。保证没有两株草具有相同的 $x$ 坐标。

下一行包含一个整数 $m$ ($1 \le m \le 3 \times 10^5$)。

接下来 $m$ 行中的每一行包含四个整数 $x_1, y_1, x_2, y_2$ ($1 \le x_1, y_1, x_2, y_2 \le 10^9$)，描述一次手的移动。保证 $x_1$ 和 $x_2$ 均不等于任何草的 $x$ 坐标。

输出格式

对于每一次移动，输出一行：触碰到的任意一株草的编号。如果有多个答案，输出其中任意一个即可。如果没有触碰到任何草，输出 $-1$。

样例

输入 1

3
2 3
6 4
4 5
3
1 4 7 6
7 4 1 2
1 6 1 6

输出 1

3
1
-1

说明

样例可视化：