루시드의 레이저 공격을 피해라!

루시드는 레이저를 이용하여 여러분의 움직임을 방해하려고 한다.

여러분은 처음에 2차원 공간의 $(r_s, c_s)$ 위치에 있고, $(r_e, c_e)$ 위치로 이동하려고 한다. 반드시 $x$축이나 $y$축에 평행하게 이동해야 하는 것은 아님에 유의하라. 그러나 이동 과정에서 레이저를 지나갈 수는 없다. 시작점이나 도착점에 레이저가 있는 경우는 처음부터 이동이 불가능하다. 레이저는 두 점을 지나가는 무한히 긴 직선이며, 수직인 직선이거나, 수평인 직선이거나, 기울기가 45도로 기울어진 대각선이다. 루시드는 레이저를 총 $M$ 번 쏘고, 루시드가 쏜 레이저는 사라지지 않는다.

시작점 $(r_s, c_s)$와 도착점 $(r_e, c_e)$로 이루진 쿼리 $Q$ 개가 주어졌을 때, 시작점에서 도착점으로 이동 가능한지 판별하는 프로그램을 작성하라.

위 그림에서 루시드가 쏜 세 레이저는 파란 직선으로 표시되어 있고, 각각 $(3, 1)$과 $(5, 3)$을 지나는 직선, $(4, 1)$과 $(1, 4)$를 지나는 직선, $(1, 4)$와 $(5, 4)$를 지나는 직선이다. 빨간 원으로 표현된 $(2, 1)$에서 출발하여 $(1, 3)$으로 레이저를 맞지 않고 갈 수 있다. 반면, 초록색 원으로 표현된 $(3, 3)$에서 출발하여 $(2, 2)$으로 레이저를 피해서 이동하는 것은 불가능하다.

입력 형식

첫 줄에 2차원 공간의 크기를 나타내는 정수 $N$, 레이저의 수를 나타내는 정수 $M$, 쿼리의 수를 나타내는 정수 $Q$가 공백으로 구분되어 주어진다. ($2 \le N \le 1\,000\,000\,000;$ $1 \le M, Q \le 200\,000$)

이어지는 $M$ 개의 줄의 $i$ 번째 줄에는 $i$ 번째 레이저에 대한 정보를 나타내는 네 정수 $r_1$, $c_1$, $r_2$, $c_2$가 공백으로 구분되어 주어진다. 이는 $i$ 번째 레이저가 $(r_1, c_1)$과 $(r_2, c_2)$를 연결하는 직선임을 의미한다. 이때, $r_1 = r_2$, $c_1 = c_2$, $r_1 + c_1 = r_2 + c_2$, $r_1 - c_1 = r_2 - c_2$ 중 정확히 하나를 만족한다. ($1 \le r_1, c_1, r_2, c_2 \le N$)

이어지는 $Q$ 개의 줄의 $i$ 번째 줄에는 $i$ 번째 쿼리에 대한 정보를 나타내는 네 정수 $r_s$, $c_s$, $r_e$, $c_e$가 공백으로 구분되어 주어진다. ($1 \le r_s, c_s, r_e, c_e \le N;$ $(r_s, c_s) \ne (r_e, c_e)$)

출력 형식

$Q$ 개의 줄에 걸쳐 답을 출력한다. $i$ 번째 줄에는 $i$ 번째 쿼리에 대한 답을 출력한다. 만약, 시작점 $(r_s, c_s)$에서 도착점 $(r_e, c_e)$로 이동이 가능하면 1, 아니면 0을 출력한다.

예제 1

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

1
0

예제 2

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

1
0
0

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설