다시 마우스 옮기기

시간 제한3초메모리 제한128 MB

요약

최대 50,000개의 축에 평행한 직사각형이 아래에서 위 순서로 쌓여 있고, 50,000번의 클릭 지점마다 그 점을 덮는 가장 위 창을 출력한 뒤 맨 위로 올린다.

난이도: 어려움10점 중 9점
유형: 세그먼트 트리, 기하, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

$R$ 개의 행과 $C$ 개의 열로 이루어진 화면이 있다 ( $1 \le R \le 10{,}000$ , $1 \le C \le 10{,}000$ ).

화면에는 $n$ 개 ( $1 \le n \le 50{,}000$ )의 직사각형 창이 있다. $i$ 번째 창은 왼쪽 위 꼭짓점 $(x_l, y_t)$ 와 오른쪽 아래 꼭짓점 $(x_r, y_b)$ 로 주어지며, $1 \le x_l < x_r \le C$ 와 $1 \le y_b < y_t \le R$ 를 만족한다 (즉, 넓이가 $0$ 인 창은 없다). 창은 경계 위의 점을 모두 포함한다. 즉, 그 창은 $x_l \le x \le x_r$ 이고 $y_b \le y \le y_t$ 인 모든 점 $(x, y)$ 로 이루어진다.

창들은 아래에서 위로 쌓인 순서대로 주어진다. 두 창이 겹치는 곳에서는 입력에서 더 뒤에 나온 창이 앞선 창 위에 그려진다 (바로 다음일 필요는 없다). 창의 번호는 입력 순서대로 $1$ 부터 $n$ 까지이다.

마우스는 화면을 클릭할 수 있다. 마우스는 $m$ 개 ( $1 \le m \le 50{,}000$ )의 명령을 받는다. 각 명령은 마우스를 위치 $(x, y)$ ( $1 \le x \le C$ , $1 \le y \le R$ )로 옮긴 뒤 그 자리를 클릭한다. 클릭하면 그 위치에서 보이는 창, 즉 그 점을 덮고 있는 창들 중 가장 위에 있는 창이 맨 위로 올라와 완전히 보이게 되고 초점을 가진 창이 된다. 그 위치에 창이 하나도 없으면 쌓인 순서는 바뀌지 않는다.

각 클릭 후, 그 클릭이 초점을 준 창의 번호를 출력하라.

입력

첫째 줄에 열의 개수 $C$ 가 주어진다. 둘째 줄에 행의 개수 $R$ 가 주어진다. 셋째 줄에 창의 개수 $n$ 이 주어진다.

다음 $n$ 개의 줄에는 각각 네 정수 $x_l$ , $y_t$ , $x_r$ , $y_b$ 가 주어지며, 이는 한 창의 왼쪽 위와 오른쪽 아래 좌표이다. 창의 번호는 이 순서대로 $1$ 부터 $n$ 까지이다.

그 다음 줄에는 정수 $m$ 이 주어진다. 다음 $m$ 개의 줄에는 각각 두 정수 $x$ 와 $y$ 가 주어지며, 이는 그 클릭에서 마우스가 옮겨 갈 새 위치이다.

출력

$m$ 개의 줄을 출력한다. $i$ 번째 줄에는 $0 \le v_i \le n$ 인 정수 $v_i$ 를 출력한다. $v_i > 0$ 이면 $i$ 번째 클릭이 창 $v_i$ 위에서 이루어져 그 창을 맨 위로 올렸다는 뜻이고, $v_i = 0$ 이면 $i$ 번째 클릭이 창이 없는 위치에서 이루어졌다는 뜻이다.

힌트

규칙을 눈으로 확인해 보자. 너비 $200$ , 높이 $100$ 화면에 세 개의 창이 있을 때, $(60, 20)$ 을 클릭하면 창 $1$ 이 맞아 맨 위로 올라간다. $(150, 90)$ 에는 창이 없으므로 $0$ 이 출력된다. $(150, 30)$ 을 클릭하면 창 $2$ 가 맞아 맨 위로 올라간다.

예제3

예제 1

입력

200
100
3
50 50 80 20
70 60 180 10
10 90 100 40
3
60 20
150 90
150 30

예상 출력

1
0
2

예제 2
입력
```
10
10
1
2 8 5 3
3
2 3
1 1
5 8
```
예상 출력
```
1
0
1
```

예제 3

입력

예상 출력