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-----

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-----

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


-----Examples-----

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
Output
YES
NO
YES
NO
YES
YES


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

Difficulty: MEDIUM
Tags: Mathematics

Game theory

Implementation

Constructive algorithms

Starter code:

Solutions:
import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	(r1, c1, r2, c2, r3, c3) = map(int, inp().split())
	if r1 == r2:
		r = r1
	elif r1 == r3:
		r = r1
	elif r2 == r3:
		r = r2
	if c1 == c2:
		c = c1
	elif c1 == c3:
		c = c1
	elif c2 == c3:
		c = c2
	(x, y) = map(int, inp().split())
	if (r == 1 or r == n) and (c == 1 or c == n):
		if x == r or y == c:
			print('YES')
		else:
			print('NO')
	elif (x - r) % 2 == 0 or (y - c) % 2 == 0:
		print('YES')
	else:
		print('NO')

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import sys
input = sys.stdin.readline
from math import sqrt
for _ in range(int(input())):
	n = int(input())
	(r1, c1, r2, c2, r3, c3) = [int(i) for i in input().split()]
	(x, y) = [int(i) for i in input().split()]
	if r1 == r2 or r1 == r3:
		r = r1
	else:
		r = r2
	if c1 == c2 or c1 == c3:
		c = c1
	else:
		c = c3
	if r == 1 and c == 1:
		if x == 1 or y == 1:
			print('YES')
		else:
			print('NO')
		continue
	if r == n and c == n:
		if x == n or y == n:
			print('YES')
		else:
			print('NO')
		continue
	if r == 1 and c == n:
		if x == 1 or y == n:
			print('YES')
		else:
			print('NO')
		continue
	if r == n and c == 1:
		if x == n or y == 1:
			print('YES')
		else:
			print('NO')
		continue
	if x % 2 == r % 2 or y % 2 == c % 2:
		print('YES')
	else:
		print('NO')


import sys, math

def get_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())
t = int(sys.stdin.readline())
for t2 in range(t):
	n = int(sys.stdin.readline())
	(r1, c1, r2, c2, r3, c3) = get_ints()
	(x, y) = get_ints()
	if r1 == r2:
		row = r1
	elif r1 == r3:
		row = r1
	else:
		row = r2
	if c1 == c2:
		col = c1
	elif c1 == c3:
		col = c1
	else:
		col = c2
	if row == x or col == y:
		print('YES')
		continue
	if row == 1 and col == 1:
		print('NO')
		continue
	elif row == 1 and col == n:
		print('NO')
		continue
	elif row == n and col == n:
		print('NO')
		continue
	elif row == n and col == 1:
		print('NO')
		continue
	if abs(x - row) % 2 != 0 and abs(y - col) % 2 != 0:
		print('NO')
	else:
		print('YES')


data = [[int(input()), [int(q) for q in input().split()], [int(q) for q in input().split()]] for _ in range(int(input()))]
for q in data:
	if q[1][0] == q[1][2]:
		x = q[1][0]
	else:
		x = q[1][4]
	if q[1][1] == q[1][3]:
		y = q[1][1]
	else:
		y = q[1][5]
	if (q[2][0] % 2 == x % 2 or q[2][1] % 2 == y % 2) and (not (x == 1 and y == 1)) and (not (x == 1 and y == q[0])) and (not (x == q[0] and y == 1)) and (not (x == q[0] and y == q[0])) or q[2][0] == x or q[2][1] == y:
		print('YES')
	else:
		print('NO')


def get_white(r1, r2, r3, r4, c1, c2, c3, c4):
	if r4 != r1 and c4 != c1:
		return (r1, c1)
	if r4 != r2 and c4 != c2:
		return (r2, c2)
	return (r3, c3)

def is_stuck(white):
	if white[0] in (1, n) and white[1] in (1, n):
		return True
	return False
t = int(input())
for i in range(t):
	n = int(input())
	(r1, c1, r2, c2, r3, c3) = map(int, input().split())
	(x, y) = map(int, input().split())
	r4 = r1 ^ r2 ^ r3
	c4 = c1 ^ c2 ^ c3
	white = get_white(r1, r2, r3, r4, c1, c2, c3, c4)
	if is_stuck(white):
		if x == white[0] or y == white[1]:
			print('YES')
		else:
			print('NO')
		continue
	if (x - r4) % 2 == 0 and (y - c4) % 2 == 0:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	(r1, c1, r2, c2, r3, c3) = map(int, input().split())
	(x, y) = map(int, input().split())
	if (r1 + r2 + r3) % 2 == 0:
		r_alone = 0
	else:
		r_alone = 1
	if (c1 + c2 + c3) % 2 == 0:
		c_alone = 0
	else:
		c_alone = 1
	if x % 2 == r_alone and y % 2 == c_alone:
		print('NO')
	elif r1 + r2 + r3 == 4 and c1 + c2 + c3 == 4:
		if x == 1 or y == 1:
			print('YES')
		else:
			print('NO')
	elif r1 + r2 + r3 == 4 and c1 + c2 + c3 == 3 * n - 1:
		if x == 1 or y == n:
			print('YES')
		else:
			print('NO')
	elif r1 + r2 + r3 == 3 * n - 1 and c1 + c2 + c3 == 3 * n - 1:
		if x == n or y == n:
			print('YES')
		else:
			print('NO')
	elif r1 + r2 + r3 == 3 * n - 1 and c1 + c2 + c3 == 4:
		if x == n or y == 1:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


for jdcnnfv in range(int(input())):
	n = int(input())
	a = input().split()
	a = [int(i) for i in a]
	(x, y) = input().split()
	x = int(x)
	y = int(y)
	if a[0] == a[2] or a[0] == a[4]:
		a1 = a[0]
	else:
		a1 = a[2]
	if a[1] == a[3] or a[1] == a[5]:
		a2 = a[1]
	else:
		a2 = a[3]
	if (a1, a2) in [(1, 1), (1, n), (n, 1), (n, n)]:
		if x == a1 or y == a2:
			print('YES')
		else:
			print('NO')
	elif (x % 2, y % 2) in [(a[0] % 2, a[1] % 2), (a[2] % 2, a[3] % 2), (a[4] % 2, a[5] % 2)]:
		print('YES')
	else:
		print('NO')


def findMid(x1, y1, x2, y2, x3, y3):
	if x1 == x2 and y1 == y3 or (x1 == x3 and y1 == y2):
		return (x1, y1)
	if x2 == x1 and y2 == y3 or (x2 == x3 and y2 == y1):
		return (x2, y2)
	return (x3, y3)
for t in range(int(input())):
	n = int(input())
	(x1, y1, x2, y2, x3, y3) = list(map(int, input().split()))
	(x, y) = map(int, input().split())
	(xm, ym) = findMid(x1, y1, x2, y2, x3, y3)
	if (xm, ym) in [(1, 1), (1, n), (n, 1), (n, n)]:
		if x == xm or y == ym:
			print('YES')
		else:
			print('NO')
	elif x % 2 != xm % 2 and y % 2 != ym % 2:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	lr = [int(ii) for ii in input().split()]
	(l1, r1, l2, r2, l3, r3, l, r) = (lr[0], lr[1], lr[2], lr[3], lr[4], lr[5], 0, 0)
	xy = [int(ii) for ii in input().split()]
	(x, y) = (xy[0], xy[1])
	if (l1 == l2 or r1 == r2) and (l1 == l3 or r1 == r3):
		(l, r) = (l1, r1)
	elif (l1 == l2 or r1 == r2) and (l2 == l3 or r2 == r3):
		(l, r) = (l2, r2)
	else:
		(l, r) = (l3, r3)
	if l == 1 and r == 1 or (l == 1 and r == n) or (l == n and r == 1) or (l == n and r == n):
		if x == l or y == r:
			print('YES')
		else:
			print('NO')
		continue
	if (x + l) % 2 == 1 and (y + r) % 2 == 1:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(num, (r1, c1, r2, c2, r3, c3), (x0, y0)) = (int(input()), map(int, input().split()), map(int, input().split()))
	(r, c) = ((r1, r2, r3), (c1, c2, c3))
	print(['NO', 'YES'][x0 in r and x0 in (1, num) or (y0 in c and y0 in (1, num))] if sum((x in (1, num) for x in r + c)) == 4 else ['YES', 'NO'][x0 % 2 + sum((x % 2 for x in r)) == 2 and y0 % 2 + sum((y % 2 for y in c)) == 2])


def inp():
	return int(input())

def strng():
	return input().strip()

def jn(lst_1, l):
	return lst_1.join(map(str, l))

def strl():
	return list(input().strip())

def mul():
	return map(int, input().strip().split())

def mulf():
	return map(float, input().strip().split())

def seq():
	return list(map(int, input().strip().split()))

def ceil(lst_1):
	return int(lst_1) if lst_1 == int(lst_1) else int(lst_1) + 1

def ceildiv(lst_1, d):
	return lst_1 // d if lst_1 % d == 0 else lst_1 // d + 1
for i in range(inp()):
	n = inp()
	(a1, b1, a2, b2, a3, b3) = mul()
	(x, y) = mul()
	lst_1 = sorted([a1, a2, a3])
	lst_2 = sorted([b1, b2, b3])
	if {lst_1[1], lst_2[1]} <= {1, n}:
		print(['NO', 'YES'][x - lst_1[1] == 0 or y - lst_2[1] == 0])
	else:
		print(['NO', 'YES'][(x - lst_1[1]) % 2 == 0 or (y - lst_2[1]) % 2 == 0])


t = int(input())
for _ in range(t):
	n = int(input())
	(r1, c1, r2, c2, r3, c3) = map(int, input().split())
	(x, y) = map(int, input().split())
	if x == r1 and y == c1 or ((x == r2 and y == c2) and (x == r3 and y == c3)):
		print('YES')
		continue
	parity = ((r1 + c1) % 2 + (r2 + c2) % 2 + (r3 + c3) % 2 + 1) % 2
	r = (r1 + r2 + r3 + 1) // 3
	c = (c1 + c2 + c3 + 1) // 3
	if r == 1 and c == 1 or (r == n and c == 1) or (r == 1 and c == n) or (r == n and c == n):
		if x == r or y == c:
			print('YES')
		else:
			print('NO')
		continue
	if x % 2 == r % 2 or y % 2 == c % 2:
		print('YES')
		continue
	if (x + y) % 2 == parity:
		print('YES')
		continue
	print('NO')


def unique(a):
	for i in a:
		if a.count(i) == 1:
			return i

def non_unique(a):
	for i in a:
		if a.count(i) == 2:
			return i
t = int(input())
for _ in range(t):
	n = int(input())
	(x1, y1, x2, y2, x3, y3) = map(int, input().split())
	(xc, yc) = (unique([x1, x2, x3]), unique([y1, y2, y3]))
	(xz, yz) = (non_unique([x1, x2, x3]), non_unique([y1, y2, y3]))
	(x, y) = map(int, input().split())
	if xz in (1, n) and yz in (1, n) and (xc in (2, n - 1)) and (yc in (2, n - 1)):
		if x == xz or y == yz:
			print('YES')
		else:
			print('NO')
	elif abs(x - xc) % 2 == 0 and abs(y - yc) % 2 == 0:
		print('NO')
	else:
		print('YES')


import math
t = int(input())
for _ in range(t):
	n = int(input())
	(a, b, c, d, e, f) = map(int, input().split())
	x = [a % 2, c % 2, e % 2]
	y = [b % 2, d % 2, f % 2]
	(p, q) = map(int, input().split())
	ok = False
	for i in range(3):
		if x[i] == p % 2 and y[i] == q % 2:
			ok = True
	pairs = [(a, b), (c, d), (e, f)]
	pairs.sort()
	if pairs[0] == (1, 1) and pairs[1] == (1, 2) and (pairs[2] == (2, 1)) and (p != 1) and (q != 1):
		ok = False
	if pairs[0] == (n - 1, n) and pairs[1] == (n, n - 1) and (pairs[2] == (n, n)) and (p != n) and (q != n):
		ok = False
	if pairs[0] == (1, n - 1) and pairs[1] == (1, n) and (pairs[2] == (2, n)) and (p != 1) and (q != n):
		ok = False
	if pairs[0] == (n - 1, 1) and pairs[1] == (n, 1) and (pairs[2] == (n, 2)) and (p != n) and (q != 1):
		ok = False
	print('YES' if ok else 'NO')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = input().split()
	arr = [int(i) for i in arr]
	ss = []
	for i in range(3):
		ss.append(arr[i * 2] % 2 * 2 + arr[i * 2 + 1] % 2)
	(x, y) = input().split()
	(x, y) = (int(x), int(y))
	arr_sort = sorted(arr)
	if arr_sort[3] == 1:
		if x == 1 or y == 1:
			print('YES')
		else:
			print('NO')
	elif arr_sort[2] == n:
		if x == n or y == n:
			print('YES')
		else:
			print('NO')
	elif arr_sort[1] == 1 and arr_sort[4] == n:
		if min(arr[0], arr[2], arr[4]) == 1:
			if x == 1 or y == n:
				print('YES')
			else:
				print('NO')
		elif x == n or y == 1:
			print('YES')
		else:
			print('NO')
	else:
		s = x % 2 * 2 + y % 2
		if s in ss:
			print('YES')
		else:
			print('NO')


import math
import collections
import bisect
import heapq
from collections import deque
from math import sqrt, ceil, floor

def inp_arr():
	return list(map(int, input().strip().split(' ')))

def inp_int():
	return int(input())

def inp_str():
	return input()

def solve():
	(n,) = inp_arr()
	(r1, c1, r2, c2, r3, c3) = inp_arr()
	(x, y) = inp_arr()
	r0 = (r1 + r2 + r3 - (r1 ^ r2 ^ r3)) // 2
	c0 = (c1 + c2 + c3 - (c1 ^ c2 ^ c3)) // 2
	corners = [[1, 1], [1, n], [n, n], [n, 1]]
	if [r0, c0] in corners:
		if x == r0 or y == c0:
			print('YES')
		else:
			print('NO')
		return

	def check(x1, y1, x2, y2):
		diff1 = abs(x1 - x2)
		diff2 = abs(y1 - y2)
		if diff1 % 2 == 0 and diff2 % 2 == 0:
			return True
		return False
	if check(r1, c1, x, y) or check(r2, c2, x, y) or check(r3, c3, x, y):
		print('YES')
		return
	print('NO')
tt = inp_int()
for t in range(tt):
	solve()


import sys, os
if os.getlogin() == 'arun':
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
from collections import defaultdict
from math import comb
import math
t = int(input())

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for _ in range(t):
	n = int(input())
	lt = list(map(int, input().split()))
	d1 = defaultdict(lambda : 0)
	d2 = defaultdict(lambda : 0)
	for i in range(0, 6, 2):
		d1[lt[i]] += 1
		d2[lt[i + 1]] += 1
	x = 0
	for i in d1.keys():
		if d1[i] == 2:
			x = i
	y = 0
	for i in d2.keys():
		if d2[i] == 2:
			y = i
	(x2, y2) = map(int, input().split())
	if (x, y) not in [(1, 1), (n, n), (1, n), (n, 1)]:
		if (x2 - x) % 2 == 0 or (y2 - y) % 2 == 0:
			print('YES')
		else:
			print('NO')
	elif x2 == x or y2 == y:
		print('YES')
	else:
		print('NO')


def f(s):
	for i in range(3):
		if s[i - 1][0] != s[i - 2][0] and s[i - 1][1] != s[i - 2][1]:
			return [s[i], s[i - 1], s[i - 2]]
for _ in range(int(input())):
	n = int(input())
	tmp = list(map(int, input().split()))
	s = f([(tmp[0], tmp[1]), (tmp[2], tmp[3]), (tmp[4], tmp[5])])
	(x, y) = map(int, input().split())
	ans = ''
	if s[0] == (1, 1):
		if x == 1 or y == 1:
			ans = 'YES'
		else:
			ans = 'NO'
	elif s[0] == (n, 1):
		if x == n or y == 1:
			ans = 'YES'
		else:
			ans = 'NO'
	elif s[0] == (1, n):
		if x == 1 or y == n:
			ans = 'YES'
		else:
			ans = 'NO'
	elif s[0] == (n, n):
		if x == n or y == n:
			ans = 'YES'
		else:
			ans = 'NO'
	else:
		for i in range(3):
			s[i] = (s[i][0] % 2, s[i][1] % 2)
		s.append((x % 2, y % 2))
		if len(set(s)) == 3:
			ans = 'YES'
		else:
			ans = 'NO'
	print(ans)


from math import ceil, floor, gcd, exp, log
from functools import lru_cache, reduce
from itertools import combinations, permutations, product, combinations_with_replacement, count, cycle, tee, islice
from collections import Counter
for t in range(int(input())):
	n = int(input())
	c = [int(a) for a in input().split()]
	t = [int(a) for a in input().split()]
	k = Counter([c[0], c[2], c[4]])
	s = Counter([c[1], c[3], c[5]])
	sss = 0
	for (s, ss) in s.items():
		if ss == 2:
			sss = s
	kkk = 0
	for (s, ss) in k.items():
		if ss == 2:
			kkk = s
	if kkk == 1 and sss == 1 or (kkk == 1 and sss == n) or (kkk == n and sss == n) or (kkk == n and sss == 1):
		if t[0] == kkk or t[1] == sss:
			print('YES')
		else:
			print('NO')
		continue
	if t[0] % 2 == kkk % 2 or t[1] % 2 == sss % 2:
		print('YES')
	else:
		print('NO')