Ela and Crickets
Contest: Dytechlab Cup 2022
Difficulty rating: 1500
Tags: constructive algorithms, games, implementation, math

Ela likes Chess a lot. During breaks, she usually challenges her co-worker in DTL to some chess games. She's not an expert at classic chess, but she's very interested in Chess variants, where she has to adapt to new rules and test her tactical mindset to win the game.

The problem, which involves a non-standard chess pieces type that is described below, reads: given $$$3$$$ white crickets on a $$$n \cdot n$$$ board, arranged in an "L" shape next to each other, there are no other pieces on the board. Ela wants to know with a finite number of moves, can she put any white cricket on the square on row $$$x$$$, column $$$y$$$?

An "L"-shape piece arrangement can only be one of the below:

For simplicity, we describe the rules for crickets on the board where only three white crickets are. It can move horizontally, vertically, or diagonally, but only to a square in some direction that is immediately after another cricket piece (so that it must jump over it). If the square immediately behind the piece is unoccupied, the cricket will occupy the square. Otherwise (when the square is occupied by another cricket, or does not exist), the cricket isn't allowed to make such a move.

See an example of valid crickets' moves on the pictures in the Note section.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains $$$n$$$ ($$$4 \le n \le 10^5$$$) — denotes the size of the chessboard.

The second line of each test case contains 6 numbers: $$$r_1$$$, $$$c_1$$$, $$$r_2$$$, $$$c_2$$$, $$$r_3$$$, $$$c_3$$$ ($$$1 \le r_1, c_1, r_2, c_2, r_3, c_3 \le n$$$) — coordinates of the crickets. The input ensures that the three crickets are arranged in an "L" shape that the legend stated.

The third line of each test case contains 2 numbers: $$$x$$$, $$$y$$$ ($$$1 \le x, y \le n$$$) — coordinates of the target square.

Output format:
For each test case, print "YES" or "NO" to denotes whether Ela can put a cricket on the target square.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Here's the solution for the first test case. The red square denotes where the crickets need to reach. Note that in chess horizontals are counted from bottom to top, as well as on this picture.

Example input:
6
8
7 2 8 2 7 1
5 1
8
2 2 1 2 2 1
5 5
8
2 2 1 2 2 1
6 6
8
1 1 1 2 2 1
5 5
8
2 2 1 2 2 1
8 8
8
8 8 8 7 7 8
4 8

Example output:
YES
NO
YES
NO
YES
YES

Editorial:
The initial configuration will have one central piece and 2 non-central pieces. The central piece is the one on the square that shares the edges with both of the 2 other squares.
As the crickets are standing next to each other, we can prove that each of them can only jump into another square with the same color of the square it's standing on. Assuming that the central piece are on the dark square, we consider 3 cases:
1. The central piece initially lies on the corner of the board (restrict the moves of the crickets): can only move pieces to squares on the edges they cover.
2. The target square is dark: we can prove that there is always a way to line up 2 pieces on the same-colored squares with the target square diagonally.
3. The target square is light: we can see that the only piece on the white square can only move 2 squares horizontally/vertically, not diagonally in any way, so if the target square x-coordinates has the same oddity as the original square x-coordinate of the light, then it's possible. Otherwise, it's not.
For the case of 2 lights, and 1 dark, use the same reasoning.
Complexity: $$$O(1)$$$