Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

There is a grid of size 10^{5} \times 10^{5}, covered completely in railway tracks. Tom is riding in a train, currently in cell (a, b), and Jerry is tied up in a different cell (c, d), unable to move. The train has no breaks. It shall move exactly K steps, and then its fuel will run out and it shall stop. In one step, the train must move to one of its neighboring cells, sharing a side. Tom can’t move without the train, as the grid is covered in tracks. Can Tom reach Jerry’s cell after exactly K steps?  

Note: Tom can go back to the same cell multiple times.

------ Input Format ------ 

- The first line contains an integer T, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, five integers a, b, c, d, K. 

------ Output Format ------ 

For each testcase, output in a single line "YES" if Tom can reach Jerry's cell in exactly K moves and "NO" if not.

You may print each character of the string in uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$0 ≤ a, b, c, d ≤ 10^{5}$
$(a, b) \ne (c, d)$
$1 ≤ K ≤ 2 \cdot 10^{5}$

------ subtasks ------ 

Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
3

1 1 2 2 2

1 1 2 3 4

1 1 1 0 3
----- Sample Output 1 ------ 
YES

NO

YES
----- explanation 1 ------ 
Test Case $1$: A possible sequence of moves is $(1, 1) \to (1, 2) \to (2, 2)$.

Test Case $2$: There is a possible sequence in $3$ moves, but not in exactly $4$ moves.

Test Case $3$: A possible sequence of moves is $(1, 1) \to (1, 0) \to (0, 0) \to (1, 0)$.

Source: codechef | Difficulty: EASY
Tags: Mathematics


Solutions:
for _ in range(int(input())):
	(a, b, c, d, k) = map(int, input().split())
	p = abs(c - a)
	q = abs(d - b)
	o = k - (p + q)
	if o % 2 == 0 and o >= 0:
		print('YES')
	else:
		print('NO')


T = int(input())
while T > 0:
	(a, b, c, d, K) = map(int, input().split())
	diff_x = a - c
	diff_y = b - d
	r1 = abs(diff_x) + abs(diff_y)
	r2 = K - r1
	if r2 % 2 == 0 and r2 >= 0:
		print('YES')
	else:
		print('NO')
	T -= 1


for i in range(int(input())):
	(a, b, c, d, k) = map(int, input().split())
	m = abs(a - c) + abs(b - d)
	if m == k:
		print('YES')
	elif (k - m) % 2 == 0 and k > m:
		print('YES')
	else:
		print('NO')


t = int(input())
for T in range(t):
	(a, b, c, d, k) = map(int, input().split())
	dist = abs(a - c) + abs(b - d)
	if dist <= k and (k - dist) % 2 == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	(a, b, c, d, k) = map(int, input().split())
	if abs(c - a) + abs(d - b) == k or (abs(c - a) + abs(d - b) < k and (k - (abs(c - a) + abs(d - b))) % 2 == 0):
		print('YES')
	else:
		print('NO')
	t -= 1


def main():
	T = int(input().strip())
	for _ in range(T):
		(a, b, c, d, K) = map(int, input().strip().split())
		x_distance = abs(c - a)
		y_distance = abs(d - b)
		if x_distance + y_distance <= K and (K - (x_distance + y_distance)) % 2 == 0:
			print('YES')
		else:
			print('NO')
main()


t = int(input())
for i in range(t):
	(a, b, c, d, k) = map(int, input().split())
	di = abs(a - c) + abs(b - d)
	if k >= di and di % 2 == k % 2:
		print('YES')
	else:
		print('NO')


import math
t = int(input())
for _ in range(t):
	(a, s, d, f, g) = map(int, input().split())
	if abs(a - d) + abs(s - f) <= g and (abs(a - d) + abs(s - f) - g) % 2 == 0:
		print('YES')
	else:
		print('NO')


a = int(input(''))
for i in range(a):
	(a, b, c, d, K) = [int(x) for x in input('').split()]
	ans = abs(c - a) + abs(d - b)
	if ans == K:
		print('YES')
	elif (K - ans) % 2 == 0 and ans < K:
		print('YES')
	else:
		print('NO')


T = int(input())
for _ in range(0, T):
	(a, b, c, d, k) = map(int, input().split())
	x = abs(c - a)
	y = abs(d - b)
	if k >= x + y:
		if (k - x - y) % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


for i in range(int(input())):
	(a, b, c, d, K) = map(int, input().split())
	x = abs(c - a)
	y = abs(d - b)
	if x + y > K:
		print('NO')
	elif (K - x + y) % 2 != 0:
		print('NO')
	else:
		print('YES')


t = int(input())
while t:
	(a, b, c, d, k) = map(int, input().split())
	x = abs(a - c)
	y = abs(b - d)
	z = k - (x + y)
	if x + y > k:
		print('NO')
	elif z % 2 != 0:
		print('NO')
	else:
		print('YES')
	t -= 1


for _ in range(int(input())):
	(a, b, c, d, K) = map(int, input().split())
	diff = abs(c - a) + abs(d - b)
	if (K - diff) % 2 == 0 and K - diff >= 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	arr = list(map(int, input().split()))
	tot_diff = abs(arr[0] - arr[2]) + abs(arr[1] - arr[3])
	if tot_diff % 2 == 0 and arr[4] % 2 == 0 and (tot_diff <= arr[4]):
		print('YES')
	elif tot_diff % 2 != 0 and arr[4] % 2 != 0 and (tot_diff <= arr[4]):
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	(a, b, c, d, k) = map(int, input().split())
	z1 = abs(a - c)
	z2 = abs(d - b)
	z = z1 + z2
	if (k - z) % 2 == 0 and k >= z:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(a, b, c, d, k) = map(int, input().split())
	count1 = abs(d - b)
	count2 = abs(a - c)
	count = count1 + count2
	if (k - count) % 2 == 0 and k >= count:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	M = input()
	L = M.split()
	K = int(L[-1])
	(a, b) = (int(L[0]), int(L[1]))
	(c, d) = (int(L[2]), int(L[3]))
	diff1 = abs(a - c)
	diff2 = abs(b - d)
	l = diff1 + diff2
	if K >= l and (K - l) % 2 == 0:
		print('YES')
	else:
		print('NO')


import math
T = int(input())
for i in range(0, T):
	(a, b, c, d, k) = map(int, input().split())
	ans = abs(a - c) + abs(b - d)
	if ans <= k:
		if ans == k:
			print('YES')
		elif k > ans and (k - ans) % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(a, b, c, d, k) = map(int, input().split())
	minDist = abs(c - a) + abs(d - b)
	if minDist > k:
		print('NO')
	elif minDist % 2 == k % 2:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	(a, b, c, d, k) = map(int, input().split())
	x = abs(a - c)
	y = abs(b - d)
	z = x + y
	if k >= z and (k - z) % 2 == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(a, b, c, d, k) = map(int, input().split())
	requried = abs(a - c) + abs(b - d)
	if requried > k or (requried - k) % 2 != 0:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	(a, b, c, d, k) = list(map(int, input().split()))
	steps_rows = max(a, c) - min(a, c)
	steps_cols = max(b, d) - min(b, d)
	min_steps = steps_rows + steps_cols
	if min_steps % 2 == 0:
		if k % 2 == 0 and k >= min_steps:
			print('YES')
		else:
			print('NO')
	elif k % 2 != 0 and k >= min_steps:
		print('YES')
	else:
		print('NO')


import math
from builtins import int
from sys import stdin, stdout
read = stdin.readline

def TomJerry(A, B, C, D, K):
	AC = abs(A - C)
	BD = abs(B - D)
	total_distance = AC + BD
	if total_distance > K:
		print('NO')
	elif total_distance == K:
		print('YES')
	else:
		remaining = total_distance - K
		if remaining % 2 == 0:
			print('YES')
		else:
			print('NO')
numbertest = int(input())
for i in range(numbertest):
	(A, B, C, D, K) = map(int, input().split())
	TomJerry(A, B, C, D, K)


for _ in range(int(input())):
	(a, b, c, d, k) = map(int, input().split())
	r1 = abs(a - c)
	r2 = abs(d - b)
	x = r1 + r2
	if x > k:
		print('NO')
	elif x == k:
		print('YES')
	else:
		rem = x - k
		if rem % 2 == 0:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	(a, b, c, d, k) = map(int, input().split())
	ac = abs(a - c)
	bd = abs(b - d)
	dis = ac + bd
	mdif = k - dis
	if dis > k:
		print('NO')
	elif dis == k:
		print('YES')
	elif mdif & 1 == 1:
		print('NO')
	else:
		print('YES')


tests = int(input())
for i in range(tests):
	(a, b, c, d, k) = map(int, input().split())
	x_gap = abs(a - c)
	y_gap = abs(b - d)
	min_required = x_gap + y_gap
	if k == min_required or (k > min_required and (k - min_required) % 2 == 0):
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	inputs = list(map(int, input().split(' ')))
	minD = abs(inputs[2] - inputs[0]) + abs(inputs[3] - inputs[1])
	if inputs[4] >= minD and minD % 2 == inputs[4] % 2:
		print('YES')
	else:
		print('NO')
	t -= 1


n = int(input())
for i in range(n):
	(a, b, c, d, k) = map(int, input().split())
	e = abs(a - c) + abs(b - d)
	if e <= k and e % 2 == k % 2:
		print('YES')
	else:
		print('NO')


test_case = int(input())
for _ in range(test_case):
	(a, b, c, d, k) = map(int, input().split(' '))
	total_dist = abs(c - a) + abs(d - b)
	if abs(total_dist - k) % 2 == 0 and k >= total_dist:
		print('YES')
	else:
		print('NO')


n = int(input())
for _ in range(n):
	(a, b, c, d, k) = map(int, input().split())
	x = abs(a - c) + abs(b - d)
	if x <= k and x % 2 == k % 2:
		print('YES')
	else:
		print('NO')


def check(a, b, c, d, K):
	ans = abs(a - c) + abs(b - d)
	if ans <= K and ans % 2 == K % 2:
		return 'YES'
	else:
		return 'NO'
K = int(input())
for i in range(K):
	(a, b, c, d, K) = map(int, input().split())
	print(check(a, b, c, d, K))


for _ in range(int(input())):
	(a, b, c, d, k) = map(int, input().split())
	distance = abs(a - c) + abs(b - d)
	if distance > k:
		print('NO')
	elif (k - distance) % 2:
		print('NO')
	else:
		print('YES')


def solve():
	(a, b, c, d, K) = map(int, input().split())
	jerry_min = abs(a - c) + abs(b - d)
	if K == jerry_min:
		print('YES')
	elif K > jerry_min and abs(K - jerry_min) % 2 == 0:
		print('YES')
	else:
		print('NO')
for _ in range(int(input())):
	solve()


for i in range(int(input())):
	(a, b, c, d, k) = list(map(int, input().split()))
	diff1 = c - a if c > a else a - c
	diff2 = d - b if d > b else b - d
	x = diff2 + diff1
	if k >= x and x % 2 == k % 2:
		print('YES')
	else:
		print('NO')


import math
for _ in range(int(input())):
	(a, b, c, d, k) = map(int, input().split())
	x = abs(a - c) + abs(b - d)
	if x <= k:
		if x == k:
			print('YES')
		elif x < k and (k - x) % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = input().split(' ')
	total = abs(int(n[0]) - int(n[2])) + abs(int(n[1]) - int(n[3]))
	road = int(n[4]) - total
	if road < 0 or (int(n[4]) - total) % 2 != 0:
		print('NO')
	else:
		print('YES')