Even Path

Pathfinding is the task of finding a route between two points. It appears often in many problems, for example in GPS navigation software where a driver can query for a suggested route, in robot motion planning where the robot should find a valid sequence of movements to perform some tasks, or in a simple maze solver where it should find a valid path from one point to another point. This problem is related to solving a maze.

The maze in this problem has the form of an N × N matrix of integers A. The value of each cell is generated from a given array R and C of N integers each. Specifically, the value at the ith row and jth column, cell (i, j), is Ri + Cj. All indexes in this problem run from 1 to N.

A path in this maze is a sequence of cells (r1, c1), (r2, c2), ..., (rk, ck) such that |ri − ri+1| + |ci − ci+1| = 1 for all 1 ≤ i < k. In other words, each adjacent cell differs by only 1 row or only 1 column. An even path in this maze is a path in which all the cells in the path contain only even numbers.

Given a tuple <ra, ca, rb, cb> as a query, your task is to determine whether there exists an even path from cell (ra, ca) to cell (rb, cb). To simplify the problem, it is guaranteed that both cell (ra, ca) and cell (rb, cb) contain even numbers. For example, let N = 5, R = {6, 2, 7, 8, 3}, and C = {3, 4, 8, 5, 1}. The following figure depicts the 5 × 5 matrix A generated from the given arrays R and C.

Consider several queries:

• <2, 2, 1, 3>: There is an even path from cell (2, 2) to cell (1, 3), for example (2, 2), (2, 3), (1, 3). Of course, (2, 2), (1, 2), (1, 3) is also a valid even path.
• <4, 2, 4, 3>: There is an even path from cell (4, 2) to cell (4, 3), namely (4, 2), (4, 3).
• <5, 1, 3, 4>: There is no even path from cell (5, 1) to cell (3, 4). The only two neighboring cells of (5, 1) are (5, 2) and (4, 1), and both contain odd numbers (7 and 11, respectively), so no even path can start at cell (5, 1).

The input begins with a line containing two integers N Q (2 ≤ N ≤ 100 000; 1 ≤ Q ≤ 100 000), representing the size of the maze and the number of queries. The next line contains N integers Ri (0 ≤ Ri ≤ 106), representing the array R. The next line contains N integers Ci (0 ≤ Ci ≤ 106), representing the array C. The next Q lines each contain four integers ra ca rb cb (1 ≤ ra, ca, rb, cb ≤ N), representing a query of <ra, ca, rb, cb>. It is guaranteed that (ra, ca) and (rb, cb) are two different cells in the maze and both contain even numbers.

For each query in the same order as the input, output on a line the string "YES" or "NO" indicating whether there exists an even path from cell (ra, ca) to cell (rb, cb).