#P18162. Touching Grass

Touching Grass

Touching Grass

Adamant 的草坪上长着 nn 株草,编号 1..n1..n。把草坪画在平面上:地面是直线 y=0y=0,草竖直向上生长。第 ii 株草可以看成从 (xi,0)(x_i,0) 到 (xi,yi)(x_i,y_i) 的竖直线段。

Adamant 会移动他的手 mm 次。每次他从 (x1,y1)(x_1,y_1) 沿直线移动到 (x2,y2)(x_2,y_2)。若这条线段与第 ii 株草的线段(包括端点)相交,则称他碰到了第 ii 株草。

对每次移动,判断他是否会碰到草;若会,输出任意一株被碰到的草的编号,否则输出 -1。

输入格式

第一行一个整数 nn(1≤n≤8⋅1051\le n\le 8\cdot10^5)。

接下来 nn 行,每行两个整数 x,yx,y(1≤x,y≤1091\le x,y\le 10^9),表示一株草。保证所有草的 xx 互不相同。

下一行一个整数 mm(1≤m≤3⋅1051\le m\le 3\cdot10^5)。

接下来 mm 行,每行四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2(1≤x1,y1,x2,y2≤1091\le x_1,y_1,x_2,y_2\le10^9)。保证 x1,x2x_1,x_2 都不等于任何草的 xx。

输出格式

对每次移动输出一行:被碰到的草的编号(任意一株),若没有则输出 -1。

样例

输入:

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

输出:

3
1
-1

(第二行的答案也可以是其它被碰到的草。)