32766번 - 색깔 사각형과 쿼리

문제

색깔 사각형은 내부가 비어 있고 동서남북을 이루는 선분 4ドル$개가 각각 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 200,000円)$

다음 $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 200,000円)$

다음 $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$개의 줄에 걸쳐 각 쿼리의 답을 한 줄에 하나씩 출력한다.

제한

힌트