You have $a$ coins of value $n$ and $b$ coins of value $1$. You always pay in exact change, so you want to know if there exist such $x$ and $y$ that if you take $x$ ($0 \le x \le a$) coins of value $n$ and $y$ ($0 \le y \le b$) coins of value $1$, then the total value of taken coins will be $S$.

You have to answer $q$ independent test cases.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 10^4$) — the number of test cases. Then $q$ test cases follow.

The only line of the test case contains four integers $a$, $b$, $n$ and $S$ ($1 \le a, b, n, S \le 10^9$) — the number of coins of value $n$, the number of coins of value $1$, the value $n$ and the required total value.


-----Output-----

For the $i$-th test case print the answer on it — YES (without quotes) if there exist such $x$ and $y$ that if you take $x$ coins of value $n$ and $y$ coins of value $1$, then the total value of taken coins will be $S$, and NO otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).


-----Example-----
Input
4
1 2 3 4
1 2 3 6
5 2 6 27
3 3 5 18

Output
YES
NO
NO
YES

Difficulty: introductory

Starter code:

Solutions:
q=int(input())
for t in range(q):
    a,b,n,s=map(int,input().split())
    v=min(a*n,s//n*n)
    if s-v>b:
        print("NO")
    else:
        print("YES")

for __ in range(int(input())):
    a, b, n, s = list(map(int, input().split()))
    x = s % n
    if x > b or a * n + b < s:
        print('NO')
    else:
        print('YES')

read = lambda: [int(i) for i in input().split()]

q = int(input())

for _ in range(q):
    a, b, n, S = read()
    spend_a = min(a, S // n)
    if S - spend_a * n > b:
        print('NO')
    else:
        print('YES')

Q = int(input())

for _ in range(Q):
	a, b, n, S = list(map(int, input().split()))

	left = S - (min(a, S // n)) * n

	if left <= b:
		print("YES")
	else:
		print("NO")


for _ in range(int(input())):
    a, b, n, S = list(map(int, input().split()))
    if b >= S % n and a * n + b >= S:
        print('YES')
    else:
        print('NO')


q = int(input())
for i in range(q):
    a, b, n, s = map(int, input().split())
    k = s // n
    if k > a:
        p = a * n
    else:
        p = k * n
    if s - p > b:
        print("NO")
    else:
        print("YES")

for _ in range(int(input())):
    a,b,n,s=map(int,input().split())
    maxi=n*a  
    rem=s%n 
    z=s//n*n 
    z=min(z,a*n)
    if s-z<=b:
        print('YES')
    else:
        print('NO')

q = int(input())
for i in range(q):
    a, b, n, S = map(int, input().split())
    if a * n >= S:
        x = S // n
    else:
        x = a
    if b >= S - x * n:
        print('YES')
    else:
        print('NO')

for _ in range(int(input())):
    a, b, n, s = map(int, input().split())
    s -= min(a, s // n) * n
    if b >= s:
        print("YES")
    else:
        print("NO")

q = int(input())
while q:
    a, b, n, s = [int(x) for x in input().split()]
    s -= min((s//n), a)*n
    if s <= b:
        print('YES')
    else:
        print('NO')
    q -= 1

import sys
input = sys.stdin.readline

q=int(input())

for testcases in range(q):
    a,b,n,S=list(map(int,input().split()))

    x=S//n

    S-=min(x,a)*n

    if S<=b:
        print("YES")
    else:
        print("NO")


t=int(input())
for tt  in range(t):
	a,b,n,s=map(int,input().split())
	temp=s//n 
	aa=min(temp,a)
	s-=(n*aa)
	if b>=s:
		print("YES")
	else:
		print("NO")

n = int(input())
for _ in range(n):
    a, b, n, s = map(int, input().split())
    t = min(s//n, a)
    if b >= s - t*n: print('YES')
    else: print('NO')

q = int(input())
for qi in range(q):
    a, b, n, s = list(map(int, input().split()))
    ac = s // n
    ac = min(a, ac)
    curs = ac * n
    if s - curs <= b:
        print("YES")
    else:
        print("NO")

num = int(input())
for testcase in range(1, num+1):
    [a, b, n, S] = [int(i) for i in input().split()]
    S-=(n*min(a, S//n))
    if(S>b): print('NO')
    else: print('YES')

q = int(input())
ans = ['NO'] * q
for i in range(q):
    a, b, n, s = map(int, input().split())
    if a * n + b >= s and b >= s % n:
        ans[i] = "YES"
for x in ans:
    print(x)

t = int(input())
answer = []

for i in range (t):
    a, b, n, s = list(map(int,input().split()))
    ans = "NO"
    if a * n + b >= s:
        s %= n
        if s <= b:
            ans = "YES"
    answer.append(ans)
for i in range (t):
    print (answer[i])

q = int(input())

for __ in [0]*q:
    a,b,n,s = map(int,input().split())
    xx = min(s//n,a)
    s -= xx*n
    if s <= b:
        print('YES')
    else:
        print('NO')

t = int(input())
for _ in range(t):

    a,b,n,s = list(map(int, input().split()))
    coins = min(s//n,a)
    s = s - coins*n
    if(s<=b):
        print("YES")
    else:
        print("NO")


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int,minp().split()))

def solve():
	a,b,n,S = mints()
	d = S // n
	r = S % n
	d = min(a, d)
	print(["NO","YES"][S - d * n <= b])


for i in range(mint()):
	solve()


q = int(input())
for query in range(q):
    a,b,n,s = map(int, input().split(" "))
    if(s >= n*a):
       s = s - n*a
    else:
        s = s - ((s // n) * n)
    if s > b:
        print("NO")
    else:
        print("YES")

q=int(input())
for i in range(q):
    a,b,c,d=map(int,input().split())
    if a*c>d:
        d%=c
    else:
        d-=a*c
    print('YES' if d<=b else 'NO')