직선과 두 점

2차원 평면상에 M개의 직선이 있다.

직선은 두 점을 지나가는 무한히 긴 직선이며,
수직인 직선이거나, 수평인 직선이거나, 기울기가 45도로 기울어진 대각선이다.

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

이동은 반드시 x축이나 y축에 평행하게 이동해야 하는 것은 아니며, 평면공간을 벗어나서는 안되고,
시작점이나 도착점이 이미 직선 위에 있는 경우는 처음부터 이동이 불가하다.

Entrada

첫 줄에 2차원 평면의 크기를 나타내는 정수 N, 직선의 수를 나타내는 정수 M,
쿼리의 수를 나타내는 정수 Q가 공백으로 구분되어 주어진다. (2≤N≤1 000 000 000; 1≤M, Q≤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≤r_1, c_1, r_2, c_2≤N)

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

Salida

Q개의 줄에 걸쳐 답을 출력한다. i번째 줄에는 i번째 쿼리에 대한 답을 출력한다.

만약, 시작점 (r_s, c_s)에서 도착점 (r_e, c_e)로 이동이 가능하면 1, 아니면 0을 출력한다.

Subtarea

직선과 두 점 1s 1024MB