Theofanis decided to visit his uncle's farm. There are $s$ animals and $n$ animal pens on the farm. For utility purpose, animal pens are constructed in one row.

Uncle told Theofanis that a farm is lucky if you can distribute all animals in all pens in such a way that there are no empty pens and there is at least one continuous segment of pens that has exactly $k$ animals in total.

Moreover, a farm is ideal if it's lucky for any distribution without empty pens.

Neither Theofanis nor his uncle knows if their farm is ideal or not. Can you help them to figure it out?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases.

The first and only line of each test case contains three integers $s$, $n$, and $k$ ($1 \le s, n, k \le 10^{18}$; $n \le s$).


-----Output-----

For each test case, print YES (case-insensitive), if the farm is ideal, or NO (case-insensitive) otherwise.


-----Examples-----

Input
4
1 1 1
1 1 2
100 50 200
56220 47258 14497
Output
YES
NO
NO
YES


-----Note-----

For the first and the second test case, the only possible combination is $[1]$ so there always will be a subsegment with $1$ animal but not with $2$ animals.

Difficulty: VERY_HARD
Tags: Mathematics

Constructive algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(s, n, k) = map(int, input().split())
	if s < k:
		print('NO')
		continue
	if s == k:
		print('YES')
		continue
	if n == 1:
		print('NO')
		continue
	r = s - n
	if k & 1 and r >= n and ((r - n) % 2 == 0):
		print('NO')
		continue
	if n < k:
		print('NO')
		continue
	if n >= k:
		if s - n >= n // k * k:
			print('NO')
			continue
	print('YES')


T = int(input())
for t in range(T):
	(s, n, k) = map(int, input().split())
	if s == k:
		print('YES')
		continue
	s -= n
	if s >= n // k * k:
		print('NO')
	else:
		print('YES')


test = int(input())
for _ in range(test):
	(s, n, k) = map(int, input().split())
	if s < k:
		print('NO')
	elif s == k:
		print('YES')
	else:
		s -= n
		for i in range(n // k):
			s -= k
		if s >= 0:
			print('NO')
		else:
			print('YES')


import sys
readline = sys.stdin.readline
T = int(readline())
for _ in range(T):
	(S, N, K) = map(int, readline().split())
	if S == K:
		ans = 'YES'
	elif S < K:
		ans = 'NO'
	else:
		cnt = S // (2 * K) * K
		cnt += min(S % (2 * K) + 1, K)
		if cnt >= N + 1:
			ans = 'NO'
		else:
			ans = 'YES'
	print(ans)


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
a = []
(n, k) = (0, 0)
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07
x = 0
pref = []
lvl = []

def update_it(bit, i, val):
	n = len(bit)
	while i < n:
		bit[i] += val
		i += i & -i

def get_ans(bit, i):
	n = len(bit)
	tot = 0
	while i > 0:
		tot += bit[i]
		i -= i & -i
	return tot

def hnbhai(tc):
	(s, n, k) = sd()
	if s == k:
		print('YES')
		return
	if s < k:
		print('NO')
		return
	bal = s - n
	req = n // k * k
	if bal < req:
		print('YES')
		return
	print('NO')
for _ in range(sb()):
	hnbhai(_ + 1)


import sys
from sys import stdin
tt = int(stdin.readline())
ANS = []
for loop in range(tt):
	(s, n, k) = map(int, stdin.readline().split())
	use = n // k * k
	if k == s:
		ans = 'YES'
	elif use <= s - n:
		ans = 'NO'
	else:
		ans = 'YES'
	ANS.append(ans)
print('\n'.join(ANS))


def main():
	for _ in range(int(input())):
		(s, n, k) = map(int, input().split())
		if k > s:
			print('NO')
		elif s == k:
			print('YES')
		elif n == 1:
			print('NO')
		elif s == n or s == n + 1:
			print('YES')
		elif n // k * k + n <= s:
			print('NO')
		else:
			print('YES')
main()


def solve():
	(s, n, k) = map(int, input().split())
	if s == k:
		return 1
	if n < k:
		return 0
	return n // k * 2 * k + n % k > s
import sys
input = lambda : sys.stdin.readline().rstrip()
t = int(input())
ans = ['NO', 'YES']
for i in range(t):
	print(ans[solve()])


import sys
input = sys.stdin.readline
for nt in range(int(input())):
	(s, n, k) = map(int, input().split())
	if k == s:
		print('YES')
	elif k > s:
		print('NO')
	elif n + n // k * k <= s:
		print('NO')
	else:
		print('YES')


import io, os
import math
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main(t):
	(s, n, k) = map(int, input().split())
	if s < k:
		print('NO')
		return
	elif s == k:
		print('YES')
		return
	left = s % k
	right = k - left
	leftnum = s // k + 1
	rightnum = s // k
	maxleft = (leftnum // 2 + leftnum % 2) * left
	maxright = (rightnum // 2 + rightnum % 2) * right
	if rightnum % 2 == 1:
		maxright -= 1
	if n > maxleft + maxright:
		print('YES')
	else:
		print('NO')
T = int(input())
t = 1
while t <= T:
	main(t)
	t += 1


import sys
from bisect import bisect_right as lb
from collections import deque
from queue import PriorityQueue as pq
from math import gcd
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
lii = lambda : list(map(int, list(ip())))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
mod = 10 ** 9 + 7
mod1 = 998244353
for _ in range(ii()):
	(s, n, k) = il()
	if k > s:
		print('NO')
	elif k == s:
		print('YES')
	else:
		s1 = s - n
		t1 = n // k * k
		if s1 < t1:
			print('YES')
		else:
			print('NO')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(s, n, k) = map(int, input().split())
	if s < k:
		print('NO')
		continue
	if s == k:
		print('YES')
		continue
	if n == 1:
		print('NO')
		continue
	if s - n >= n // k * k:
		print('NO')
		continue
	print('YES')


import sys
input = sys.stdin.readline

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

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

def input_string():
	s = input()
	return list(s[:len(s) - 1])

def input_int_gen():
	return map(int, input().split())
tests = inp()
for _ in range(tests):
	(s, n, k) = input_int_gen()
	if s < k:
		print('NO')
		continue
	if s == k:
		print('YES')
		continue
	q = (s + 1) // k
	r = (s + 1) % k
	maxi = r * ((q + 2) // 2) + (k - r) * ((q + 1) // 2)
	print('YES' if maxi < n + 1 else 'NO')


import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
output = sys.stdout.write

def solve(S, N, K):
	if S == K:
		return 'YES\n'
	sz = S // (2 * K) * K + K
	sz -= K - min(1 + S % (2 * K), K)
	return 'NO\n' if sz >= N + 1 else 'YES\n'

def main():
	T = int(input())
	for _ in range(T):
		(S, N, K) = list(map(int, input().split()))
		out = solve(S, N, K)
		output(out)
main()