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 \lt 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)$.

路径查找（Pathfinding）是指在两点之间寻找一条路径的任务。它经常出现在许多问题中。例如，在GPS导航软件中，驾驶员可以查询推荐路线；在机器人运动规划中，机器人需要找到一系列有效的移动动作来完成某些任务；或在一个简单的迷宫求解器中，需要找到从一个点到另一个点的有效路径。本题与求解迷宫相关。

本题所考虑的迷宫是一个 $N \times N$ 的整数矩阵 $A$。每个格子的值由给定的两个长度均为 $N$ 的整数数组 $R$ 和 $C$ 生成。具体地，第 $i$ 行、第 $j$ 列（即格子 $(i,j)$）的值等于 $R_i + C_j$。注意：本题中所有下标均从 $1$ 到 $N$。

该迷宫中的一条路径定义为一组格子序列 $(r_1,c_1), (r_2,c_2), \dots, (r_k,c_k)$，满足对所有 $1 \le i < k$，均有 $|r_i - r_{i+1}| + |c_i - c_{i+1}| = 1$。换言之，任意相邻两个格子仅在行号上相差 $1$，或仅在列号上相差 $1$。该迷宫中的一条偶路径（even path） 是指路径中所有格子的值均为偶数的路径。

给定一个查询元组 $\langle r_a,c_a,r_b,c_b \rangle$，你的任务是判断是否存在一条从格子 $(r_a,c_a)$ 到格子 $(r_b,c_b)$ 的偶路径。为简化问题，保证格子 $(r_a,c_a)$ 和 $(r_b,c_b)$ 的值均为偶数。

例如，设 $N = 5$，$R = \{6, 2, 7, 8, 3\}$，$C = \{3, 4, 8, 5, 1\}$。下图展示了由给定数组 $R$ 和 $C$ 生成的 $5 \times 5$ 矩阵 $A$：

我们考虑如下几个查询：

• $\langle 2, 2, 1, 3 \rangle$：存在一条从格子 $(2,2)$ 到格子 $(1,3)$ 的偶路径，例如 $(2,2), (2,3), (1,3)$。当然，$(2,2), (1,2), (1,3)$ 也是一条合法的偶路径。
• $\langle 4, 2, 4, 3 \rangle$：存在一条从格子 $(4,2)$ 到格子 $(4,3)$ 的偶路径，即 $(4,2), (4,3)$。
• $\langle 5, 1, 3, 4 \rangle$：不存在从格子 $(5,1)$ 到格子 $(3,4)$ 的偶路径。观察可知，格子 $(5,1)$ 的两个相邻格子仅为 $(5,2)$ 和 $(4,1)$，而它们的值分别为 $7$ 和 $11$（均为奇数），因此无法从格子 $(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.

输入的第一行包含两个整数：$N$ 和 $Q$（$2 \le N \le 100\,000$；$1 \le Q \le 100\,000$），分别表示迷宫的大小和查询次数。
第二行包含 $N$ 个整数：$R_i$（$0 \le R_i \le 10^6$），表示数组 $R$。
第三行包含 $N$ 个整数：$C_i$（$0 \le C_i \le 10^6$），表示数组 $C$。
接下来的 $Q$ 行，每行包含四个整数：$r_a$ $c_a$ $r_b$ $c_b$（$1 \le r_a, c_a, r_b, c_b \le N$），表示一次关于 $\langle r_a, c_a, r_b, c_b \rangle$ 的查询。
保证 $(r_a,c_a)$ 和 $(r_b,c_b)$ 是迷宫中两个不同的格子，且这两个格子中均含有偶数。

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)$.

对于每个查询，按照输入的相同顺序，输出一行字符串“YES”（不带引号）或“NO”（不带引号），表示是否存在一条从单元格 $(r_a,c_a)$ 到单元格 $(r_b,c_b)$ 的偶路径。

Explanation for the sample input/output #1

This is the example from the problem description.

样例输入/输出 #1 的说明

这是题目描述中的示例。