색깔 사각형과 쿼리

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

요약

서로 닿지 않는 축 정렬 직사각형 N개와 각 변의 색이 주어질 때, 두 점을 잇는 경로가 반드시 거쳐야 하는 서로 다른 색의 최소 개수를 각 질의마다 구합니다.

난이도: 어려움10점 중 8점
유형: 기하, 세그먼트 트리, 비트 연산
정답자: 아직 제출이 없습니다

문제

색깔 사각형은 내부가 비어 있고, 동서남북을 이루는 네 변이 각각 $1$ , $2$ , $3$ , $4$ , $5$ , $6$ 중 하나의 색으로 칠해진 직사각형이다. 꼭짓점은 그 꼭짓점에서 만나는 두 변의 색 중 더 큰 값의 색으로 칠한다.

준혁이는 색깔 사각형 $N$ 개를 평면 위에 배치했다. 서로 다른 두 사각형의 변은 교차하지도 접하지도 않는다. 모든 변은 $x$ 축 또는 $y$ 축과 평행하다.

쿼리 $Q$ 개를 처리하자.

두 점 $(x_s, y_s)$ , $(x_e, y_e)$ 가 주어질 때, $(x_s, y_s)$ 에서 출발해 $(x_e, y_e)$ 에 도착하는 어떤 경로든 반드시 지나야 하는 사각형 변의 색은 최소 몇 종류인지 출력한다. 경로는 평면 위의 어느 점이든 자유롭게 지날 수 있다.

입력

첫째 줄에 사각형의 개수 $N$ 이 주어진다. ( $1 \leq N \leq 200000$ )

다음 $N$ 개의 줄에는 사각형의 정보를 나타내는 정수 $x_1$ , $y_1$ , $x_2$ , $y_2$ , $c_1$ , $c_2$ , $c_3$ , $c_4$ 가 공백으로 구분되어 주어진다.

왼쪽 아래 점은 $(x_1, y_1)$ , 오른쪽 위 점은 $(x_2, y_2)$ 이다. ( $-10^9 \leq x_1 < x_2 \leq 10^9$ , $-10^9 \leq y_1 < y_2 \leq 10^9$ )
$c_1$ , $c_2$ , $c_3$ , $c_4$ 는 각각 왼쪽, 위쪽, 오른쪽, 아래쪽 변의 색이다. ( $1 \leq c_i \leq 6$ )

다음 줄에 쿼리의 개수 $Q$ 가 주어진다. ( $1 \leq Q \leq 200000$ )

다음 $Q$ 개의 줄에는 쿼리 $x_s$ , $y_s$ , $x_e$ , $y_e$ 가 주어진다. 점 $(x_s, y_s)$ 와 $(x_e, y_e)$ 는 어떤 사각형의 변 위에도 있지 않다. ( $-10^9 \leq x_s, x_e, y_s, y_e \leq 10^9$ )

출력

$Q$ 개의 줄에 걸쳐 각 쿼리의 답을 한 줄에 하나씩 출력한다.

예제2

예제 1

입력

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

예상 출력

예제 2

입력

4
1 1 10 10 1 2 3 4
2 11 4 13 2 1 2 1
4 4 5 5 6 6 6 6
6 6 8 9 5 5 4 4
4
2 5 6 5
7 7 3 12
15 -1 9 9
-1 -1 5 -1

예상 출력