Manhattanstíflur

commons.wikimedia.org에서 가져온 이미지

아마 이미 알고 있겠지만, Manhattan의 모든 도로는 남북 방향이나 동서 방향으로 놓여 있다. 남북 방향으로 뻗은 도로에 $0, 1, \dots, n$의 번호를 붙이되, $0$이 가장 서쪽에 있는 도로라고 하자. 또한 동서 방향으로 뻗은 도로에 $0, 1, \dots, m$의 번호를 붙이되, $0$이 가장 북쪽에 있는 도로라고 하자. 그러면 교차로를 그 교차로를 이루는 도로의 번호로 나타낼 수 있으며, 그 범위는 $(0, 0)$부터 $(n, m)$까지이다. 도로를 따라 이동하여 북서쪽 모퉁이 $(0, 0)$에서 남동쪽 모퉁이 $(n, m)$까지 갈 수 있는지에 관심이 있다. 문제는 공사나 다른 문제로 인해 도로 구간이 종종 폐쇄된다는 점이다. 이러한 폐쇄로 인해 $(0, 0)$에서 $(n, m)$까지 가는 모든 경로가 언제 차단되는지 답할 수 있는가?

채점

그룹 | 점수 | 제한 조건

1 | 10 | $n = 1$, $m, q \leq 500$

2 | 10 | $n = 2$, $m, q \leq 500$

3 | 20 | $n, m, q \leq 500$

4 | 30 | $n, m, q \leq 5\,000$

5 | 30 | $n, m \leq 10^9$, $q \leq 5 \cdot 10^5$

입력의 첫째 줄에는 하나의 양의 정수 $q$가 주어진다. 다음 줄에는 양의 정수 두 개 $n, m$가 주어지며, 이는 각 방향의 도로 수를 나타낸다. 마지막으로 폐쇄되는 도로 구간에 관한 정보가 각각 담긴 $q$개의 줄이 주어진다. 각 줄에는 $0 \leq x_1, x_2 \leq n$과 $0 \leq y_1, y_2 \leq m$를 만족하는 네 정수 $x_1, y_1, x_2, y_2$가 주어진다. 이는 교차로 $(x_1, y_1)$에서 교차로 $(y_1, y_2)$까지의 도로 구간이 폐쇄된다는 뜻이다. 이 두 교차로는 항상 서로 인접한다.

$i$번 질의로 인해 $(0, 0)$에서 $(n, m)$까지 가는 모든 경로가 차단된다면 $i$를 출력한다. 모든 질의가 처리된 후에도 $(0, 0)$에서 $(n, m)$까지 이동할 수 있다면 대신 $-1$를 출력한다.