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

s = input().replace('\n', '')
q = int(input())
flag = True
for i in range(q):
    query = list(map(str, input().split()))
    if query[0]=='1':
        if flag: flag = False
        else: flag = True
    else:
        if (not flag and query[1]=='1') or flag and query[1]=='2':
            s += query[2]
        else:
            s = query[2] + s
print(s if flag else s[::-1])


### FIXED CODE ###

from collections import deque
s = deque(input().replace('\n', ''))
q = int(input())
flag = True
for i in range(q):
    query = list(map(str, input().split()))
    if query[0]=='1':
        if flag: flag = False
        else: flag = True
    else:
        
        if (not flag and query[1]=='1') or flag and query[1]=='2':
            s.append(query[2])
        else:
            s.appendleft(query[2])
s = ''.join(s)
print(s if flag else s[::-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
l = len(a)
a = [a[i]-(i+1) for i in range(l)]
a_min = min(a)
a_max = max(a)

res = float('inf')
for i in range(min(a),max(a)+1):
    sum = 0
    for j in a:
        sum += abs(j - i)
    res = min(res, sum)
print(res)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
l = len(a)
b = [a[i]-(i+1) for i in range(n)]
b = sorted(b)
mid = b[l//2]
sum = 0
for i in range(n):
    sum+=abs(a[i]-(mid+(i+1)))
print(sum)
### BUGGY CODE ###

import numpy as np

n = int(input())
table = np.array([[-1]*n for _ in range(n)]) # 証言がないやつはとりあえず-1入れとくか

for i_speaker in range(n):
    ai = int(input())
    for _ in range(ai):
        xij, yij= map(int, input().split())
        table[i_speaker][xij-1] = yij

ans = 0
for i in range(2**n):
    isConflict = False

    for j_speaker in range(n): # それぞれの桁について0か1かを判断したいので
        if (i >> j_speaker) & 1 == 0: # j桁目が1かどうかをジャッジ
            continue

        for k_target in range(n):
            if table[j_speaker][k_target] != -1 and table[j_speaker][k_target] != ((i >> k_target) & 1) :
                isConflict = True
                break

        if isConflict:
            break
    if isConflict == False:
        ans = max(ans, bin(i).count("1"))


print(ans)


### FIXED CODE ###

n = int(input())
testimony_table = [[] for _ in range(n)]

for i_witness in range(n):
    ai = int(input())
    for _ in range(ai):
        xij, yij= map(int, input().split())
        testimony_table[i_witness].append((xij-1,yij))

ans = 0
for i in range(2**n):
    isConflict = False

    for j_witness in range(n): # それぞれの桁について0か1かを判断したいので
        if (i >> j_witness) & 1 == 0: # j桁目が1かどうかをジャッジ
            continue


        for x_suspect, y_testimony in testimony_table[j_witness]:
            if ((i >> x_suspect) & 1) != y_testimony:
                isConflict = True
                break

        if isConflict:
            break
    if isConflict == False:
        ans = max(ans, bin(i).count("1"))

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

n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(n):
    b.append(a[i])
    b.reverse()
print(*b)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
for i in a[-1::-2]:
    b.append(i)
for i in a[(n%2 == 1)::2]:
    b.append(i)
print(*b)
### BUGGY CODE ###

n=int(input())
s=input()
ans=n
for i in range(0,n):
    sl=s[:i].count("W")
    sr=s[i+1:].count("E")
    ans=min(ans,sl+sr)
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
ans=n
sl=[0]
sr=[0]
c=0
for i in s:
    if i=="W":c+=1
    sl.append(c)
s=s[::-1]
c=0
for i in s:
    if i=="E":c+=1
    sr.append(c)
sr=sr[::-1]
for i in range(n):ans=min(ans,sl[i]+sr[i+1])
print(ans)
### BUGGY CODE ###

N ,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
inf = max(A[0]**2,A[-1]**2)
ok = inf
ng = -inf

def is_ok(arg):
    ans = 0
    for i in range(N):
        if A[i] * A[i] < arg :
            ans -= 1
        ok = N
        ng = -1
        if A[i] == 0:
            if arg > 0:
                ans += N
        elif A[i] > 0:
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ng = mid
                else:
                    ok = mid
            ans += ok
        else: 
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ok = mid
                else:
                    ng = mid       
            ans += N-ok   
    ans /= 2
    return K > ans

while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid):
        ng = mid
    else:
        ok = mid
print(ng)


### FIXED CODE ###

N ,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
inf = max(A[0]**2,A[-1]**2)
ok1 = inf
ng1 = -inf
while (abs(ok1 - ng1) > 1):
    arg = (ok1 + ng1) // 2
    ans = 0
    for i in range(N):
        if A[i] * A[i] < arg :
            ans -= 1
        ok = N
        ng = -1
        if A[i] == 0:
            if arg > 0:
                ans += N
        elif A[i] > 0:
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ng = mid
                else:
                    ok = mid
            ans += ok
        else: 
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ok = mid
                else:
                    ng = mid       
            ans += N-ok   
    ans /= 2
    if K>ans:
        ng1 = arg
    else:
        ok1 = arg
print(ng1)
### BUGGY CODE ###

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

answer=0
for i in range(1000):
  i0=i//100
  i1=(i//10)%10
  i2=i%10

  flag_num=0
  for s in S:
    if flag_num==0 and s==str(i0):
      flag_num+=1
    elif flag_num==1 and s==str(i1):
      flag_num+=1
    elif flag_num==2 and s==str(i2):
      answer+=1
      break
      
print(answer)

### FIXED CODE ###

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

answer=0
for i in range(1000):
  i0=i//100
  i1=(i//10)%10
  i2=i%10

  flag_num=0
  for s in S:
    if flag_num==0 and s==str(i0):
      flag_num+=1
    elif flag_num==1 and s==str(i1):
      flag_num+=1
    elif flag_num==2 and s==str(i2):
      answer+=1
      break
      
print(answer)
### BUGGY CODE ###

import numpy as np
import heapq

INF=10**15
N,M=map(int,input().split())
adj=[[] for i in range(N)]
for i in range(M):
    L,R,C=map(int,input().split())
    L-=1
    R-=1
    adj[L].append((R,C))
    adj[R].append((L,C))
for i in range(N-1):
    adj[i+1].append((i,0))
    
s=0
g=N-1
heap=[]
table=np.array([INF for i in range(N)])
table[s]=0
heapq.heappush(heap,(s,table[s]))
                
while heap:
    q=heapq.heappop(heap)
    a=q[0]
    if q[1]>table[a]: continue
    for ne in adj[a]:
        p=ne[0]
        co=ne[1]
        if table[p]>table[a]+co:
            table[p]=table[a]+co
            heapq.heappush(heap,(p,table[p]))
ans=table[g]
if ans==INF:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import numpy as np
import heapq

INF=10**15
N,M=map(int,input().split())
adj=[[] for i in range(N)]
for i in range(M):
    L,R,C=map(int,input().split())
    L-=1
    R-=1
    adj[L].append((R,C))
    adj[R].append((L,C))
for i in range(N-1):
    adj[i+1].append((i,0))
    
s=0
g=N-1
heap=[]
table=np.array([INF for i in range(N)])
table[s]=0
heapq.heappush(heap,(table[s],s))
                
while heap:
    q=heapq.heappop(heap)
    a=q[1]
    if q[0]>table[a]: continue
    for ne in adj[a]:
        p=ne[0]
        co=ne[1]
        if table[p]>table[a]+co:
            table[p]=table[a]+co
            heapq.heappush(heap,(table[p],p))
ans=table[g]
if ans==INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

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

point=[]
answer=10**19
for i in range(N):
  point.append(list(map(int,input().split())))
sorted(point)
for left in range(N):
  for right in range(N):
    dx=point[right][0]-point[left][0]
    for ceil in range(N):
      for bottom in range(N):
        if point[bottom][1] > point[ceil][1]:
          continue
        count=0
        for i in range(N):
          x=point[i][0]
          y=point[i][1]
          if point[left][0]<=x and x<=point[right][0] and point[bottom][1]<=y and y<=point[ceil][1]:
            count+=1
        if count>=K:
          answer=min(answer,dx*(point[ceil][1]-point[bottom][1]))
     
          
print(answer)

### FIXED CODE ###

#https://atcoder.jp/contests/abc075/submissions/2242350
N,K=map(int,input().split())

points=[tuple(map(int,input().split())) for i in range(N)]
answer=10**19
sortx=sorted(points)
numberx = list(enumerate(sortx))

#n-k+1以降を左の頂点とすると点の数が明らかに足りない
for left,(x1,y1) in numberx[:N-K+1]:
  #left+K-1以降を右の頂点にしないと間に足りる点の数が入ってない
  for right,(x2,y2) in numberx[left+K-1:]:
    dx=x2-x1
    #left-rightの間でyについてsort
    sorty=sorted(y for x,y in sortx[left:right+1])
    #K個点を入れた状態で面積を求める
    for y3,y4 in zip(sorty,sorty[K-1:]):
      if y3<=y1 and y3<=y2 and y4>=y1 and y4>=y2:
        answer=min(answer,dx*(y4-y3))
         
print(answer)
### BUGGY CODE ###

# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# import re
# from bisect import bisect_left
# from heapq import heappush,heappop
# from numba import njit,jit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
from networkx import Graph,shortest_path,single_source_shortest_path
G = Graph()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

# slist = "abcdefghijklmnopqrstuvwxyz"
N,M = map(int,input().split())
rows = [list(map(int,input().split())) for _ in range(M)]

G.add_edges_from(rows)

# shortestPath = shortest_path(G,target=1)
shortestPath = single_source_shortest_path(G,source=1)
# shortestPath = single_target_shortest_path(G,target=1)
# shortestPathLength,shortestPath = single_source_dijkstra(G,source=1)

# print(shortestPath)
if len(shortestPath) != N:
    print("No")
    exit()

print("Yes")
for i in range(2,N+1):
    print(shortestPath[i][-2])


# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


### FIXED CODE ###

# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# import re
# from bisect import bisect_left
# from heapq import heappush,heappop
# from numba import njit,jit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
from networkx import Graph
from networkx.algorithms.traversal.breadth_first_search import bfs_predecessors
G = Graph()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

# slist = "abcdefghijklmnopqrstuvwxyz"
N,M = map(int,input().split())
rows = [list(map(int,input().split())) for _ in range(M)]

G.add_edges_from(rows)

# shortestPath = shortest_path(G,target=1)
preds = bfs_predecessors(G,source=1)
# shortestPath = single_target_shortest_path(G,target=1)
# shortestPathLength,shortestPath = single_source_dijkstra(G,source=1)

preds = dict(preds)
if len(preds)+1 != N:
    print("No")
    exit()

print("Yes")
for i in range(2,N+1):
    print(preds[i])
### BUGGY CODE ###

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

cnt = 0
for i in range(n-1):
    for j in range(i+1, n):
        if (i + 1) + A[i] == (j + 1) - A[j]:
            cnt += 1

print(cnt)

### FIXED CODE ###

from collections import Counter
n = int(input())
A = list(map(int, input().split()))

P = [i + a for i, a in enumerate(A, start=1)]
Q = [j - a for j, a in enumerate(A, start=1)]

Q = Counter(Q)

cnt = 0
for p in P:
    cnt += Q[p]

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

# from collections import Counter
N = int(input())
sN = [input() for _ in range(N)]
# counts = [Counter(s) for s in sN]
# pool = []
# ans = 0
# for count in counts:
#     if count in pool:
#         ans += 1
#     else:
#         pool.append(count)
# print(pool)
# # print(get_unique_list(counts))
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        if sorted(sN[i]) == sorted(sN[j]):
            ans += 1
print(ans)


### FIXED CODE ###

from collections import Counter
from scipy.misc import comb
N = int(input())
s = [''.join(sorted(input())) for _ in range(N)]
ans = 0
for count in Counter(s).values():
    ans += comb(count, 2, exact=True)
print(ans)
### BUGGY CODE ###

n,q = map(int,input().split())
node = [[]for _ in range(n)]
looked = [1 for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    node[b-1].append(a-1)
    node[a-1].append(b-1)
counter = [0 for _ in range(n)]
for i in range(q):
    p,x = map(int,input().split())
    counter[p-1] += x
queue = [0]
looked[0] = 0
while(len(queue)):
    now = queue.pop(0)
    for i in node[now]:
        if looked[i]:
            queue.append(i)
            counter[i] += counter[now]
            looked[i] = 0
print(" ".join(list(map(str,counter))))

### FIXED CODE ###

from collections import deque
def main():
    n,q = map(int,input().split())
    node = [[]for _ in range(n)]
    looked = [1]*n
    for i in range(n-1):
        a,b = map(int,input().split())
        node[b-1].append(a-1)
        node[a-1].append(b-1)
    counter = [0]*n
    for i in range(q):
        p,x = map(int,input().split())
        counter[p-1] += x
    queue = deque([0])
    looked[0] = 0
    while(queue):
        now = queue.pop()
        for i in node[now]:
            if looked[i]:
                queue.append(i)
                counter[i] += counter[now]
                looked[i] = 0
    print(*counter)
main()
### BUGGY CODE ###

def main():
    import heapq
    import sys
    input = sys.stdin.buffer.readline
    N, M, L = map(int, input().split())

    G = [set() for i in range(N)]
    for i in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        G[A].add((B, C))
        G[B].add((A, C))

    # ある地点からそこまでにL以下の道があるか、０でいける地点からそのときの残量以下で行ける地点が0で行ける地点
    # ある地点からL以下ではいけるが、その地点に行くまでの残量ではいけない場合には、+1

    D = [[[-1, -1]for j in range(N)] for i in range(N)]
    for i in range(N):
        D[i][i] = [0, L]
    #q = collections.deque()
    hq = []
    count = 0
    for i in range(N):
        r = set([i])
        # q.append(i)
        hq = [(0, i)]
        DD = D[i]
        while(hq):
            count += 1
            #x = q.popleft()
            d, x = heapq.heappop(hq)
            for y, c in G[x]:
                if c > L:
                    continue
                elif c > DD[x][1]:
                    if DD[y][0] == -1 or DD[y][0] > DD[x][0]+1:
                        DD[y][0] = DD[x][0] + 1
                        DD[y][1] = L - c
                        heapq.heappush(hq, (DD[y][0], y))
                    elif DD[y][0] == DD[x][0]+1 and DD[y][1] < L - c:
                        DD[y][1] = L - c
                        heapq.heappush(hq, (DD[y][0], y))
                else:
                    if DD[y][0] == -1 or DD[y][0] > DD[x][0]:
                        DD[y][0] = DD[x][0]
                        DD[y][1] = DD[x][1] - c
                        heapq.heappush(hq, (DD[y][0], y))
                    elif DD[y][0] == DD[x][0] and DD[y][1] < DD[x][1] - c:
                        DD[y][1] = DD[x][1] - c
                        heapq.heappush(hq, (DD[y][0], y))
    # print(D)

    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        print(D[s][t][0])


main()


### FIXED CODE ###

from scipy.sparse.csgraph import csgraph_from_dense, dijkstra


def main():
    import heapq
    import sys
    input = sys.stdin.buffer.readline
    N, M, L = map(int, input().split())

    G = [[-1]*N for i in range(N)]

    for i in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        G[A][B] = C
        G[B][A] = C
    g = csgraph_from_dense(G, null_value=-1)
    D = dijkstra(g)
    G2 = [[-1]*N for i in range(N)]
    for i in range(N):
        for j in range(N):
            if D[i][j] >= 0 and D[i][j] <= L:
                G2[i][j] = 1

    g2 = csgraph_from_dense(G2, null_value=-1)
    D = dijkstra(g2)


    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        if D[s][t] <= N**2:
            print(int(D[s][t])-1)
        else:
            print(-1)


main()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

ans = 1

for i in A:
    ans *= i

if ans > 10 ** 18:
    print("-1")
else:
    print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

ans = 1

A = sorted(A, reverse=True)

if 0 not in A:
    for i in A:
        ans *= i
        if ans > 10 ** 18:
            break
else:
    ans = 0

if ans > 10 ** 18:
    print("-1")
else:
    print(ans)
### BUGGY CODE ###

import fractions

N = int(input())
A = list(map(int, input().split()))
L = A[0]
for i in range(1, N):
    L = L * A[i] // fractions.gcd(L, A[i])

ans = 0
for i in range(N):
    ans = (ans + L // A[i]) % 1000000007

print(ans)


### FIXED CODE ###

import fractions

N = int(input())
A = list(map(int, input().split()))
L = A[0]
for i in range(1, N):
    L = L * A[i] // fractions.gcd(L, A[i])

ans = 0
for i in range(N):
    ans = (ans + L // A[i]) #% 1000000007

print(ans%1000000007)
### BUGGY CODE ###

n = int(input())
plus_bracket = []
minus_bracket = []
zero_bracket = 0
for _ in range(n):
  mini = 0
  cur = 0
  for bracket in input():
    if bracket == '(':
      cur += 1
    else:
      cur -= 1
    if cur < mini:
      mini = cur
  if cur > 0:
    plus_bracket.append([mini, cur])
  elif cur < 0:
    minus_bracket.append([mini - cur, -cur])
  elif mini < zero_bracket:
    zero_bracket = mini

success = True
cur = 0
plus_bracket.sort(reverse=True)
minus_bracket.sort(reverse=True)
for bracket in plus_bracket:
  if cur + bracket[0] < 0:
    success = False
    break
  cur += bracket[1]
if cur + zero_bracket < 0:
  success = False
back_cur = 0
for bracket in minus_bracket:
  if back_cur + bracket[0] < 0:
    success = False
    break
  back_cur += bracket[1]
if cur != back_cur:
  success = False

if success:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

n = int(input())
plus_bracket = []
minus_bracket = []

for _ in range(n):
  mini = 0
  cur = 0
  for bracket in input():
    if bracket == '(':
      cur += 1
    else:
      cur -= 1
    if cur < mini:
      mini = cur
  if cur > 0:
    plus_bracket.append([-mini, cur])
  else:
    minus_bracket.append([cur - mini, -cur])

success = True
cur = 0
plus_bracket.sort()
minus_bracket.sort()
for bracket in plus_bracket:
  if cur < bracket[0]:
    success = False
    break
  cur += bracket[1]
back_cur = 0
for bracket in minus_bracket:
  if back_cur < bracket[0]:
    success = False
    break
  back_cur += bracket[1]
if cur != back_cur:
  success = False

if success:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

from heapq import heapify, heappop, heappush
from math import ceil
import sys

input = sys.stdin.readline


def main():
    n, d, a = map(int, input().split())
    hp = [list(map(int, input().split())) for _ in range(n)]
    heapify(hp)

    ans = 0

    while hp:
        left = heappop(hp)
        cnt = ceil(left[1] / a)
        li = []
        while hp and hp[0][0] <= left[0] + 2 * d:
            nxt = heappop(hp)
            if nxt[1] - a * cnt > 0:
                li.append([nxt[0], nxt[1] - a * cnt])

        for e in li:
            heappush(hp, e)

        ans += cnt

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from heapq import heapify, heappush, heappop
from math import ceil

REAL = 0
UNREAL = 1

n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]

hp = []
for x, h in xh:
    heappush(hp, [x, REAL, h])

bomb_acm = 0
ans = 0
while hp:
    x, r, h = heappop(hp)
    if r == REAL:
        if h > bomb_acm:
            left = h - bomb_acm
            bomb_cnt = ceil(left / a)
            hp_dis = a * bomb_cnt
            bomb_acm += hp_dis
            heappush(hp, [x + 2 * d, UNREAL, hp_dis])
            ans += bomb_cnt

    else: # r == UNREAL
        bomb_acm -= h

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

def main():
    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))
    dp = [10 ** 9] * n
    dp[0] = 0
    for i in tuple(range(n)):
        for j in tuple(range(1, k + 1)):
            i_j = i + j
            if i_j < n:
                x = dp[i] + abs(h[i] - h[i_j])
                if dp[i_j] > x:
                    dp[i_j] = x
    print(dp[-1])


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))
    INF = 10 ** 9
    dp = [INF] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1, k + 1):
            i_j = i + j
            if i_j < n:
                x = dp[i] + abs(h[i] - h[i_j])
                if dp[i_j] > x:
                    dp[i_j] = x
    print(dp[-1])


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

n = int(input())
apple = []
for _ in range(n):
    a = str(input())
    if a not in apple:
        apple.append(a)
    else:
        apple.remove(a)
print(len(apple))

### FIXED CODE ###

n = int(input())
apple = []
for _ in range(n):
    apple.append(int(input()))
apple = sorted(apple)
apple.append(0)
count = 0
ans = 1
for i in range(n):
    if apple[i] == apple[i + 1]:
        ans += 1
    else:
        if ans%2 == 0:
            ans = 1
        else:
            count += 1
print(count)
### BUGGY CODE ###

import bisect


def preliminary(k, aaa):
    dp = [False] * k
    dp[0] = True
    curr_max = 0
    fwd = []
    for a in aaa:
        for i in range(min(curr_max, k - a - 1), -1, -1):
            if dp[i]:
                dp[i + a] = True
        fwd.append(dp[:])
        curr_max += a

    dp = [False] * k
    dp[0] = True
    curr_max = 0
    bwd = []
    for a in reversed(aaa):
        for i in range(min(curr_max, k - a - 1), -1, -1):
            if dp[i]:
                dp[i + a] = True
        bwd.append([i for i, v in enumerate(dp) if v][1:])
        curr_max += a
    bwd.reverse()

    dummy = [False] * k
    dummy[0] = True
    fwd.append(dummy)
    bwd.append([])

    return fwd, bwd


def get_judge(k, aaa):
    fwd, bwd = preliminary(k, aaa)
    cache = [None] * k

    def judge(m):
        am = aaa[m]
        if cache[am] is None:
            dp = fwd[m - 1]
            ndp = dp[:]
            for i in bwd[m + 1]:
                for j in range(k - i - 1, -1, -1):
                    if dp[j]:
                        ndp[i + j] = True
            cache[am] = any(ndp[-am:])
        return cache[am]

    return judge


def solve(k, aaa):
    if sum(aaa) < k:
        return n

    aaa.sort()
    aaa = aaa[:bisect.bisect_left(aaa, k)]

    judge = get_judge(k, aaa)

    l = 0
    r = len(aaa) - 1
    m = (l + r) // 2
    while l <= r:
        if judge(m):
            r = m - 1
        else:
            l = m + 1
        m = (l + r) // 2

    return l


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
print(solve(k, aaa))


### FIXED CODE ###

import bisect


def solve(k, aaa):
    aaa = aaa[:bisect.bisect_left(aaa, k)]

    dp = [False] * k
    dp[0] = True
    curr_max = 0
    ans = len(aaa)
    for i, a in reversed(list(enumerate(aaa))):
        if curr_max + a >= k:
            ans = i
        f = True
        for j in range(min(curr_max, k - a - 1), -1, -1):
            if dp[j]:
                dp[j + a] = True
                if f:
                    curr_max = max(curr_max, j + a)
                    f = False
    return ans


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

print(solve(k, aaa))