Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

N, K = map(int, input().split())
S = set()

MOD = 998244353
for _ in range(K):
    L, R = map(int, input().split())
    S |= set(range(L, R + 1))
# print(f'{S=}')

DP = [-1] * (N + 1)
DP[0] = 0
DP[1] = 1


def f(idx):
    ans = 0
    for s in S:
        if idx - s < 0:
            continue
        if DP[idx - s] == -1:
            DP[idx - s] = f(idx - s)
        ans += DP[idx - s]
    return ans % MOD


ans = f(N)
# print(f'{DP=}')
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
MOD = 998244353
LR = []
for _ in range(K):
    L, R = map(int, input().split())
    LR.append((L, R))
# print(f'{LR=}')

DP = [0] * (N + 1)
DP[1] = 1
S = [0] * (N + 1)

for i in range(1, len(DP)):
    for L, R in LR:
        v = S[max(i - L, 0)] - S[max(i - R - 1, 0)]
        DP[i] += v
    DP[i] %= MOD
    S[i] = (S[i - 1] + DP[i]) % MOD

# print(f'{DP=}')
# print(f'{S=}')
print(DP[-1])
### BUGGY CODE ###

import numpy as np
N,K = map(int,input().split())
people = np.array(sorted(list(map(int,input().split()))))
food = np.array(sorted(list(map(int,input().split())))[::-1])


#2分探索　Kの値で
_max = 10**12
_min = 0

while _max!=_min:
  mean = (_max+_min)//2
  # 各人が修行をする回数の配列　負の値もでる
  K_arr = people - mean//food
  K_arr = K_arr[K_arr>0]
  # 総修行回数
  _K = sum(K_arr)
  if _K > K:
    _min = mean+1
  else:
    _max = mean
    
print(_max)
  

### FIXED CODE ###

import sys
import numpy as np
readline = sys.stdin.buffer.readline

N,K = map(int,readline().split())
people = np.array(readline().split(),np.int64)
food = np.array(readline().split(),np.int64)
 
people.sort()
food.sort()
food=food[::-1]

#2分探索　Kの値で
_max = max(people)*max(food)
_min = 0

while _max>_min:
  mean = (_max+_min)//2
  # 各人が修行をする回数の配列　負の値もでる
  _K = np.maximum(0,people - mean//food).sum()
  if _K > K:
    _min = mean+1
  else:
    _max = mean
    
print(_max)
### BUGGY CODE ###

n, x, y = map(int, input().split())
dp = [[0 for _ in range(n)] for _ in range(n)]
ans = [0 for _ in range(n-1)]
for i in range(1, n):
  for j in range(i+1, n+1):
    a = min(j-i, abs(x-i)+abs(y-j)+1, abs(x-j)+abs(y-i)+1)
    ans[a-1] += 1
for i in range(n-1):
  print(ans[i])

### FIXED CODE ###

n, x, y = map(int, input().split())
ans = [0 for _ in range(n-1)]
for i in range(1, n):
  for j in range(i+1, n+1):
    a = min(j-i, abs(x-i)+abs(y-j)+1, abs(x-j)+abs(y-i)+1)
    ans[a-1] += 1
for i in range(n-1):
  print(ans[i])
### BUGGY CODE ###

from itertools import accumulate
import math

def is_prime(n):
  if n == 1: return False
  for k in range(2, int(math.sqrt(n))+1):
    if n % k == 0:
      return False
  return True

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    A = [i for i in range(l, r+1, 2)]
    B = [(a+1)//2 for a in A]
    cnt = 0
    for i in range(len(A)):
      if is_prime(A[i]) and is_prime(B[i]):
        cnt += 1
    print(cnt)

### FIXED CODE ###

import math
from itertools import accumulate

def is_prime(n):
  if n == 1: return False
  for k in range(2, int(math.sqrt(n))+1):
    if n % k == 0: return False
  return True

MAX = (10**5)+1
q = int(input())
A = [1 if is_prime(i)and is_prime((i + 1)//2) else 0 for i in range(MAX) ]
S = [0] + list(accumulate(A))

Q =[]
Q_append = Q.append
for _ in range(q):
    l, r = map(int, input().split())
    Q_append((l, r))

for qi in Q:  
    print(S[qi[1]+1]-S[qi[0]])
### BUGGY CODE ###

s =list(input())
N = len(s)
mod = pow(10,9)+7
dp = [[0]*13 for i in range(N)]
if s[0] == '?':
        dp[0][0:9] = [1 for i in range(10)]
else:
    dp[0][int(s[0])] = 1
for i in range(1,N):
    if s[i] == '?':
        for j in range(10):
            for m in range (13):
                 dp[i][(m*10+j)%13] += dp[i-1][m]%mod
    else:
        for m in range(13):
            dp[i][(m*10+int(s[i]))%13] += dp[i-1][m]%mod
print(dp[-1][5]% mod)


### FIXED CODE ###

s =list(input())
N = len(s)
mod = pow(10,9)+7
dp = [[0]*13 for i in range(N)]
if s[0] == '?':
        dp[0][0:9] = [1 for i in range(10)]
else:
    dp[0][int(s[0])] = 1
for i in range(1,N):
    if s[i] == '?':
        for j in range(10):
            for m in range (13):
                 dp[i][(m*10+j)%13] += dp[i-1][m]%mod
    else:
        for m in range(13):
            dp[i][(m*10+int(s[i]))%13] += dp[i-1][m]%mod
print(dp[-1][5]% mod)
### BUGGY CODE ###

n = int(input())
A = []
ans = 0
for i in range(n):
    a = input()
    if a not in A:
        ans += 1
        A.append(a)
print(ans)

### FIXED CODE ###

import collections
n = int(input())
A = [input() for i in range(n)]
c = collections.Counter(A)
print(len(list(c)))
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = I()
edge = [[] for _ in range(n)]
for v in range(1,n):
    u = I()-1
    edge[u].append(v)

dp = [inf]*n
def dfs(s):
    if edge[s] == []:
        dp[s] = 0
        return 0
    tmp = []
    for v in edge[s]:
        tmp.append(dfs(v))
    m = 0
    tmp.sort(reverse=True)
    for i,j in enumerate(tmp):
        m = max(m,(i+1)+j)
    dp[s] = m
    return m

dfs(0)
print(dp[0])

### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = I()
edge = [[] for _ in range(n)]
for v in range(1,n):
    u = I()-1
    edge[u].append(v)

dp = [None]*n
def dfs(s):
    if dp[s] != None:
        return dp[s]
    if edge[s] == []:
        dp[s] = 0
        return 0
    tmp = []
    for v in edge[s]:
        tmp.append(dfs(v))
    tmp.sort(reverse=True)
    m = 0
    for i,j in enumerate(tmp):
        m = max(m,(i+1)+j)
    dp[s] = m
    return m

dfs(0)
print(dp[0])
### BUGGY CODE ###

n=int(input())
p=1
for i in range(1,n+1):
    p*=i
print(p%(10**9+7))


### FIXED CODE ###

n=int(input())
p=1
if n<=1000:
    for i in range(1,n+1):
        p*=i
        p=p%(10**9+7)
    print(p)
else:
    p=641419708
    for i in range(1001,n+1):
        p*=i
        p=p%(10**9+7)
    print(p)
### BUGGY CODE ###

import queue

N, Q = map(int, input().split())
tree = [[] for _ in range(N+1)]
value = [0] * (N+1)
visit = [False] * (N+1)

# make_tree
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

# make_value
for _ in range(Q):
    p, x = map(int, input().split())
    value[p] += x

# all_value_sum
q = queue.Queue()
q.put(1)
visit[1] = True
while not q.empty():
    now = q.get()
    for next in tree[now]:
        if not visit[next]:
            value[next] += value[now]
            q.put(next)
            visit[next] = True

# output_value
s = " ".join(map(str, value[1:]))
print(s)

### FIXED CODE ###

import sys
import queue
input = sys.stdin.readline

N, Q = map(int, input().split())
tree = [[] for _ in range(N+1)]
value = [0] * (N+1)
visit = [False] * (N+1)

# make_tree
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

# make_value
for _ in range(Q):
    p, x = map(int, input().split())
    value[p] += x

# all_value_sum
q = queue.Queue()
q.put(1)
visit[1] = True
while not q.empty():
    now = q.get()
    for next in tree[now]:
        if not visit[next]:
            value[next] += value[now]
            q.put(next)
            visit[next] = True

# output_value
s = " ".join(map(str, value[1:]))
print(s)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
ki = [0]*1001
for i in range(1, 1001):
    ki[i] = ki[i-1]+i

pp = []
for pa in p:
    pp.append(ki[pa]/pa)

ans = 0
for i in range(n-k+1):
    ans = max(ans, sum(pp[i:i+k]))

print("{0:.12f}".format(ans))


### FIXED CODE ###

import itertools
n, k = map(int, input().split())
p = list(map(int, input().split()))
ki = [0]*1001
for i in range(1, 1001):
    ki[i] = ki[i-1]+i

pp = []
for pa in p:
    pp.append(ki[pa]/pa)

# print(pp)
ppp = [0] + list(itertools.accumulate(pp))
# print(ppp)
ans = 0
for i in range(n-k+1):
    # print(ppp[i+k]-ppp[i])
    ans = max(ans, ppp[i+k]-ppp[i])

print("{0:.12f}".format(ans))
### BUGGY CODE ###

N = int(input())
ans = 100000
for i in range(1, 2 * 10 ** 7):
    if N % i == 0:
        ans = min(ans, max(len(str(i)), len(str(N // i))))

print(ans)


### FIXED CODE ###

N = int(input())
ans = 100000
for i in range(1, 10 ** 5):
    if N % i == 0:
        ans = min(ans, max(len(str(i)), len(str(N // i))))

print(ans)
### BUGGY CODE ###

N = int(input())
S = input()

ans = 0
for i in range(1000):
    s = list()
    s.append(str(i // 100))
    s.append(str((i//10) % 10))
    s.append(str(i % 10))

    ind = 0
    cnt = 0
    while cnt < 3 and ind < N:
        if S[ind] == s[cnt]:
            cnt += 1
        ind += 1

        if cnt == 3:
            ans += 1

print(ans)


### FIXED CODE ###

def check(num, N): #Nからnumが作れるならreturn 1
    length = len(N)

    get_target = 0
    for i in range(length):
        if get_target == 0 and N[i] == num[0]:
            get_target = 1
            # print("target1", num)
        elif get_target == 1 and N[i] == num[1]:
            get_target = 2
            # print("target2", num)
        elif get_target == 2 and N[i] == num[2]:
            get_target = 3
            # print("target3", num)
    
    if get_target == 3:
        # print(num)
        return 1
    else:
        return 0


N = int(input())
S = input()

counter = 0
for i in range(1000):
    str_i = str(i)
    while len(str_i) <3:
        str_i = "0" + str_i
    
    counter += check(str_i, S)
print(counter)
### BUGGY CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))

for i in range(K):
    H[H.index(max(H))]=0

print(sum(H))


### FIXED CODE ###

import numpy as np

N,K=map(int,input().split())
H=list(map(int,input().split()))

if K==0:
    print(sum(H))
elif N>K:
    H=sorted(H)
    del H[-K:]
    print(sum(H))
else:
    print(0)
### BUGGY CODE ###

import math
from math import floor
A,B,N = map(int,input().split())
maxi = 0
Npower = 0
diff = 0
S = N
while S/10 >= 1:
    Npower += 1
    S /=10
if Npower >= 7:
    for i in range(0,10**6+10**5):
        maxi = max(floor((A*i)/B)-A*floor(i/B),maxi)
    for i in range(N-9*10**6,N+1):
        maxi = max(floor((A*i)/B)-A*floor(i/B),maxi)
else:
    for i in range(0,N+1):
        maxi = max(floor((A*i)/B)-A*floor(i/B),maxi)
print(max(maxi,0))


### FIXED CODE ###

import math
from math import floor
A,B,N = map(int,input().split())
def f(x):
  return floor(A*x/B) - A*floor(x/B)
print(f(min(B-1,N)))
### BUGGY CODE ###

import math


def main():
    a,b,n = map(int,input().split())
    m = math.floor(a * 0 /b) - a * math.floor(0/b)
    for i in range(1,min(b-1,n)+1):
        if m < math.floor(a * i / b) - a * math.floor(i/b):

            m = math.floor(a * i / b) - a * math.floor(i/b)
    print(m)
if __name__ == "__main__":
    main()


### FIXED CODE ###

import math


def main():
    a,b,n = map(int,input().split())
    # m = math.floor(a * 0 /b) - a * math.floor(0/b)
    # for i in range(1,min(b-1,n)+1):
    #     if m < math.floor(a * i / b) - a * math.floor(i/b):
    #         m = math.floor(a * i / b) - a * math.floor(i/b)
    i = min(b-1,n)
    m = a*i//b - a*(i//b)
    
    print(m)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# DP
N, W = map(int, input().split())

dp = [-1] * (W + 1)
dp[0] = 0
for _ in range(N):
    w, v = map(int, input().split())
    for i in range(W - w, -1, -1):
        if dp[i] == -1:
            continue
        if dp[i + w] < dp[i] + v:
            dp[i + w] = dp[i] + v
print(max(dp))


### FIXED CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))
### BUGGY CODE ###

n = int(input())
s = input()

password = {}
cnt = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            p = s[i] + s[j] + s[k]
            if not p in password.keys():
                password[p] = 0
                cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
s = input()

cnt = 0
for i in range(10):
    s_ = s
    if str(0) in s_:
        s_ = s_[s_.index(str(0))+1:]
        if str(0) in s_:
            s_ = s_[s_.index(str(0))+1:]
            if str(i) in s_:
                cnt += 1

for i in range(10,100):
    s_ = s
    if str(0) in s_:
        s_ = s_[s_.index(str(0))+1:]
        if str(i)[0] in s_:
            s_ = s_[s_.index(str(i)[0])+1:]
            if str(i)[1] in s_:
                cnt += 1

for i in range(100,1000):
    s_ = s
    if str(i)[0] in s_:
        s_ = s_[s_.index(str(i)[0])+1:]
        if str(i)[1] in s_:
            s_ = s_[s_.index(str(i)[1])+1:]
            if str(i)[2] in s_:
                cnt += 1  

print(cnt)
### BUGGY CODE ###

from functools import reduce


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


N = int(input())
a_list = list(map(int, input().split()))
max_gcd_a = reduce(gcd, a_list[1:], a_list[1])
for idx in range(1, N):
    gcd_1 = reduce(gcd, a_list[1:idx], a_list[0])
    gcd_a = reduce(gcd, a_list[idx + 1:], gcd_1)
    if max_gcd_a < gcd_a:
        max_gcd_a = gcd_a

print(max_gcd_a)

# どれか１つを除いた時の最大公約数で最大のもの


### FIXED CODE ###

from functools import reduce


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


N = int(input())
a_list = list(map(int, input().split()))
gcd_list = [a_list[-1]]
for idx in range(N - 2, 0, -1):
    gcd_list.append(gcd(gcd_list[N - 2 - idx], a_list[idx]))
max_gcd_a = gcd_list[-1]
gcd_list.append(1)
gcd_list.reverse()

for idx in range(1, N):
    if idx != 1:
        left_gcd = gcd(left_gcd, a_list[idx - 1])
    else:
        left_gcd = a_list[0]
    if idx < N - 1:
        right_gcd = gcd_list[idx + 1]
    else:
        right_gcd = left_gcd

    gcd_a = gcd(left_gcd, right_gcd)
    if max_gcd_a < gcd_a:
        max_gcd_a = gcd_a

print(max_gcd_a)

# どれか１つを除いた時の最大公約数で最大のもの
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	C
# CreatedDate:  2020-08-18 14:20:26 +0900
# LastModified: 2020-08-18 14:29:03 +0900
#


import os
import sys
from collections import Counter


def main():
    n = int(input())
    ans_box = dict()
    for i in range(n):
        s = list(map(str, input()))
        s_cnt = Counter(s)
        ans_box[i] = s_cnt
    cnt = 0
    for i in range(n):
        for j in range(i+1, n):
            if ans_box[i] == ans_box[j]:
                cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	C_fix
# CreatedDate:  2020-08-18 14:31:47 +0900
# LastModified: 2020-08-18 14:42:13 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    n = int(input())
    ans_box = dict()
    for _ in range(n):
        s = sorted(map(str, input()))
        if ''.join(s) in ans_box.keys():
            ans_box[''.join(s)] += 1
        else:
            ans_box[''.join(s)] = 1
    ans = 0
    for key, value in ans_box.items():
        if value == 1:
            pass
        else:
            ans += value*(value-1)//2
    print(ans)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

import scipy.misc

N=int(input())
X=list(map(int,input().split()))
SX=sorted(X)
M=SX.pop()
MV=0
ANS=0
for x in SX:
  if (M - x) in SX:
    continue
  else:
    cb = scipy.misc.comb(M,x)
    if MV < cb:
      MV = cb
      ANS = x
print("{} {}".format(M,ANS))



### FIXED CODE ###

import scipy.misc

N=int(input())
X=list(map(int,input().split()))
SX=sorted(X)
M=SX.pop()
MV=10**9
ANS=0
for x in SX:
  z = abs(M - x - x)
  if MV > z:
    MV = z
    ANS = x
print("{} {}".format(M,ANS))
### BUGGY CODE ###

n, k = map(int,input().split())
count = 0
while(True):
  nk_abs = abs(n - k)

  if min(n, k, nk_abs) == n:
    break
  if k == 1:
    n = 0
    break
  n = nk_abs
  count += 1

print(n)

### FIXED CODE ###

n, k = map(int, input().split())
print(min(n % k, k - n % k))
### BUGGY CODE ###

import sys,copy

n=int(input())
l=[]
for i in range(5):
    l.append(int(input()))
m=[n]
for i in range(5):
    m.append(0)
mm=[0]*6
t=0


while m[5]!=n:
    for j in range(5):
        if m[j]>0:
            mm[j+1]=min(m[j],l[j])
            m[j]-=min(m[j],l[j])
    for k in range(6):
        m[k]+=mm[k]
        mm[k]=0
    t+=1
print(t)

### FIXED CODE ###

import math

n=int(input())
l=[]
for i in range(5):
    l.append(int(input()))
    
m=math.ceil(n/min(l))

print(m-1+5)
### BUGGY CODE ###

import fractions
from functools import reduce
N = int(input())
X = list(map(int, input().split()))
 
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
  
gcd = 1
 
for i in range(N):
  Y = X.pop(i)
  gcd_1 = gcd_list(X)
  gcd = max(int(gcd), int(gcd_1))
  if gcd in X:
    break
  X.insert(i,Y)
print(gcd)

### FIXED CODE ###

#解説の方針にしたがった
import fractions

N = int(input())
X = list(map(int, input().split()))
   
M = 1  
L = [0 for i in range(100004)] #L(0)=0
R = [0 for i in range(100004)]  #R(N+1) = 0

for i in range(N):
  L[i] = (fractions.gcd(L[i-1],X[i]))

for i in reversed(range(N)):
  #print(i)
  R[i] = (fractions.gcd(R[i+1],X[i]))
    
ans = 1

#print(L)
#print(R)
for i in range(N):
  ans = max(ans, fractions.gcd(L[i-1],R[i+1]))

print(ans)
### BUGGY CODE ###

# ac
import numpy as np
# imos法
def update(a):
    n = len(a)
    # b = np.zeros_like(a)       # aと同じ形状の配列を生成(https://deepage.net/features/numpy-zeros.html)
    b = [0 for _ in range(n)]
    for i, x in enumerate(a):  # enumerateはindex, valueを返す
        l = max(0, i - x)      # lampの照らす範囲の下限（左側）
        r = min(n - 1, i + x)  # lampの上限（右側）
        b[l] += 1              # 以下imos法
        if r + 1 < n:          # r+1はx=nの時（最後のサイクル）r+1=nでindexの指定に失敗するから弾く（indexは0~n-1）
            b[r + 1] -= 1
    b = np.cumsum(b)           # bの要素の累積和（フィボナッチ数列みたいな）（imos法の締め）
    return b

n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))

k = min(k, 41)                 # 今回の制限範囲のnなら41回も試行すればaの値が全て上限に達するのでそれ以上の試行は不要（解説PDF）
for _ in range(k):
    a = update(a)
print(' '.join(map(str, a)))   # joinメソッドはstrを''で区切って連結する

### FIXED CODE ###

# ac
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i8[::1],)', cache=True)
def update(a):
    n = len(a)
    b = np.zeros_like(a)       # aと同じ形状の配列を生成(https://deepage.net/features/numpy-zeros.html)
    for i, x in enumerate(a):  # enumerateはindex, valueを返す
        l = max(0, i - x)      # lampの照らす範囲の下限（左側）
        r = min(n - 1, i + x)  # lampの上限（右側）
        b[l] += 1              # 以下imos法
        if r + 1 < n:          # r+1はx=nの時（最後のサイクル）r+1=nでindexの指定に失敗するから弾く（indexは0~n-1）
            b[r + 1] -= 1
    b = np.cumsum(b)           # bの要素の累積和（フィボナッチ数列みたいな）（imos法の締め）
    return b


n, k = map(int, readline().split())
a = np.array(read().split(), np.int64)

k = min(k, 41)                 # 今回の制限範囲のnなら41回も試行すればaの値が全て上限に達するのでそれ以上の試行は不要（解説PDF）
for _ in range(k):
    a = update(a)
print(' '.join(map(str, a)))   # joinメソッドはstrを''で区切って連結する
### BUGGY CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

s = input()
k = INT()
a = set()
for i in range(len(s)):
    for j in range(i, len(s)):
        a.add(s[i:j+1])
b = sorted(list(a))
print(b[k-1])

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

s = input()
k = INT()
a = set()
for i in range(len(s)):
    t = s[i]
    a.add(t)
    if i < len(s) - 1:
        for j in range(i+1, min(i+k+1,len(s))):
            t += s[j]
            a.add(t)
b = sorted(list(a))
print(b[k-1])
### BUGGY CODE ###

rgbn = list(map(int, input().split()))
R = rgbn[0]
G = rgbn[1]
B = rgbn[2]
N = rgbn[3]
res = 0
r = 0
while R * r <= N:
    b = 0
    while B * b <= N - R * r:
        if (N - R * r -B * b) % G == 0:
            res += 1
        b += 1
    r += 1
print(res)


### FIXED CODE ###

rgbn = list(map(int, input().split()))
R = rgbn[0]
G = rgbn[1]
B = rgbn[2]
N = rgbn[3]
res = 0
r = 0
while R * r <= N:
    b = 0
    while B * b <= N - R * r:
        if (N - R * r -B * b) % G == 0:
            res += 1
        b += 1
    r += 1
print(res)
### BUGGY CODE ###

S = []
N, M = input().split(" ")
for m in range(int(M)):
  a, b = input().split(" ")
  S.append(set([i for i in range(int(a),int(b)+1)]))
if M == 1:
  print(len(S[0]))
else:
  sets = S[0]
  for i in range(1,int(M)):
    sets = sets & S[i]
  print(len(sets))

### FIXED CODE ###

N, M = input().split(" ")
#S = []
if M == 1:
    a, b = input().split(" ")
    print(int(b)-int(a)+1)
else:    
    a, b = input().split(" ")
    aM, bm = int(a),int(b)
    #sets = set([i for i in range(int(a),int(b)+1)])
    for m in range(int(M)-1):
        a, b = input().split(" ")
        aM = max(aM,int(a))
        bm = min(bm,int(b))
        #sets = sets & set([i for i in range(int(a),int(b)+1)])
    if(bm<aM):
        print(0)
    else:
        print(int(bm)-int(aM)+1)
### BUGGY CODE ###

t = int(input())
for i in range(t):
    a, b, c, d = map(int, input().split())
    rec = [a]
    flag = False
    num = 0
    while True and num < 100000:
        if a < b:
            break
        else:
            a = a % b
        if a <= c:
            a += d
        if a in rec:
            flag = True
            break
        num += 1
        rec.append(a)
    if flag:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

T = int(input())


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


for i in range(T):
    a, b, c, d = map(int, input().split())
    if a < b:
        print('No')
    elif d < b:
        print('No')
    elif c >= b:
        print('Yes')
    else:
        g = gcd(b, d)
        if b - g + a % g > c:
            print('No')
        else:
            print('Yes')