Harryxun/stf_run huggingface dataset:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import accumulate
from bisect import bisect
def main():
    n, m, k = map(int, input().split())
    a = tuple(map(int, input().split()))
    b = tuple(map(int, input().split()))

    aa = tuple(accumulate(a))
    ba = tuple(accumulate(b))
    r = 0
    for i1, aae in enumerate(aa):
        if aae > k:
            break
        else:
            time_remain = k - aae
            b_num = bisect(ba, time_remain)
            if pos:
                rtmp = i1 + 1 + b_num
            else:
                rtmp = i1 + 1
            r = max(r, rtmp)
    print(r)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from itertools import accumulate
from bisect import bisect
def main():
    n, m, k = map(int, input().split())
    a = tuple(map(int, input().split()))
    b = tuple(map(int, input().split()))

    aa = tuple(accumulate(a))
    ba = tuple(accumulate(b))
    r = 0
    for i1 in range(n):
        if aa[i1] > k:
            break
        else:
            t = bisect(ba, k - aa[i1])
            r = max(r, i1 + 1 + t)
    for j1 in range(m):
        if ba[j1] > k:
            break
        else:
            t = bisect(aa, k - ba[j1])
            r = max(r, j1 + 1 + t)
    print(r)
if __name__ == '__main__':
    main()
S = input()
eng_list = [i for i in range(97, 123)]
for i in range(len(S)):
    for j in range(len(eng_list)):
        if ord(S[i]) == eng_list[j]:
            k = j
    eng_list.pop(k)
print(chr(eng_list[0])) if len(eng_list) != 0 else print("None")

### FIXED CODE ###

S = input()
eng_list = [i for i in range(97, 123)]
for i in range(len(S)):
    for j in range(len(eng_list)):
        if ord(S[i]) == eng_list[j]:
            eng_list.pop(j)
            break
print(chr(eng_list[0])) if len(eng_list) != 0 else print("None")
n=int(raw_input())
while n:
    n-=1
    s=map(str,raw_input().split())
    if s[0][0]=='i':
        ans.insert(0,s[1])
    elif s[0][-3]=='r':
        ans.pop(0)
    elif s[0][-3]=='a':
        ans.pop(0)
    else:
        ans.remove(s[1])
for i in ans:
    print i,

### FIXED CODE ###

import sys
import collections
n=int(raw_input())
ans=collections.deque()
while n:
    n-=1
    s=sys.stdin.readline().rstrip().split(' ')
    if s[0][0]=='i':
        ans.appendleft(s[1])
    elif s[0][-3]=='r':
        ans.popleft()
    elif s[0][-3]=='a':
        ans.pop()
    else:
        try:
            ans.remove(s[1])
        except:
            pass
sys.stdout.write(' '.join(ans))
print
l =[]
s = []
for i in range(4):
  l.appned(int(input()))
if l[0] <= l[1]:
  s.appned(l[0])
else:
  s.append(l[1])
if l[2] <= l[3]:
  s.appned(l[2])
else:
  s.appned(l[3])
print(sum(s))

### FIXED CODE ###

l =[]
s = []
for i in range(4):
  l.append(int(input()))
if l[0] <= l[1]:
  s.append(l[0])
else:
  s.append(l[1])
if l[2] <= l[3]:
  s.append(l[2])
else:
  s.append(l[3])
print(sum(s))
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

p, q = [0], [0]
for i in range(n):
	p.append(p[i] + a[i])
for i in range(m):
	q.append(q[i] + b[i])

j, ans = m, 0
for i in range(N+1):
	if a[i] > k:
		break

	while b[j] > k - a[i]:
		j -= 1

	ans = max(ans, i+j)

print(ans)

### FIXED CODE ###

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

p, q = [0], [0]
for i in range(n):
	p.append(p[i] + a[i])
for i in range(m):
	q.append(q[i] + b[i])

j, ans = m, 0
for i in range(n+1):
	if p[i] > k:
		break

	while q[j] > k - p[i]:
		j -= 1

	ans = max(ans, i+j)

print(ans)
n=int(input())
h=list(map(int,input().split()))
dp=[10**6]*n
dp[0]=0
dp[1]=dp[0]+abs(h[1]-h[0])
for i in range(2,n):
    dp[i]=min((dp[i-1]+abs(h[i]-h[i-1]),(dp[i-2]+abs(h[i]-h[i-2])))
print(dp(n-1))

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
dp=[10**6]*n
dp[0]=0
dp[1]=dp[0]+abs(h[1]-h[0])
for i in range(2,n):
    dp[i]=min((dp[i-1]+abs(h[i]-h[i-1])),(dp[i-2]+abs(h[i]-h[i-2])))
print(dp[n-1])
#貪欲に埋める
from collections import deque
h,w,k = map(int,input().split( ))

s = []
ichigo = []
for i in range(h):
    si = input()
    si+="."
    s.append(si)
    for j in range(w):
        if si[j]=="#":
            ichigo.append((i,j))

Nm = [[-1]*w for _ in range(h)]

tmp = 1
for ich in ichigo:
    Nm[ich[0]][ich[1]]=tmp
    tmp += 1
#print(Nm)
for ich in ichigo:
    Q = deque()
    Q.append(ich)
    #print(ich)
    now = Nm[ich[0]][ich[1]]
    while Q:
        b,c = Q.popleft()
        for i in range(c+1,w):
            if Nm[b][i]<0:
                Nm[b][i] = now
            else:
                i-=1##
                break

        for j in range(c-1,-1,-1):
            if Nm[b][j]<0:
                Nm[b][j] = now
            else:
                j+=1##
                break
        for u in range(b+1,h):
            flag = True
            for t in range(j,i+1):
                if Nm[u][t]>=0:
                    flag = False
                    break
            if flag:
                for t in range(j,i+1):
                    Nm[u][t] = now
            else:
                break
        for u in range(b-1,-1,-1):
            flag = True
            for t in range(j,i+1):
                if Nm[u][t]>=0:
                    flag = False
                    break
            if flag:
                for t in range(j,i+1):
                    Nm[u][t] = now
            else:
                break
            
for i in range(h):
    print(*Nm[i])

### FIXED CODE ###

h,w,k = map(int, input().split())
s = []
Nm = [[0]*w for i in range(h)]
nm = 1
Q = []
empty =[]
for i in range(h):
    si = input()
    s.append(si)
    berry = False
    for j in range(w):
        if si[j]=="#":
            berry = True
            Nm[i][j]=nm
            nm+=1
            Q.append((i,j))
    if not berry:
        empty.append(i)

for i,j in Q:#横に伸ばす
    for t in range(j+1,w):
        if Nm[i][t]==0:
            Nm[i][t]=Nm[i][j]
        else:
            break
    for t in range(j-1,-1,-1):
        if Nm[i][t]==0:
            Nm[i][t]=Nm[i][j]
        else:
            break
if not empty:
    for i in range(h):
        print(*Nm[i])
    exit()
j=0###
if 0 in empty:#下から延ばす必要がある場合
    j = 0
    while empty[j]==j:
        j+=1
        if j<len(empty):
            continue
        else:
            break
    for t in range(j):
        for s in range(w):
            Nm[t][s] = Nm[j][s]
#print(j)
for i in empty[j:]:#縦下に伸ばす
    for j in range(w):
        Nm[i][j] = Nm[i-1][j]

for i in range(h):
    print(*Nm[i])
import sys
sys.setrecursionlimit(10**9)
class SegTee:
    
    def __init__(self):
        self.arr=[0]*(4*n)
    def update(self,node,start,end,index,val):
        if index <start or index>end:
            return
        
        if start==end:
            #print(node,val)
            
            self.arr[node]=val
        else:
            mid=(start+end)//2
            self.update(2*node+1,start,mid,index,val)
            self.update(2*node+2,mid+1,end,index,val)
            self.arr[node]=max(self.arr[2*node+1],self.arr[2*node+2])
            
    def query(self,node,tl,tr,l,r):
        if tl>r or tr<l:
            return 0
        elif tl>=l and tr<=r:
            return self.arr[node]
        else:    
            mid=(tr+tl)//2
            p1=self.query(2*node+1,tl,mid,l,r)
            p2=self.query(2*node+2,mid+1,tr,l,r)
            return max(p1,p2)
    
n=int(input())
hi=[int(k) for k in input().split()]
co=[int(k) for k in input().split()]
#print(hi)
#print(co)
segTree=SegTee()
dp=[0]*(n)
ans=0
for i in range(n):
  x=hi[i]
  y=segTree.query(0,0,n-1,0,x-1)
  dp[i]=y+co[i]
  ans=max(ans,dp[i])
  #print(dp[i])
  segTree.update(0,0,n-1,x-1,dp[i])
  #print(segTree.arr)
#print(dp)
print(segTree.query(0,0,n-1,0,n-1))  
      


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
class SegTee:
    
    def __init__(self):
        self.arr=[0]*(4*n)
    def update(self,node,start,end,index,val):
        if index <start or index>end:
            return
        
        if start==end:
            #print(node,val)
            
            self.arr[node]=val
        else:
            mid=(start+end)//2
            self.update(2*node+1,start,mid,index,val)
            self.update(2*node+2,mid+1,end,index,val)
            self.arr[node]=max(self.arr[2*node+1],self.arr[2*node+2])
            
    def query(self,node,tl,tr,l,r):
        if tl>r or tr<l:
            return 0
        elif tl>=l and tr<=r:
            return self.arr[node]
        else:    
            mid=(tr+tl)//2
            p1=self.query(2*node+1,tl,mid,l,r)
            p2=self.query(2*node+2,mid+1,tr,l,r)
            return max(p1,p2)
    

n = int(raw_input())
hi = list(map(int,raw_input().split()))
co= list(map(int,raw_input().split()))
#print(hi)
#print(co)
segTree=SegTee()
dp=[0]*(n)
ans=0
for i in range(n):
  x=hi[i]
  y=segTree.query(0,0,n-1,0,x-1)
  dp[i]=y+co[i]
  ans=max(ans,dp[i])
  #print(dp[i])
  segTree.update(0,0,n-1,x-1,dp[i])
  #print(segTree.arr)
#print(dp)
print(segTree.query(0,0,n-1,0,n-1))
s = input()
_list = [int(i) for i in s.split(' ')]
if sum(_list) % 2 != 0:
  print('IMPOSSIBLE')
  return
print(sum(_list) / 2)

### FIXED CODE ###

_l = input().split()
_s = sum([int(i) for i in _l])
if _s % 2 != 0:
    print('IMPOSSIBLE')
else:
    print(int(_s / 2))
import sys
while(1):
  H,W = map(int, raw_input().split())
  if H==0 and W==0:
    break
  for i in range(H):
    sys.stdout.white("#")
    for j in range(1,W-1):
      if i == 1 or i == H:
        sys.stdout.write("#")
      else:
        sys.stdout.write(".")
    sys.stdout.white("#")
    print ""
  print ""    

### FIXED CODE ###

while(1):
  H,W = map(int, raw_input().split())
  if H == 0 and W == 0:
    break
  for i in range(H):
    if i == 0 or i == H-1:
      print "#"*W
    else:
      print "#" + "."*(W-2) + "#"
  print ""
import numpy as np
N = input()
a = np.array(input().split()).astype(int)
flags = (np.diff(a) <= 0).astype(int)
result = 0
results = []
for i, flag in enumerate(flags):
    if flag == 0:
        results.append(result)
        result = 0
    elif flag == 1 and i != len(flags) - 1:
        result += 1
    else:
        result += 1
        results.append(result)
print(max(results))

### FIXED CODE ###

import numpy as np
N = input()
a = np.array(input().split()).astype(int)
flags = (np.diff(a) <= 0).astype(int)
result = 0
max_result = 0
for i, flag in enumerate(flags):
    if flag == 0:
        if result > max_result:
            max_result = result
        result = 0
    else:
        result += 1
    if i == len(flags) - 1:
        if result > max_result:
            max_result = result
print(max_result)
# -*- coding: utf-8 -*-

# スペース区切りの文字列の入力
st = input().split()

for i in range(1000):
  #切り捨て
  a = int(i * 0.08)
  b = int(i * 0.1)
  if(a == int(st[0]) and b == int(st[1])):
    print(i)
    break;
  elif(i == 999):
    print('-1')

### FIXED CODE ###

# -*- coding: utf-8 -*-

# 整数の入力
station = input()

if(station[0] != station[1] or station[0] != station[2]):
  print("Yes")
else:
  print("No")
a = int(input())
b = int(input())

X = a*b
if X%2 ==1:
    print('Odd')
else:
    print('Even')

### FIXED CODE ###

a, b = map(int, input().split())

X = a*b
if X%2 ==1:
    print('Odd')
else:
    print('Even')
# -*- coding: utf-8 -*-
import math

def mod_factorial(n):
    mod = 10**9+7

    if n < 1:
        return 1

    r = n
    for i in range(n-1):
        r = r*(i+1) % mod
    
    return r

def mod_pow(n,m):

    mod = 10**9+7
    r = 1

    while m > 0:
        if m & 1:
            r = r*n % mod
        n = n * n % mod
        m = m>>1

    return(r)



def mod_comb(n, k):
    mod = 10**9+7

    if n+k < 1:
        return 1
    
    a = mod_factorial(n)
    b = mod_pow(mod_factorial(k), mod-2)
    c = mod_pow(mod_factorial(n-k), mod-2)


    return (a * ((b * c) % mod)) % mod


a, b= map(int, input().split())

t = [a,b]

r = 0
mod = 10**9+7

x = (2*a-b)
y = (2*b-a)

if (x%3 == 0 and y%3 == 0) and (x > 0 and y > 0):
    m = int(x/3)
    n = int((y/3)

    r += mod_comb(n+m,m)

print(r)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import math

def mod_factorial(n):
    mod = 10**9+7

    if n < 1:
        return 1

    r = n
    for i in range(n-1):
        r = r*(i+1) % mod
    
    return r

def mod_pow(n,m):

    mod = 10**9+7
    r = 1

    while m > 0:
        if m & 1:
            r = r*n % mod
        n = n * n % mod
        m = m>>1

    return(r)



def mod_comb(n, k):
    mod = 10**9+7

    if n+k < 1:
        return 1
    
    a = mod_factorial(n)
    b = mod_pow(mod_factorial(k), mod-2)
    c = mod_pow(mod_factorial(n-k), mod-2)


    return (a * ((b * c) % mod)) % mod


a, b= map(int, input().split())

t = [a,b]

r = 0
mod = 10**9+7

x = (2*a-b)
y = (2*b-a)

if x%3 == 0 and y%3 == 0 and x*y >=0:
    m = int(x/3)
    n = int(y/3)

    r += mod_comb(n+m,m)

print(r)
n,m=map(int,input().split())
a=[]
for i in range(m):
    x=int(input())
    if a:
        if x!=a[-1]:
            a.append(x)
    else:
        a.append(x)
count=[0]*(n+2)
count[1]=2
count[0]=1
i=0
s=a.pop(0)
if s==1:
    count[1]=1
    count[0]=0
    if a:
        s=a.pop(0)
if s==2:
    count[1]=0
    if a:
        s=a.pop(0)

while i<n:        
    if (i+2==s-1):
        i=i+1
        if a:
            s=a.pop(0)
    else:
        count[i+2]=(count[i]+count[i+1])%1000000007
        i=i+1
#print(count)
print(count[n-1])

### FIXED CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
    x=int(input())
    if a:
        if x!=a[-1]:
            a.append(x)
    else:
        a.append(x)
count=[0]*(n+2)
count[1]=2
count[0]=1
i=0
s=0
if a:
    s=a.pop(0)
if s==1:
    count[1]=1
    count[0]=0
    if a:
        s=a.pop(0)
if s==2:
    count[1]=0
    if a:
        s=a.pop(0)

while i<n:        
    if (i+2==s-1):
        i=i+1
        if a:
            s=a.pop(0)
    else:
        count[i+2]=(count[i]+count[i+1])%1000000007
        i=i+1
#print(count)
print(count[n-1])
#include <bits/stdc++.h>
using namespace std;
struct _I { _I() {cin.tie(0);ios::sync_with_stdio(false);}} __I;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
#define all(a) begin(a),end(a)
template<class F, class S> istream& operator >> (istream& s, pair<F, S>& p)
{ cin >> p.first >> p.second; return s;}
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
template<class T> void cout_h(const vector<T>& c, int n=INT_MAX)
{ rep(i, min(n, (int)c.size())) cout << c[i] << (i==c.size()-1?"\n":" "); }
template<class T> inline bool chmin(T& a, T b) {return a>b?a=b,true:false;}
template<class T> inline bool chmax(T& a, T b) {return a<b?a=b,true:false;}
#define D1(a) cout<<#a<<":"<<a<<"\n"
#define D2(a,b) cout<<#a<<":"<<a<<","<<#b<<":"<<b<<endl 
#define D3(a,b,c) cout<<#a<<":"<<a<<","<<#b<<":"<<b<<","<<#c<<":"<<c <<endl
#define D4(a,b,c,d) cout<<#a<<":"<<a<<","<<#b<<":"<<b<<","<<#c<<":"<<c<<","<<#d<<":"<<d<<endl 
#define MOD 1000000007

int main()
{
    ll N; cin >>N;
    vector<ll> h(N); cin >> h;
    
    vll dp(N+1, LLONG_MAX);
    dp[1] = 0;

    for (int i = 1; i < N; i++) {
        if (i + 1 <= N)
            dp[i+1] = min(dp[i+1], dp[i] + abs(h[i-1]- h[i]));
        if (i + 2 <= N)
            dp[i+2] = min(dp[i+2], dp[i] + abs(h[i-1]- h[i+1]));
    }

    cout << dp[N] << endl;
}


### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))

inf = 2**63-1
dp = [inf] * (n+1)
dp[1] = 0

for i in range(1, n):
    if i+1 <= n:
        dp[i+1] = min(dp[i+1], dp[i] + abs(h[i+1-1]-h[i-1]))
    if i+2 <= n:
        dp[i+2] = min(dp[i+2], dp[i] + abs(h[i+2-1]-h[i-1]))

print(dp[n])
N = int(input())
V = list(map(int, input().split()))
alist = []
tmp = 0

def cook(N, V):
    if N = 1
    print(V[0])
    
    else:
        V.sort()
        for i in range(0, N, 2):
            if i + 1 > N - 1:
                alist.append(V[i])
                
            else:
                tmp = (V[i] + V[i +1]) / 2
            alist.append(tmp)
            
        N = len(alist)
        V = alist
        alist = []
        cook(N, V)
        
cook(N, V)

### FIXED CODE ###

N = int(input())
v = list(map(float, input().split()))

v.sort()

r = v[0]

for i in v[1::]:
    r = (r + i) / 2

print(r)
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = 10**9+7
p = []
q = []
r = []
for i in range(N):
    if A[i] > 0:
        p.append(A[i])
    elif A[i] < 0:
        q.append(A[i])
    else:
        r.append(A[i])
p.sort()
q.sort()
P = len(p)
Q = len(q)
if P+Q < K:
    print(0)
    exit()
if P > 0:
    if P+Q == K:
        ans = 1
        for i in range(P):
            ans = ans * p[i] % m
        for i in range(Q):
            ans = ans * q[i] % m
        print(ans)
    else:
        i = K
        j = 0
        while i > P:
            i -= 2
            j += 2
            
        while i >= 0 and j < Q-1:
            if p[P-i]*p[P-i+1] < q[Q-j-1]*q[Q-j-2]:
                i -= 2
                j += 2
            else:
                break
        ans = 1
        for k in range(max(0,i)):
            ans = ans * p[P-k-1] % m
        for l in range(min(Q,j)):
            ans = ans * q[Q-l-1] % m
        print(ans)
else:
    if K % 2 == 0:
        if Q >= K:
            ans = 1
            for i in range(K):
                ans = ans * q[Q-1-i] % m
            print(ans)
        else:
            print(0)
    else:
        if len(r) > 0:
            print(0)
        else:
            ans = 1
            for i in range(K):
                ans = ans * q[Q-1-i] % m
            print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
m = 10**9+7
pos = [*filter(lambda x: x>=0, A)]
neg = [*filter(lambda x: x<0, A)]
pos.sort(reverse=True)
neg.sort()

ans = 1
i,j = 0,0# 使った数
while i+j < K:
    flag = True
    if i == len(pos):
        flag = False
    elif j == len(neg):
        flag = True
    elif pos[i] >= -neg[j]:
        flag = True
    else:
        flag = False

    if flag:
        ans = ans * pos[i] % m
        i += 1
    else:
        ans = ans * neg[j] % m
        j += 1

if j % 2 == 0 or N==K:
    print(ans)
elif len(pos) == 0:
    ans = 1
    for i in range(K):
        ans = ans * neg[len(neg)-1-i] % m
    print(ans)
else:
    flag2 = True
    if i == 0:
        flag2 = True
    elif j == 0:
        flag2 = False
    elif i == len(pos):
        flag2 = False
    elif j == len(neg):
        flag2 = True
    elif pos[i-1]*pos[i] > neg[j-1]*neg[j]:# = を抜いた
        flag2 = True
    else:
        flag2 = False

    if flag2:
        ans = ans * pow(neg[j-1],m-2,m) % m
        ans = ans * pos[i] % m
    else:
        ans = ans * pow(pos[i-1],m-2,m) % m
        ans = ans * neg[j] % m
    print(ans)
s = input()
if s == AAA :
    print("Yes")
elif s == ABB :
    print("Yes")
elif s == AAB :
    print("Yes")
elif s == ABA :
    print("Yes")
elif s == BAA :
    print("Yes")
elif s == BBA :
    print("Yes")
elif s == BAB :
    print("Yes")
else :
    print("No")

### FIXED CODE ###

s=input()
if s == "ABB" :
    print("Yes")
elif s == "AAB" :
    print("Yes")
elif s == "ABA" :
    print("Yes")
elif s == "BAA" :
    print("Yes")
elif s == "BBA" :
    print("Yes")
elif s == "BAB" :
    print("Yes")
else :
    print("No")
from queue import deque
k=input()
que=deque([i for i in range(1,10)])
for i in range(k):
    x=que.popleft()
    if x%10!=0:
        que.append(10*x+x%10-1)
    que.append(10*x+x%10)
    if que%10!=9:
        que.append(10*x+q%10+1)
print(x)


### FIXED CODE ###

from collections import deque
k=int(input())
q=deque(range(1,10))
for i in range(k):
    x=q.popleft()
    if x%10!=0:
        q.append(10*x+x%10-1)
    q.append(10*x+x%10)
    if x%10!=9:
        q.append(10*x+x%10+1)
print(x)
n = int(input())
if n >= 30:
  print('Yes')
  else:
    print('No')

### FIXED CODE ###

n = int(input())
if n >= 30:
    print('Yes')
else:
    print('No')
from collections import deque
n = int(input())
# 最終的に出力する色
colors = [-1] * n
# 重み付き無向グラフ
conns = [set() for _ in [0] * n] 

for x in range(1, n):
  v1, v2, dis = map(int, input().split())
  # (接続ノード, 重み) を加える
  conns[v1-1].add((v2-1, dis))
  conns[v2-1].add((v1-1, dis))

# BFSの為に根ノードを初期化. (基準ノード, 距離)
q = deque([(0, 0)])
# BFS開始
while q:
  v, dis, past = q.popleft()
  
  # 奇数なら1で,偶数なら0で塗る
  colors[v] = dis&1
  
  # 基準ノードから生える各エッジに対し
  for edge, w in conns[v]:
    
    # 根からここまでの距離を足しつつ,新しく探索先を追加.
    q.append((edge, dis + w))

print('\n'.join(map(str, colors)))

### FIXED CODE ###

from collections import deque
n = int(input())
# 最終的に出力する色
colors = [-1] * n
# 重み付き無向グラフ
conns = [set() for _ in [0] * n] 

for x in range(1, n):
  v1, v2, dis = map(int, input().split())
  # (接続ノード, 重み) を加える
  conns[v1-1].add((v2-1, dis))
  conns[v2-1].add((v1-1, dis))

# BFSの為に根ノードを初期化. (基準ノード, 距離, 過去のノード)
q = deque([(0, 0, -1)])
# BFS開始
while q:
  v, dis, past = q.popleft()
  
  # 奇数なら1で,偶数なら0で塗る
  colors[v] = dis&1
  
  # 基準ノードから生える各エッジに対し
  for edge, w in conns[v]:
    
    # エッジが既に調べたものなら飛ばす
    if edge == past:
      continue
    # 根からここまでの距離を足しつつ,新しく探索先を追加.
    q.append((edge, dis + w, v))

print('\n'.join(map(str, colors)))
k = int(input())

from collection import deque
queue = deque(range(1,10))
count = 0
while count < k:
  count += 1
  tmp = queue.popleft()
  tail = tmp%10
  if tail != 0:
    queue.append(10*tmp+tail-1)
  queue.append(10*tmp)
  if tail != 9:
    queue.append(10*tmp+tail+1)

print(tmp)

### FIXED CODE ###

k = int(input())

numset = {i for i in range(1,10)}
flag = False
count = len(numset)
if count >= k:
    flag = True
arr = [numset]
index = 0

while not flag:
    beforeset = arr[index]
    tmpset = set()
    for i in beforeset:
        tail = str(i)[-1]
        if tail == "0":
            tmpset.add(int(str(i)+str(0)))
            tmpset.add(int(str(i)+str(1)))
        elif tail == "9":
            tmpset.add(int(str(i)+str(8)))
            tmpset.add(int(str(i)+str(9)))
        else:
            tmpset.add(int(str(i)+str(int(tail))))
            tmpset.add(int(str(i)+str(int(tail)+1)))
            tmpset.add(int(str(i)+str(int(tail)-1)))
    count += len(tmpset)
    if count >= k:
        flag = True
    arr.append(tmpset)
    index += 1
    
totalarr = []
for tmpset in arr:
    totalarr += list(tmpset)
    
totalarr.sort()
print(totalarr[k-1])
N=int(input())
x=a//2
print(X/a)

### FIXED CODE ###

N=int(input())
x=(N+1)//2
print(x/N)
n = int(input())
k = int(input())
h = list(map(int, input().split()))

ans = 0

for i in h:
  if i >= k:
    ans += 1
print(ans)

### FIXED CODE ###

n,k = map(int, input().split())
h = list(map(int, input().split()))

ans = 0

for i in h:
  if i >= k:
    ans += 1
print(ans)
list = (input(.split(" "))
a = int(list[0])
b = int(list[1])
print(a*b, 2*(a+b))

### FIXED CODE ###

nums = input().split(" ")
a =int( nums[0])
b = int(nums[1])

print(a*b, (a+b)*2)
t=int(input())
for i in range(t):
  a,b,c,d=map(int,input().split())
  if a<b:
    print("No")
  elif d<=b:
    if d<b:
      print("No")
    else:
      if a-(a//b)*b<=c:
        if d>b+c:
          p=0
        else:
          p= (c+b-d)//(d-b) +1
        if (d+(d-b)*p)%b<=c:
          print("Yes")
        else:
          print("No")
      else:
        print("No")
  else:
    if a>b+c:
      p=0
    else:
      p= (c+b-a)//(d-b) +1
    if (a+(d-b)*p)%b<=c:
      if d>b+c:
        p=0
      else:
        p= (c+b-d)//(d-b) +1
      if (d+(d-b)*p)%b<=c:
        print("Yes")
      else:
        print("No")
    else:
      print("No")

### FIXED CODE ###

t=int(input())
def gcd(x,y):
  if y==0:
    return x
  else:
    return gcd(y,x%y)
for i in range(t):
  a,b,c,d=map(int,input().split())
  if a<b:
    print("No")
  elif b>d:
    print("No")
  elif c>b:
    print("Yes")
  else:
    if b-gcd(b,d)+a%gcd(b,d)>c:
      print("No")
    else:
      print("Yes")