CF1252C.Even Path

Pathfinding is a task of finding a route between two points. It often appears in many problems. For example, in a GPS navigation software where a driver can query for a suggested route, or in a robot motion planning where it should find a valid sequence of movements to do 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 considered in this problem is in the form of a matrix of integers $A$ of $N \times N$ . The value of each cell is generated from a given array $R$ and $C$ of $N$ integers each. Specifically, the value on the $i^{th}$ row and $j^{th}$ column, cell $(i,j)$ , is equal to $R_i + C_j$ . Note that all indexes in this problem are from $1$ to $N$ .

A path in this maze is defined as a sequence of cells $(r_1,c_1), (r_2,c_2), \dots, (r_k,c_k)$ such that $|r_i - r_{i+1}| + |c_i - c_{i+1}| = 1$ for all $1 \le i < k$ . In other words, each adjacent cell differs only by $1$ row or only by $1$ column. An even path in this maze is defined as a path in which all the cells in the path contain only even numbers.

Given a tuple $\langle r_a,c_a,r_b,c_b \rangle$ as a query, your task is to determine whether there exists an even path from cell $(r_a,c_a)$ to cell $(r_b,c_b)$ . To simplify the problem, it is guaranteed that both cell $(r_a,c_a)$ and cell $(r_b,c_b)$ 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 matrix $A$ of $5 \times 5$ which is generated from the given array $R$ and $C$ .

Let us consider several queries:

• $\langle 2, 2, 1, 3 \rangle$ : There is an even path from cell $(2,2)$ to cell $(1,3)$ , e.g., $(2,2), (2,3), (1,3)$ . Of course, $(2,2), (1,2), (1,3)$ is also a valid even path.
• $\langle 4, 2, 4, 3 \rangle$ : There is an even path from cell $(4,2)$ to cell $(4,3)$ , namely $(4,2), (4,3)$ .
• $\langle 5, 1, 3, 4 \rangle$ : There is no even path from cell $(5,1)$ to cell $(3,4)$ . Observe that the only two neighboring cells of $(5,1)$ are cell $(5,2)$ and cell $(4,1)$ , and both of them contain odd numbers (7 and 11, respectively), thus, there cannot be any even path originating from cell $(5,1)$ .

Input begins with a line containing two integers: $N$ $Q$ ( $2 \le N \le 100\,000$ ; $1 \le Q \le 100\,000$ ) representing the size of the maze and the number of queries, respectively. The next line contains $N$ integers: $R_i$ ( $0 \le R_i \le 10^6$ ) representing the array $R$ . The next line contains $N$ integers: $C_i$ ( $0 \le C_i \le 10^6$ ) representing the array $C$ . The next $Q$ lines each contains four integers: $r_a$ $c_a$ $r_b$ $c_b$ ( $1 \le r_a, c_a, r_b, c_b \le N$ ) representing a query of $\langle r_a, c_a, r_b, c_b \rangle$ . It is guaranteed that $(r_a,c_a)$ and $(r_b,c_b)$ are two different cells in the maze and both of them contain even numbers.

For each query in the same order as input, output in a line a string "YES" (without quotes) or "NO" (without quotes) whether there exists an even path from cell $(r_a,c_a)$ to cell $(r_b,c_b)$ .

Explanation for the sample input/output #1

This is the example from the problem description.