B'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 x 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), ... , (r_k,c_k) such that |r_i - r_{i+1}| + |c_i - c_{i+1}| = 1 for all 1 <= 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 x 5 which is generated from the given array R and C . Let us consider several queries: 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, respectively. The next line contains N integers: R_i$$'...