Problem:


Score : 600 points

Problem Statement

Ringo Mart, a convenience store, sells apple juice.

On the opening day of Ringo Mart, there were A cans of juice in stock in the morning.
Snuke buys B cans of juice here every day in the daytime.
Then, the manager checks the number of cans of juice remaining in stock every night.
If there are C or less cans, D new cans will be added to the stock by the next morning.

Determine if Snuke can buy juice indefinitely, that is, there is always B or more cans of juice in stock when he attempts to buy them.
Nobody besides Snuke buy juice at this store.

Note that each test case in this problem consists of T queries.

Constraints

1 \leq T \leq 300

1 \leq A, B, C, D \leq 10^{18}

All values in input are integers.

Input

Input is given from Standard Input in the following format:

T
A_1 B_1 C_1 D_1
A_2 B_2 C_2 D_2
:
A_T B_T C_T D_T

In the i-th query, A = A_i, B = B_i, C = C_i, D = D_i.

Output

Print T lines. The i-th line should contain Yes if Snuke can buy apple juice indefinitely in the i-th query; No otherwise.

Sample Input 1

14
9 7 5 9
9 7 6 9
14 10 7 12
14 10 8 12
14 10 9 12
14 10 7 11
14 10 8 11
14 10 9 11
9 10 5 10
10 10 5 10
11 10 5 10
16 10 5 10
1000000000000000000 17 14 999999999999999985
1000000000000000000 17 15 999999999999999985

Sample Output 1

No
Yes
No
Yes
Yes
No
No
Yes
No
Yes
Yes
No
No
Yes

In the first query, the number of cans of juice in stock changes as follows: (D represents daytime and N represents night.)

9
→D 2
→N 11
→D 4
→N 13
→D 6
→N 6
→D x

In the second query, the number of cans of juice in stock changes as follows:

9
→D 2
→N 11
→D 4
→N 13
→D 6
→N 15
→D 8
→N 8
→D 1
→N 10
→D 3
→N 12
→D 5
→N 14
→D 7
→N 7
→D 0
→N 9
→D 2
→N 11
→D …

and so on, thus Snuke can buy juice indefinitely.

Sample Input 2

24
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

Sample Output 2

No
No
No
No
No
No
Yes
Yes
No
No
No
No
Yes
Yes
Yes
No
No
No
Yes
Yes
Yes
No
No
No



Sample input:
14
9 7 5 9
9 7 6 9
14 10 7 12
14 10 8 12
14 10 9 12
14 10 7 11
14 10 8 11
14 10 9 11
9 10 5 10
10 10 5 10
11 10 5 10
16 10 5 10
1000000000000000000 17 14 999999999999999985
1000000000000000000 17 15 999999999999999985


Sample output:
No
Yes
No
Yes
Yes
No
No
Yes
No
Yes
Yes
No
No
Yes

Submission status: Runtime Error

Solution code:
from math import gcd
T = int(input())
for _ in range(T):
    A,B,C,D = map(int,input().split())
    if A < B or D < B:
        print('No')
    else:
        g = gcd(B,D)
        k = B//g
        r = (A-C)%B
        if r == 0:
            sm = C
        else:
            sm = C+r-B
        if sm < 0:
            print('No')
        else:
            s = sm%g
            if s + (k-1)*g <= C:
                print('Yes')
            else:
                print('No')

Submission status: Runtime Error

Solution code:
import numpy as np

def check(a,b,c,d):
    z = a
    ans = 'Yes'
    if a < b:
        ans = 'No'
        return ans
    z_list = [z]
    for k in range(100):
        x = (z - c)//b
        if x <= 0:
            x = 1
        z = z - b * x
        if z < 0:
            ans = 'No'
            break
        if z <= c:
            z += d
        
        if z in z_list:
            ans = 'Yes'
            break
        z_list.append(z)
#         print(z)
    return ans



t = int(input())
a = []
b = []
c = []
d = []
for k in range(t):
    aa,bb,cc,dd = list(map(int,input().split()))
    a.append(aa)
    b.append(bb)
    c.append(cc)
    d.append(dd)

aa = a
bb = b
cc = c
dd = d

cd_rec = []
z_rec  = []
ans_rec = []
for a,b,c,d in zip(aa,bb,cc,dd):
    
    ans,z_list = check(a,b,c,d)
    if [c,d] in cd_rec:
        
        
    cd_rec.append([c,d])
    z_rec.append(z_list)
    ans_rec.append(ans)
    
    print(ans)

Submission status: Runtime Error

Solution code:
import math


def read_ints():
    return [int(c) for c in input().split()]


def solve(a, b, c, d):
    if a < b:
        return False
    if d < b:
        return False
    if c >= b:
        return True
    e = a % b
    delta = d % b
    if delta == 0:
        return e <= c
    g = math.gcd(b, delta)
    maxv = b - g
    return maxv <= c


def main():
    n = int(input())
    for _ in range(n):
        print("Yes" if solve(*read_ints()) else "No")


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
T = int(input())
for i in range(T):
    A,B,C,D = map(int,input().split())
    if B > D:
        print('No')
    elif A < B:
        print('No')
    elif C + 1 >= B:
        print('Yes')
    else:
        r = (A-C)%math.gcd(B,C)
        if C + r >= B:
            print('Yes')
        else:
            print('No')

Submission status: Runtime Error

Solution code:
import numpy as np

t = int(input())
a = []
b = []
c = []
d = []
for k in range(t):
    aa,bb,cc,dd = list(map(int,input().split()))
    a.append(aa)
    b.append(bb)
    c.append(cc)
    d.append(dd)

aa = a
bb = b
cc = c
dd = d

a = aa[0]
b = bb[0]
c = cc[0]
d = dd[0]

for a,b,c,d in zip(aa,bb,cc,dd):
    ans = check(a,b,c,d)
    print(ans)


def check(a,b,c,d):
    z = a
    z_list = [z]
    for k in range(10000000):
        x = (z - c)//b
        if x == 0:
            x = 1
        z = z - b * x
        if z < 0:
            ans = 'No'
            break
        if z <= c:
            z += d
        
        if z in z_list:
            ans = 'Yes'
            break
        z_list.append(z)
#         print(z)
    return ans

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main(){
	LL T;
	cin >> T;
	for(int t = 0; t < T; t++){
		LL A, B, C, D;
		cin >> A >> B >> C >> D;
		if(A < B || D < B){
			cout << "No" << '\n';			
			continue;
		}
		LL r = __gcd(B,D);
		LL mult = (C + 1 - (A % r) + r - 1) / r;
		LL F = mult * r + (A % r);
		if(F >= B){
			cout << "Yes" << '\n';
		} else {
			cout << "No" << '\n';			
		}
	}
}