Even Path

题意翻译

给你两列长度为 $n$ 的数列 $R$ 和 $C$。用它们构造大小为 $n \times n$ 的网格，网格 $(i,j)$ 中的数字为 $R_i+C_j$。 共有 $q$ 次询问，每次给出起点和终点坐标，问是否存在从起点到终点的合法路径。 - 合法路径定义为：路径上所有网格的数字必须为偶数。 保证起点和终点网格的数字为偶数。

题目描述

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

输入输出样例

输入样例 #1

5 3
6 2 7 8 3
3 4 8 5 1
2 2 1 3
4 2 4 3
5 1 3 4

输出样例 #1

YES
YES
NO

输入样例 #2

3 2
30 40 49
15 20 25
2 2 3 3
1 2 2 2

输出样例 #2

NO
YES

说明

Explanation for the sample input/output #1 This is the example from the problem description.