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

It's a lockdown. You’re bored in your house and are playing golf in the hallway. 

The hallway has $N + 2$ tiles numbered from $0$ to $N+1$ from left to right. There is a hole on tile number $x$. You hit the ball standing on tile $0$. When you hit the ball, it bounces at lengths of $k$, i.e. the tiles covered by it are $0, k, 2k, \ldots$, and so on until the ball passes tile $N+1$.

If the ball doesn't enter the hole in the first trial, you try again but this time standing on the tile $N+1$. When you hit the ball, it bounces at lengths of $k$, i.e. the tiles covered by it are $(N + 1), (N + 1 - k), (N + 1 - 2k), \ldots$, and so on until the ball passes tile $0$. 

Find if the ball will enter the hole, either in its forward journey or backward journey.

Note: The input and output of this problem are large, so prefer using fast input/output methods.

------ Input ------

The first line contains an integer $T$, the number of test cases. Then the test cases follow. 
The only line of each test case contains three integers $N, x, k$. 

------ Output ------
Output in a single line, the answer, which should be "YES" if the ball enters the hole either in the forward or backward journey 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}$
$1 ≤ x, k ≤ N ≤ 10^{9}$

------  Subtasks ------
Subtask #1 (10 points): $N ≤ 10^{2}$

Subtask #2 (90 points): original constraints

----- Sample Input 1 ------ 
3
5 4 2
5 3 2
5 5 2
----- Sample Output 1 ------ 
YES
NO
NO
----- explanation 1 ------ 
In each test case, the tiles covered by the ball for $N = 5$ and $k = 2$ are $\{0, 2, 4, 6\}$ in the forward journey and $\{6, 4, 2, 0\}$ in the backward journey.

Therefore, the answer for the first test case is "YES" since the ball falls in the position of the hole at tile $4$. But the answer for test cases $2$ and $3$ is "NO" since the ball does not fall in the position of the hole.

Difficulty: EASY
Tags: Mathematics

Starter code:

Solutions:
for _ in range(int(input())):
	(n, x, k) = map(int, input().split())
	if x % k == 0 or x % k == (n + 1) % k:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	(a, b, c) = map(int, input().split())
	d = (a + 1) % c
	if b % c == 0 or b % c == d:
		print('YES')
	else:
		print('NO')


for tc in range(int(input())):
	(n, x, k) = map(int, input().split())
	l = x % k
	r = (n + 1 - x) % k
	if not l or not r:
		print('YES')
	else:
		print('NO')


x = int(input())
gtr = []
for mvx in range(0, x):
	p = str(input())
	asd = p.split(' ')
	vv = []
	for mnv in asd:
		vv.append(int(mnv))
	gtr.append(vv)
for jj in gtr:
	upr = (jj[1] + jj[2]) % jj[2]
	if upr == 0:
		print('YES')
	else:
		gte = (jj[0] - jj[1] + 1 + jj[2]) % jj[2]
		if gte == 0:
			print('YES')
		else:
			print('NO')


t = int(input())
for i in range(t):
	(n, x, k) = list(map(int, input().split()))
	if x % k == 0 or (n + 1 - x) % k == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(a, b, k) = map(int, input().split())
	print('YES' if b % k == 0 or (a + 1 - b) % k == 0 else 'NO')


t = int(input())
while t != 0:
	(n, x, k) = map(int, input().split())
	if x % k == 0 or (x - (n + 1)) % k == 0:
		print('YES')
	else:
		print('NO')
	t -= 1


for i in range(int(input())):
	(n, a, k) = map(int, input().split())
	if a % k == 0 or (n + 1 - a) % k == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, x, k) = map(int, input().split())
	res = 'NO'
	if x >= k and x % k == 0:
		res = 'YES'
	elif n + 1 - x >= k and (n + 1 - x) % k == 0:
		res = 'YES'
	print(res)


for tc in range(int(input())):
	(n, x, k) = map(int, input().split())
	if x % k == 0:
		ans = 'YES'
	elif (n + 1 - x) % k == 0:
		ans = 'YES'
	else:
		ans = 'NO'
	print(ans)


a = int(input(''))
for i in range(a):
	(N, x, k) = [int(x) for x in input('').split()]
	if x % k == 0 or (N + 1 - x) % k == 0:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	(N, P, K) = map(int, input().split())
	n1 = P / K
	ans = 'NO'
	if n1 == int(n1):
		ans = 'YES'
	else:
		n2 = (N + 1 - P) / K
		if n2 == int(n2):
			ans = 'YES'
	print(ans)


T = int(input())
for t in range(T):
	(N, x, k) = map(int, input().split(' '))
	offset = N + 1 - (N + 1) // k * k
	print('YES' if x % k == 0 or (x - offset) % k == 0 else 'NO')


for t in range(int(input())):
	(n, x, k) = map(int, input().split())
	if x % k == 0:
		print('YES')
	elif (n + 1 - x) % k == 0 and n + 1 - x != 0:
		print('YES')
	else:
		print('NO')


import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

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

def intmapinp():
	return map(int, sys.stdin.readline().split())

def strmapinp():
	return map(str, sys.stdin.readline().split())

def inp():
	return sys.stdin.readline()

def intinp():
	return int(sys.stdin.readline())

def println(n):
	return sys.stdout.write(str(n) + '\n')

def prints(n):
	return sys.stdout.write(str(n) + ' ')
for _ in range(intinp()):
	(n, x, k) = intmapinp()
	if x % k == 0 or (n + 1 - x) % k == 0:
		println('YES')
	else:
		println('NO')


t = int(input())
while t > 0:
	(a, b, c) = input().split()
	(a, b, c) = (int(a), int(b), int(c))
	sum = (a + 1) % c
	if b % c == 0 or b % c == sum:
		print('YES')
	else:
		print('NO')
	t -= 1


T = int(input())
for tc in range(T):
	(N, x, k) = list(map(int, input().split(' ')))
	if x % k == 0 or x % k == (N + 1) % k:
		print('YES')
	else:
		print('NO')


tests = int(input())
for i in range(tests):
	(n, x, k) = map(int, input().split())
	ans = 'NO'
	if x % k == 0:
		ans = 'YES'
	mod = (n + 1) % k
	if (x - mod) % k == 0:
		ans = 'YES'
	print(ans)


T = int(input())
for i in range(T):
	(N, X, K) = map(int, input().split())
	num = (N + 1) % K
	if X % K == 0 or X % K == num:
		print('YES')
	else:
		print('NO')