[Solution] Ela and Crickets solution codeforces

Ela and Crickets solution codeforces – 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.

Table of Contents

[Solution] Ela and Crickets solution codeforces

The problem, which involves a non-standard chess pieces type that is described below, reads: given 33 white crickets on a 𝑛𝑛n⋅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:

 

Ela and Crickets solution codeforces

 

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.

[Solution] Ela and Crickets solution codeforces

Each test contains multiple test cases. The first line contains the number of test cases 𝑡t (1𝑡1041≤t≤104). The description of the test cases follows.

The first line of each test case contains 𝑛n (4𝑛1054≤n≤105) — denotes the size of the chessboard.

The second line of each test case contains 6 numbers: 𝑟1r1𝑐1c1𝑟2r2𝑐2c2𝑟3r3𝑐3c3 (1𝑟1,𝑐1,𝑟2,𝑐2,𝑟3,𝑐3𝑛1≤r1,c1,r2,c2,r3,c3≤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𝑥,𝑦𝑛1≤x,y≤n) — coordinates of the target square.

Output

For each test case, print “YES” or “NO” to denotes whether Ela can put a cricket on the target square.

Example

input

[Solution] Ela and Crickets solution codeforces

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

output

Copy
YES
NO
YES
NO
YES
YES

[Solution] Ela and Crickets solution codeforces

Here’s the solution for the first test case. The red square denotes where the crickets need to reach:

For Solution

“Click Here”

Leave a Comment