운석

나로우주센터(NSC)는 우리 도시로 떨어지는 운석 $k$개를 관측했다. 센터는 이 운석이 도시의 어느 건물에 충돌하는지 알고 싶다.

먼저 2차원으로 단순화한 문제를 푼다. 도시에는 건물이 $n$개 있다. 건물은 모두 아랫변이 $x$축에 놓인 직사각형이고, 서로 겹치지 않는다. 즉 서로 다른 두 직사각형은 만나지 않는다. 직사각형에는 1번부터 $n$번까지 번호를 붙이고, 1번이 가장 왼쪽에 있다. $1 \le i < j \le n$이면 $i$번 직사각형이 $j$번 직사각형보다 왼쪽에 있다.

운석은 점으로 나타낸다. 각 운석은 정수 쌍 $(dx, dy)$로 나타내는 기울기를 따라 떨어진다. 현재 위치가 $(x, y)$이고 기울기가 $(dx, dy)$인 운석은 $(x, y)$와 $(x + dx, y + dy)$를 잇는 직선을 따라 아래로 떨어진다. 위 그림에서 운석 A와 운석 B는 둘 다 3번 건물로 향한다. 운석이 어떤 건물 경계의 한 점에 닿으면 그 즉시 폭발해 사라진다.

건물 $n$개와 운석 $k$개가 주어질 때, 운석마다 어느 건물이 피해를 입는지 구하는 프로그램을 작성하시오.

프로그램은 표준 입력으로 읽는다. 첫째 줄에 도시의 건물을 나타내는 직사각형의 개수 $n$ ($1 \le n \le 100000$)이 주어진다. 이어지는 $n$개의 줄에 직사각형이 왼쪽에서 오른쪽 순서로 한 줄에 하나씩 주어지고, 주어진 순서대로 1번부터 $n$번까지 번호가 붙는다. 각 직사각형은 정수 세 개 $x_1$, $x_2$, $h$ ($1 \le x_1 < x_2 \le 10^9$, $1 \le h < 10^9$)로 주어진다. $x_1$은 왼쪽 변의 $x$좌표, $x_2$는 오른쪽 변의 $x$좌표, $h$는 위쪽 변의 $y$좌표다. 모든 직사각형의 아랫변은 $x$축에 놓여 있고, $1 \le i < j \le n$이면 $i$번 직사각형이 $j$번 직사각형보다 왼쪽에 있다. 다음 줄에 운석의 개수 $k$ ($1 \le k \le 100000$)가 주어진다. 이어지는 $k$개의 줄에 운석이 한 줄에 하나씩 주어진다. 각 운석은 정수 네 개 $x$, $y$, $dx$, $dy$ ($1 \le x \le 10^9$, $\max\{h\} < y \le 10^9$, $-1000 \le dx \le 1000$, $-1000 \le dy \le -1$)로 주어진다. $(x, y)$는 운석의 현재 좌표, $(dx, dy)$는 운석이 떨어지는 직선의 기울기이고, $\max\{h\}$는 건물 위쪽 변의 $y$좌표 중 가장 큰 값이다.

프로그램은 표준 출력으로 쓴다. 운석마다 입력에 주어진 순서대로 정확히 한 줄씩 출력한다. 각 줄에는 그 운석이 충돌하는 건물의 번호를 출력한다. 피해를 입는 건물이 없으면 0을 출력한다.