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

import bisect
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort()
    l=0
    r=n
    if sum(a)<k:
        print(n)
    else:
        while l!=r:
            i=(l+r)//2
            ta = a[i]
            if ta>=k:flag=True
            else:
                na = a[:i]+a[i+1:]
                dp = [False for _ in range(k+1)]
                dp[0]=True
                for j in range(n-1):
                    for m in range(k,0,-1):
                        if m-na[j]>=0:
                            dp[m]=dp[m] or dp[m-na[j]]
                flag = False
                for j in range(k-ta,k):
                    if dp[j]:
                        flag = True
                        break
            if flag:
                r=i
            else:
                l=i+1
        print(l)

main()

### FIXED CODE ###

import bisect
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort()
    l=0
    r=n
    d = {}
    if sum(a)<k:
        print(n)
    else:
        while l!=r:
            i=(l+r)//2
            ta = a[i]
            if ta in d.keys():
                flag = d[ta]
            elif ta>=k:flag=True
            else:
                flag = False
                na = a[:i]+a[i+1:]
                dp = [False for _ in range(k+1)]
                dp[0]=True
                for j in range(n-1):
                    for m in range(k,0,-1):
                        if m-na[j]>=0:
                            dp[m]=dp[m] or dp[m-na[j]]
                        if m != k and m>=k-ta and dp[m]:
                            flag = True
                            break
                    if flag:break
                d[ta] = flag
            
            if flag:
                r=i
            else:
                l=i+1
        print(l)

main()
### BUGGY CODE ###

n,m=map(int,input().split())
l=list(map(int,input().split()))
l1=[]
l2=[]
c=0
for i in l:
  if i in l1:
    l2[l1.index(i)]+=1
  else:
    l1.append(i)
    l2.append(1)
if m>=len(l2):
  print(0)
else:
  l2=sorted(l2)
  for i in range(len(l2)-m):
    c+=l2[i]
  print(c)

### FIXED CODE ###

n,m=map(int,input().split())
l=list(map(int,input().split()))
d={}

c=0
for i in l:
  if i in d:
    d[i]+=1
  else:
    d[i]=1
l1=d.values()
if m>=len(l1):
  print(0)
else:
  l1=sorted(l1)
  for i in range(len(l1)-m):
    c+=l1[i]
  print(c)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
work = set(a)
d = [0]*(n+1)
count = 0
for el in work:
    temp = d[el] = a.count(el)
    count += temp*(temp-1)
count //= 2
for el in a:
    print(count - d[el] + 1)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
counter = Counter(a)
d = [0]*(n+1)
count = 0
for el, cnt in counter.most_common():
    d[el] = cnt
    count += cnt*(cnt-1)
count //= 2
for el in a:
    print(count - d[el] + 1)
### BUGGY CODE ###

N = int(input())

keihin = []
for i in range(N) :
  s = input()
  if s in keihin :
    continue
  keihin.append(s)
print(len(keihin))

### FIXED CODE ###

N = int(input())

keihin = []
for i in range(N) :
  s = input()
  keihin.append(s)

print(len(set(keihin)))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

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


    visited = [0]
    now = 0
    ind = 0
    my_append = visited.append
    for _ in range(K):
        a = A[now]-1
        if a in visited:
            ind = visited.index(a)
            break
        else:
            my_append(a)
            now = a

    loop_visited = visited[ind:]
    ans_ind = (K-ind) % len(loop_visited)

    print(loop_visited[ans_ind]+1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

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

    # N = 2*(10**4)
    # K = 10**18
    # A = [i+2 for i in range(N)]
    # A[-1] = 1
    # print(A)

    visited = [0]
    visited_set = set([0])
    now = 0
    ind = 0
    my_append = visited.append
    my_add = visited_set.add
    for i in range(K):
        a = A[now]-1
        if a in visited_set:
            ind = visited.index(a)
            break
        else:
            my_add(a)
            my_append(a)
            now = a
            # ind = i

    loop_visited = visited[ind:]
    ans_ind = (K-ind) % len(loop_visited)

    print(loop_visited[ans_ind]+1)


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

import numpy as np
n,m = map(int,input().split())
a = np.zeros(m)
b = np.zeros(m)
for i in range(m):
    a[i] , b[i] = map(int ,input().split())

a -= 1
b -= 1 
cnt = 0
in_task = np.zeros(m).astype(np.bool)

for i in range(n-1):
    a_bool = (a == i).astype(np.bool)
    if(a_bool.any()):
        in_task += a_bool
    if(np.any(b == i+1)):
        cnt += 1
        tmp = np.logical_not(in_task)
        a = a[tmp]
        b = b[tmp]
        in_task = np.zeros(a.shape).astype(np.bool)

print(cnt)



### FIXED CODE ###

import numpy as np
n,m = map(int,input().split())
a = np.zeros(m)
b = np.zeros(m)
for i in range(m):
    a[i] , b[i] = map(int ,input().split())

a -= 1
b -= 1 
cnt = 0

while(a.shape[0]):
    min_b = np.min(b)
    in_task = (a < min_b).astype(np.bool)
    cnt += 1
    tmp = np.logical_not(in_task)
    a = a[tmp]
    b = b[tmp]
    
print(cnt)
### BUGGY CODE ###

n = int(input())

ans = []
ans.append(int(input()))

for i in range(n - 1):
    t = int(input())
    ch = 0
    if t <= ans[-1]:
        ans.append(t)
    else:
        for j in range(len(ans)):
            if t > ans[j]:
                ans[j] = t
                ch += 1
                break

print(len(ans))


### FIXED CODE ###

def reverse_insort(a, x):
    lo = 0
    hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if x > a[mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo


n = int(input())

ans = []
ans.append(int(input()))

for i in range(n - 1):
    t = int(input())
    ch = 0
    if t <= ans[-1]:
        ans.append(t)
    else:
        ans[reverse_insort(ans, t)] = t

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

import sys
sys.setrecursionlimit(2000)

memo_gcm = {}
def uclid_gcm(a, b):
  if a < b:
    a += b
    b = a-b
    a=a-b
  if b == 0:
    return a
  elif (a, b) in memo_gcm.keys():
    return memo_gcm[(a, b)]
  else:
    r = a%b
    memo_gcm[(a, b)] = b if r == 0 else uclid_gcm(b, r)
    return memo_gcm[(a, b)]

def gcm_all(array):
  l = len(array)
  if l == 1:
    return array[0]
  else:
    tmp = []
    for i in range(l//2):
      tmp.append(uclid_gcm(array[i*2], array[i*2+1]))
    if l %2 == 1:
      tmp.append(uclid_gcm(array[-2],array[-1]))
    return gcm_all(tmp)

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

ans = 0
for i in range(N):
  t  = A[i]
  A[i] = 0
  ans = max(ans, gcm_all(A))
  A[i] = t
print(ans)



### FIXED CODE ###

from collections import deque
def gcm(a, b):
  if a < b:
    a = a+b
    b=a-b
    a = a-b
  if b == 0:
    return a
  else:
    r = a%b
    return b if r == 0 else gcm(b, r)
N = int(input())
A = list(map(int, input().split()))
L = deque([0])
for i in range(1, N):
  L.append(gcm(L[-1],A[i-1]))
R = deque([0])
for i in reversed(range(N-1)):
  R.appendleft(gcm(R[0],A[i+1]))
ans = 0
for i in range(N):
  ans = max(ans, gcm(L[i],R[i]))
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    graph = [[] for i in range(N)]
    prev = [-1 for i in range(N)]
    colors = {}
    edges = []
    for _ in range(N-1):
        a, b = MI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
        edges.append([a-1, b-1])
    max_edge = 0
    max_edge_idx = -1
    for i in range(len(graph)):
        length = len(graph[i])
        if length >= max_edge:
            max_edge = length
            max_edge_idx = i

    deque = cl.deque([max_edge_idx])
    while len(deque) > 0:
        target = deque.popleft()
        pre = prev[target]
        unused_colors = set(list(range(1, max_edge+1)))
        pre_key = (target, pre) if target < pre else (pre, target)
        if pre != -1:
            unused_colors.remove(colors[pre_key])

        connecteds = graph[target]

        for connected in connecteds:
            key = (target, connected) if target < connected else (
                connected, target)
            if key in colors:
                unused_colors.discard(colors[key])
                continue

            color = min(unused_colors)
            colors[key] = color
            prev[connected] = target
            deque.append(connected)
            unused_colors.remove(color)

    print(max_edge)

    for edge in edges:
        print(colors[(edge[0], edge[1])])


main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    graph = [[] for i in range(N)]
    prev = [-1 for i in range(N)]
    colors = {}
    edges = []
    for _ in range(N-1):
        a, b = MI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
        edges.append([a-1, b-1])
    max_edge = 0
    max_edge_idx = -1
    for i in range(len(graph)):
        length = len(graph[i])
        if length >= max_edge:
            max_edge = length
            max_edge_idx = i

    deque = cl.deque([max_edge_idx])
    while len(deque) > 0:
        target = deque.popleft()
        pre = prev[target]
        pre_key = (target, pre) if target < pre else (pre, target)
        used_color = 0
        if pre != -1:
            used_color = colors[pre_key]

        connecteds = graph[target]
        color = 1
        for connected in connecteds:
            key = (target, connected) if target < connected else (
                connected, target)
            if key in colors:
                continue
            if color == used_color:
                color += 1
            colors[key] = color
            prev[connected] = target
            deque.append(connected)
            color += 1

    print(max_edge)

    for edge in edges:
        print(colors[(edge[0], edge[1])])


main()
### BUGGY CODE ###

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

B=[0]*(n-1)
for i in range(1,n):
  B[i-1]=A[i]-min(A[:i])
print(B.count(max(B)))

### FIXED CODE ###

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

b=A[0]
B=[b]*(n-1)
for i in range(1,n):
  b=min(b,A[i])
  B[i-1]=A[i]-b
print(B.count(max(B)))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
d = N // 2
ans = []
def linking_up():
    if N % 2 == 0:
        for i in range(N):
            if i % 2 == 1:
                if A.count(i) == 2:
                    ans.append('a')
                else:
                    ans.append('b')
    else:
        for i in range(N):
            if i % 2 == 0 and i != 0:
                if A.count(i) == 2 and A.count(0) == 1:
                    ans.append('a')
                else:
                    ans.append('b')
linking_up()
if ans.count('a') == d:
    print(2 ** d)
else:
    print(0)
        




### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
mod=10**9+7
if n%2==0:
  for i in range(n):
    if a[i]!=(i//2)*2+1:
      print(0)
      exit()
  print(pow(2,n//2,mod))
else:
  for i in range(n):
    if a[i]!=((i+1)//2)*2:
      print(0)
      exit()
  print(pow(2,n//2,mod))
### BUGGY CODE ###

N = int(input())
A = map(int, input().split())
ans = 1

for i in A:
    ans = ans * i

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

### FIXED CODE ###

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

if 0 in A:
    print("0")
    exit(0)

for i in A:
    ans = ans * i
    if ans > 10**18:
        print("-1")
        exit(0) 

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

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

count = (K + 1) ** 3
for x in range(K + 1):
    for y in range(K + 1):
        for z in range(K + 1):
            if x + y + z != S:
                count -= 1

print(count)

### FIXED CODE ###

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

count = 0
for x in range(K + 1):
    for y in range(K + 1):
        if 0 <= S - (x + y) <= K:
            count += 1

print(count)
### BUGGY CODE ###

n = int(input())
l = []
ans =0
for i in range(n):
  a = int(input())
  l.append(a)
b = set(l)
for j in b:
  if l.count(j) %2 !=0:
    ans +=1
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
l = [0] * n
ans =0
for i in range(n):
  l[i] = int(input())
print( sum(s%2 for s in Counter(l).values()))
### BUGGY CODE ###

N,X,Y=map(int,input().split())
answers=[0]*(N-1)
for i in range(1,N+1):
    numbers=[a for a in range(1,N+1) if a!=i]
    for j in numbers:
        answer=min(abs(i-j),abs(X-i)+1+abs(j-Y),abs(i-Y)+1+abs(j-X))
        answers[answer-1]+=1
for a in answers:
    print(a//2)
    

### FIXED CODE ###

N,X,Y=map(int,input().split())
answers=[0]*(N-1)
for i in range(1,N+1):
    numbers=[a for a in range(1,N+1) if a!=i]
    for j in numbers:
        answer=min(abs(i-j),abs(X-i)+1+abs(j-Y),abs(i-Y)+1+abs(j-X))
        answers[answer-1]+=1
for a in answers:
    print(a//2)
### BUGGY CODE ###

N, Q = map(int, input().split())
s = input()
A = [1] * (N + 2)

for i in range(Q):
    t, d = input().split()
    for i, x in enumerate(s):
        if t == x:
            if d == 'L':
                A[i] += A[i + 1]
                A[i + 1] = 0
            else:
                A[i + 2] += A[i + 1]
                A[i + 1] = 0
                
print(sum(A[1 : -1]))

### FIXED CODE ###

N, Q = map(int, input().split())
s = input()

X = []
for i in range(Q):
    t, d = input().split()
    if d == 'L':
        X.append([t, -1])
    else:
        X.append([t, 1])
        
def check(m):
    i = m
    for x in X:
        if x[0] == s[i]:
            i += x[1]
            if i < 0:
                return -1
            if i >= N:
                return 1
    return 0

L, R = -1, N
while R - L > 1:
    M = (L + R) // 2
    if check(M) < 0:
        L = M
    else:
        R = M  
A = L

L, R = -1, N
while R - L > 1:
    M = (L + R) // 2
    if check(M) > 0:
        R = M
    else:
        L = M
B = R

print(B - A - 1)
### BUGGY CODE ###

N,K,Q=map(int, input().split())
#print(N,K,Q)
A=list()
for j in range(Q):
  A.append(int(input()))

#print(A)
#C=list()
for j in range(N):
  if Q-A.count(j+1)<K:
    print('Yes')
  else:
    print('No')
 
#print(C)




### FIXED CODE ###

N,K,Q=map(int, input().split())
score=[Q]*N
#print(score)
for j in range(Q):
  c=int(input())
  score[c-1] += -1
 
#print(score)

for j in range(N):
  if score[j]<K:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

import numpy as np

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

# N = 5
# A = [1, 1, 2, 1, 2]

for i in range(N):
    # i = 2
    A_sub = A.copy()
    A_sub.pop(i)

    A_sub = np.array(A_sub)

    # ans = 0
    # uni_vals = np.unique(A_sub)
    # for val in uni_vals:
    #     # val = uni_vals[0]
    #     n = np.where(A_sub == val)[0].shape[0]
    #     ans += (n*(n-1))/2
    dic = {}
    for val in A_sub:
        if val in dic.keys():
            dic[val] += 1
        else:
            dic[val] = 1
    ans = 0
    for val in dic.values():
        ans += (val*(val-1)/2)

    print(int(ans))


### FIXED CODE ###

from collections import defaultdict, Counter

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

d = defaultdict(int)
for a in A:
    d[a] += 1

all = 0
for val in d.values():
    all += val * (val - 1) / 2

all = int(all)
val_cnt = Counter(A)
for a in A:
    print(all - (val_cnt[a] - 1))
### BUGGY CODE ###

H,W = map(int,input().split())
List=[input() for i in range(H)]
A =[[1]*(W) for i in range(H)]
B =[[1]*(H) for i in range(W)]
for i in range(H):
    k = 0
    a = 0
    while k < W:
        if List[i][k]==".":
            a += 1
            k = k+1
        else:
            for j in range(a):
                A[i][k-j-1]=a
            A[i][k]=a
            a = 0
            k = k+1
    for j in range(a):
                A[i][k-j-1]=a
for i in range(W):
    k = 0
    a = 0
    while k < H:
        if List[k][i]==".":
            a += 1
            k = k+1
        else:
            for j in range(a):
                B[i][k-j-1]=a
            B[i][k] = 0
            a = 0
            k = k+1
    for j in range(a):
                B[i][k-j-1]= a
max = 0
for i in range(H):
    for j in range(W):
        if max < A[i][j] + B[j][i]:
            max = A[i][j] + B[j][i]
print(max-1)
        

### FIXED CODE ###

H,W = map(int,input().split())
List=[input() for i in range(H)]
A =[[1]*(W) for i in range(H)]
B =[[1]*(H) for i in range(W)]
for i in range(H):
    k = 0
    a = 0
    while k < W:
        if List[i][k]==".":
            a += 1
            k = k+1
        else:
            for j in range(a):
                A[i][k-j-1]=a
            A[i][k]=a
            a = 0
            k = k+1
    for j in range(a):
                A[i][k-j-1]=a
for i in range(W):
    k = 0
    a = 0
    while k < H:
        if List[k][i]==".":
            a += 1
            k = k+1
        else:
            for j in range(a):
                B[i][k-j-1]=a
            B[i][k] = 0
            a = 0
            k = k+1
    for j in range(a):
                B[i][k-j-1]= a
max = 0
for i in range(H):
    for j in range(W):
        if max < A[i][j] + B[j][i]:
            max = A[i][j] + B[j][i]
print(max-1)
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
ans = a[1]-a[0]
for i in range(n-1):
  k = max(a[i+1:]) - a[i]
  if k > ans:
      ans =  k
print(ans)



### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
nowmin = a[0]
nowmax = max(a[1:])
ans = nowmax - nowmin
for i in range(n-1):
  if a[i] == nowmax:
    nowmax = max(a[i+1:])
  if a[i] < nowmin:
    k = nowmax - a[i]
    if k > ans:
      ans =  k
      nowmin = a[i]


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

def main():
    a,b,k = map(int, input().split())

    for i in range(a, b+1):
        if i-a + 1 > k and b-i + 1 > k:
            continue
        print(i)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    a,b,k = map(int, input().split())

    i = a
    while True:
        if i > b:
            return
        if i-a + 1 > k:
            i = max(i, b-k+1)
            break
        print(i)
        i += 1
    while True:
        if i > b:
            break
        print(i)
        i += 1

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

from collections import deque   
n = int(input())
d = deque()
for _ in range(n):
    x = input().split()
    if (x[0][0] == 'i'):
        d.appendleft(int(x[1]))
    elif (x[0] == 'delete'):
        try:
            d.remove(int(x[1]))
        except ValueError:
            pass
    elif (x[0][6] == 'F'):
        d.popleft()
    else:
        d.pop()
print(*d)



### FIXED CODE ###

from collections import deque
n = int(input())
a = deque()
for i in range(n):
    c = input()
    if c == "deleteFirst":
        a.popleft()
    elif c == "deleteLast":
        a.pop()
    else:
        c, v = c.split()
        if c == "insert":
            a.appendleft(v)
        else:
            try:
                a.remove(v)
            except:
                pass
print(" ".join(a))
### BUGGY CODE ###

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

expect_value = [0]*N

for i in range(N):
    expect_value[i] = ((p[i] * (p[i]+1))/2) * (1/p[i])

ans = [0] * (N - K + 1)
for i in range(N - K + 1):
    ans[i] = sum(expect_value[i:i+K])
print(max(ans))

### FIXED CODE ###

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


def cal_expect(value):
    return ((value*(value+1))/2)*(1/value)

expect_value = [0]*N
expect_value[0] = cal_expect(p[0])

for i in range(1,K):
    expect_value[i] += expect_value[i-1] + cal_expect(p[i])

for i in range(K,N):
    expect_value[i] = expect_value[i-1] + cal_expect(p[i]) - cal_expect(p[i - K])

print(max(expect_value))
### BUGGY CODE ###

s=int(input())
for i in range(1,3501):
    for j in range(1,3501):
        t=4*i*j-i*s-j*s
        if t>0:
            if s*i*j%t==0:
                print(s*i*j//t,i,j)
                break
    else:
        continue
    break

### FIXED CODE ###

s=int(input())
for i in range(s//4,3501):
    for j in range(1,3501):
        t=4*i*j-i*s-j*s
        y=s*i*j
        if t>0 and s*i*j%t==0:
            print(s*i*j//t,i,j)
            exit()
### BUGGY CODE ###

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

# dp[i] = 足場i(0~n-1)に到着するコストの最小値
dp = [10**18]*(n)
dp[0] = 0

for i in range(n) :
    for j in range(1,k+1) :
        if i+j >= n :
            continue
        dp[i+j] = min(dp[i+j],dp[i]+abs(h[i]-h[i+j]))

print(dp[n-1])

### FIXED CODE ###

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

# dp[i] = 足場i(0~n-1)に到着するコストの最小値
dp = [10**18]*(n)
dp[0] = 0

for i in range(n) :
    for j in range(1,k+1) :
        if i+j >= n :
            continue
        dp[i+j] = min(dp[i+j],dp[i]+abs(h[i]-h[i+j]))

print(dp[n-1])
### BUGGY CODE ###

import heapq

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

b = []
for i in range(n):
    a[i] *= -1
    b.append(a[i])

heapq.heapify(b)

while True:
    p = heapq.heappop(b)
    q = a.index(p)
    for i in range(n):
        a[q-i] += n-i
        if a[q-i]>0:
            print('NO')
            exit()
    if set(a) == {0}:
        print('YES')
        exit()
    b = [a[i] for i in range(n)]
    heapq.heapify(b)




### FIXED CODE ###

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

s = sum(a)

if s%(n*(n+1)//2)!=0:
    print('NO')
    exit()

ss = s//(n*(n+1)//2)

b = [0 for i in range(n)]

# a[i]-a[i-1] = ss-b[i-1]*n
for i in range(n):
    b[i-1] = (ss-a[i]+a[i-1])//n
    if b[i-1]<0:
        print('NO')
        exit()

c = [0 for i in range(n)]
for i in range(n):
    c[0]+=b[i]*(n-i)

for i in range(1,n):
    c[i] = c[i-1] + ss - b[i-1]*n

if a==c:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(m):
    p = max(a)
    index = a.index(p)
    a[index] = a[index] // 2
print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] *= -1
import heapq
heapq.heapify(a)

for i in range(m):
    am =  -1 * heapq.heappop(a)
    am = am // 2
    heapq.heappush(a, -am)
print(-1 * sum(a))
### BUGGY CODE ###

s = input()
q = int(input())
query = [list(map(str, input().split())) for _ in range(q)]

order = True
for i in query:
    if i[0] == "1":
        order = not order
    elif i[1] == "1":
        if order:
            s = i[2] + s
        else:
            s += i[2]
    else:
        if order:
            s += i[2]
        else:
            s = i[2] + s
if not order:
    s = s[::-1]
print(s)

### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())
query = [list(map(str, input().split())) for _ in range(q)]

order = True
for i in query:
    if i[0] == "1":
        order = not order
    elif i[1] == "1":
        if order:
            s.appendleft(i[2])
        else:
            s.append(i[2])
    else:
        if order:
            s.append(i[2])
        else:
            s.appendleft(i[2])

if not order:
    s.reverse()
print("".join(s))