Alice and Bob are playing a board game. They have \(n \times n\) boards and two arrays \(a\) and \(b\) of length \(n\). The value of each cell in the \(i^{th}\) row and \(j^{th}\) row is \(a[i]+b[j]\). Alice asks \(q\) questions to Bob. In each question, Alice provides two cells \(A\) and \(B\). She asks the following questions to Bob:
Are there any paths from \(A\) to \(B\) that contains the same parity as \(A\) and \(B\).
Note: Bob can move from one cell to 8 neighbor cells in each step.
Input format
Output format
For each query, if there exists a path (for example, \(C\)) from \(A\) to \(B\) that contains the same parity as \(A\) and \(B\), then print YES. If the parity of A and B are different, then print NO.
Constraints
\(1\le n \le 10^{5}\)
\(0\leq r_i \leq 10^6\)
\(0\leq c_i \leq 10^6\)
\(1\le q \le 10^{5}\)
\(1 \leq r_1, c_1 \leq n\)
\(1 \leq r_2, c_2 \leq n\)
In the first query, we can move from $$(2, 1)$$ to $$(2, 2)$$ then to $$(3, 3)$$.
In the second query, the parity of two cells is different and therefore there isn't such a way.