20930번 - 우주 정거장

우주 정거장은 한 개의 선분으로 구성되어 있으며, 좌표 평면상에 $N$개의 우주 정거장이 있다. 각 우주 정거장은 $1$번부터 $N$번까지 번호가 붙어 있다.

비행선은 무조건 우주 정거장에서만 출발할 수 있으며 이동하면서 만나는 우주 정거장에서만 멈출 수 있다. 경계도 우주 정거장에 포함된다. 비행선이 움직이는 방법은 3가지다.

• x축과 평행한 방향으로 이동.
• y축과 평행한 방향으로 이동.
• 우주 정거장 내에서 이동.

서로 다른 두 정거장이 주어졌을 때, 두 정거장 사이를 오갈 수 있는지에 대해서 알아보자.

첫 번째 줄에는 우주 정거장 개수 $N$과 질문의 개수 $Q$가 주어진다. ($2 \le N \le 200\,000$, $1 \le Q \le 200\,000$)

다음 $N$개의 줄에는 $i$번 우주 정거장의 양 끝점을 나타내는 $x_{i,1}$, $y_{i,1}$, $x_{i,2}$, $y_{i,2}$가 주어진다. 모든 좌표의 절댓값은 $10^9$ 이하의 정수값이다.

다음 $Q$개의 줄에 서로 다른 우주 정거장의 번호 두 개가 주어진다.

$Q$개의 줄을 출력한다. 각 줄에는 주어진 순서대로 질문에 대한 대답이 출력되어야 한다. 질문에 주어진 두 정거장 사이를 오갈 수 있는 경우 대답은 1, 그렇지 않은 경우 대답은 0이다.