짝수 경로

길찾기는 두 지점 사이의 경로를 찾는 작업이다. GPS 내비게이션 소프트웨어에서 운전자가 추천 경로를 요청하거나, 로봇이 작업을 수행하기 위해 유효한 이동 순서를 찾아야 하는 로봇 운동 계획, 또는 한 지점에서 다른 지점으로 가는 유효한 경로를 찾아야 하는 단순한 미로 풀이 등 여러 문제에서 자주 등장한다. 이 문제는 미로 풀이와 관련이 있다.

이 문제에서 다루는 미로는 N × N 크기의 정수 행렬 A 형태이다. 각 칸의 값은 N개의 정수로 이루어진 배열 R과 C로부터 생성된다. 구체적으로, i번째 행과 j번째 열의 칸 (i, j)의 값은 Ri + Cj와 같다. 이 문제의 모든 인덱스는 1부터 N까지이다.

이 미로에서 경로는 모든 1 ≤ i < k에 대해 |ri − ri+1| + |ci − ci+1| = 1을 만족하는 칸의 나열 (r1, c1), (r2, c2), ..., (rk, ck)로 정의된다. 즉, 인접한 두 칸은 행만 1만큼 또는 열만 1만큼 다르다. 이 미로에서 짝수 경로는 경로에 포함된 모든 칸이 짝수만을 담고 있는 경로로 정의된다.

쿼리로 튜플 <ra, ca, rb, cb>가 주어지면, 칸 (ra, ca)에서 칸 (rb, cb)로 가는 짝수 경로가 존재하는지 판별하는 것이 과제이다. 문제를 단순화하기 위해 칸 (ra, ca)와 칸 (rb, cb) 모두 짝수를 담고 있음이 보장된다. 예를 들어 N = 5, R = {6, 2, 7, 8, 3}, C = {3, 4, 8, 5, 1}이라 하자. 다음 그림은 주어진 배열 R과 C로 생성된 5 × 5 행렬 A를 나타낸다.

몇 가지 쿼리를 살펴보자.

• <2, 2, 1, 3>: 칸 (2, 2)에서 칸 (1, 3)으로 가는 짝수 경로가 존재한다. 예를 들어 (2, 2), (2, 3), (1, 3)이 있다. 물론 (2, 2), (1, 2), (1, 3)도 유효한 짝수 경로이다.
• <4, 2, 4, 3>: 칸 (4, 2)에서 칸 (4, 3)으로 가는 짝수 경로가 존재한다. 즉 (4, 2), (4, 3)이다.
• <5, 1, 3, 4>: 칸 (5, 1)에서 칸 (3, 4)로 가는 짝수 경로가 존재하지 않는다. 칸 (5, 1)의 이웃한 두 칸은 (5, 2)와 (4, 1)뿐인데, 둘 다 홀수(각각 7과 11)를 담고 있으므로 칸 (5, 1)에서 출발하는 짝수 경로는 존재할 수 없다.

입력은 두 정수 N Q (2 ≤ N ≤ 100 000; 1 ≤ Q ≤ 100 000)를 포함하는 한 줄로 시작한다. 이는 각각 미로의 크기와 쿼리의 수를 나타낸다. 다음 줄은 배열 R을 나타내는 N개의 정수 Ri (0 ≤ Ri ≤ 106)를 포함한다. 다음 줄은 배열 C를 나타내는 N개의 정수 Ci (0 ≤ Ci ≤ 106)를 포함한다. 다음 Q개 줄은 각각 <ra, ca, rb, cb> 형태의 쿼리를 나타내는 네 정수 ra ca rb cb (1 ≤ ra, ca, rb, cb ≤ N)를 포함한다. (ra, ca)와 (rb, cb)는 미로 내의 서로 다른 두 칸이며 둘 다 짝수를 담고 있음이 보장된다.

각 쿼리에 대해 입력 순서대로, 칸 (ra, ca)에서 칸 (rb, cb)로 가는 짝수 경로가 존재하는지 여부를 나타내는 문자열 "YES" 또는 "NO"를 한 줄에 출력한다.