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

n,k = map(int,input().split())
MOD = 10**9+7

def comb(n,k):
  res = 1
  for i in range(k):
    res *= n-i
    res *= pow(i+1,MOD-2,MOD)
  return res%MOD

for i in range(k):
  #print(comb(k-1,i),comb(n-k+1,i+1))
  ans = comb(k-1,i) * comb(n-k+1,i+1)
  print(ans % MOD)

### FIXED CODE ###

n,k = map(int,input().split())
MOD = 10**9+7

history = {}
def comb(n,k):
  if (n,k) in history:
    return history[(n,k)]
  if k == 0:
    return 1
  res = (n-k+1)*pow(k,MOD-2,MOD)*comb(n,k-1)
  res = res%MOD
  history[(n,k)] = res
  history[(n,n-k)] = res
  return res

for i in range(k):
  #print(comb(k-1,i),comb(n-k+1,i+1))
  ans = comb(k-1,i) * comb(n-k+1,i+1)
  print(ans % MOD)
### BUGGY CODE ###

import numpy as np

N, K = map(int, input().split())
H = [int(i) for i in input().split()]

for i in range(K):
    H[np.argmax(H)] = 0
print(sum(H))

### FIXED CODE ###

N, K = map(int, input().split())
H = [int(i) for i in input().split()]

H.sort()

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

from itertools import combinations as c

import sys
input = sys.stdin.readline

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

ans = S.count("R") * S.count("G") * S.count("B")
for i, j in c(range(N), 2):
  k = 2 * j - i
  if k < N:
    A, B, C = S[i], S[j], S[k]
    """
    if A == B or B == C or C == A: continue
    ans -= 1
    """
    if A != B and B != C and C != A: ans -= 1
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

ans = S.count("R") * S.count("G") * S.count("B")
for i in range(N-2):
  for j in range(i+1, N-1):
    k = 2 * j - i
    if k < N:
      A, B, C = S[i], S[j], S[k]
      if A != B and B != C and C != A: ans -= 1

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

n = int(input())
ar = [[] for i in range(n)]
for i in range(n-1):
    ipt = list(map(int,input().split()))
    ar[ipt[0]-1].append((ipt[1]-1,ipt[2]))
    ar[ipt[1]-1].append((ipt[0]-1,ipt[2]))

ans = [[] for i in range(n)]
u = 0
ans[u] = 0
queue = [u] #キュー
check = [False]*n #訪問済み
check[u] = True
l = 1
while True:
    if l == 0:
        break
    u = queue.pop(0)
    l -= 1
    for v in ar[u]:
        if not check[v[0]]:
            check[v[0]] = True
            ans[v[0]] = ans[u] + v[1]
            queue.append(v[0])
            l+=1

for i in range(n):
    print(ans[i]%2)

### FIXED CODE ###

n = int(input())
ar = [[] for i in range(n)]
for i in range(n-1):
    ipt = list(map(int,input().split()))
    ar[ipt[0]-1].append((ipt[1]-1,ipt[2]))
    ar[ipt[1]-1].append((ipt[0]-1,ipt[2]))

ans = [-1 for i in range(n)]
u = 0
ans[u] = 0
queue = [u] #キュー
l = 1
while True:
    if l == 0:
        break
    u = queue.pop(0)
    l -= 1
    for v in ar[u]:
        if ans[v[0]] < 0:
            ans[v[0]] = ans[u] + v[1]
            queue.append(v[0])
            l+=1

for i in range(n):
    print(ans[i]%2)
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
for i in range(M):
    B,C=map(int,input().split())
    for j in range(B):
        A+=[C]
A=list(sorted(A,reverse=True))
print(sum(A[0:N]))

### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
BC=[[0,0] for i in range(M)]
for i in range(M):
    BC[i][0],BC[i][1]=map(int,input().split())

A=sorted(A)
BC=list(sorted(BC,reverse=True,key=lambda x: x[1]))

i=0
for B,C in BC:
    for j in range(i,min(N,i + B)):
        if A[j] < C:
            A[j] = C
            #B枚分先を飛ばす BCはCに関して降順のため問題ない
    i = i + B
 
print(sum(A))
### BUGGY CODE ###

N, P = map(int, input().split())
S = input()

if P == 2 or P == 5:
    def solve25(N, P, S):
        c = 0
        for i in range(N-1, -1, -1):
            if int(S[i]) % P == 0:
                # 以降桁を増やしてもOK
                c += i+1
        return c
    print(solve25(N, P, S))
else:
    def solve(N, P, S):
        rcounts = [0] * P
        rcounts[0] = 1 # sそのものが割り切れた場合に引き算する相手がいないから
        for i in range(len(S)):
            s = int(S[i:N])
            r = s % P
            rcounts[r] += 1
        c = 0
        for v in rcounts:
            if v > 1:
                c += v*(v-1)//2
        return c
    print(solve(N, P, S))


### FIXED CODE ###

N, P = map(int, input().split())
S = input()

if P == 2 or P == 5:
    def solve25(N, P, S):
        c = 0
        for i in range(N-1, -1, -1):
            if int(S[i]) % P == 0:
                # 以降桁を増やしてもOK
                c += i+1
        return c
    print(solve25(N, P, S))
else:
    def solve(N, P, S):
        rcounts = [0] * P
        rcounts[0] = 1 # sそのものが割り切れた場合に引き算する相手がいないから
        ints = 0
        for i, s in enumerate(S[::-1]):
            ints += int(s) * pow(10, i, P)
            r = ints % P
            rcounts[r] += 1
        c = 0
        for v in rcounts:
            c += v*(v-1)//2
        return c
    print(solve(N, P, S))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)

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


def func(b, m):
    if m == 0:
        return 0
    if m == 1:
        return b[0]

    if m % 2 == 0:
        ans0 = b[0] + func(b[2:], m - 2)
        ans1 = sum(b[i] for i in range(1, m, 2))
        ans = max(ans0, ans1)
    else:
        ans0 = b[0] + func(b[2:], m - 2)
        ans1 = b[1] + func(b[3:], m - 3)
        ans2 = sum(b[i] for i in range(2, m, 2))
        ans = max(ans0, ans1, ans2)

    return ans


ans = func(a, n)

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

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

a_cs = [0] * (n + 1)
a_cs[-2] = a[-1]
for i in reversed(range(n - 1)):
    a_cs[i] = a[i] + a_cs[i + 2]
# print(a_cs)

d = {}


def func(i):
    if i == n:
        return 0
    if i == n - 1:
        return a[-1]
    if i in d:
        return d[i]

    m = n - i
    if m % 2 == 0:
        ans0 = a[i] + func(i + 2)
        ans1 = a_cs[i + 1]
        ans = max(ans0, ans1)
    else:
        ans0 = a[i + 0] + func(i + 2)
        ans1 = a[i + 1] + func(i + 3)
        ans2 = a_cs[i + 2]
        ans = max(ans0, ans1, ans2)

    d[i] = ans
    return ans


ans = func(0)

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

A, B, C, D = map(int, input().split())
MOD = 998244353

dp = [[0] * (D + 2) for _ in range(C + 2)]
dp[A][B] = 1

for h in range(A, C + 1):
    for w in range(B, D + 1):
        d = dp[h][w] % MOD
        dp[h + 1][w] += d * w
        dp[h][w + 1] += d * h
        dp[h + 1][w + 1] -= d * w * h % MOD
print(dp[C][D] % MOD)


### FIXED CODE ###

A, B, C, D = map(int, input().split())
MOD = 998244353

dp = [[0] * (D + 2) for _ in range(C + 2)]
dp[A][B] = 1

for h in range(A, C + 1):
    for w in range(B, D + 1):
        d = dp[h][w] % MOD
        dp[h + 1][w] += d * w
        dp[h][w + 1] += d * h
        dp[h + 1][w + 1] -= d * w * h % MOD
print(dp[C][D] % MOD)
### BUGGY CODE ###

import sys

def exhaustiveSearch(A, m, i):
    if A[i] == m:
        return True
    elif i == len(A) - 1:
        return False

    return exhaustiveSearch(A, m, i + 1) or exhaustiveSearch(A, m - A[i], i + 1)

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    A = map(int, lines[1].split())
    M = map(int, lines[3].split())

    for m in M:
        if exhaustiveSearch(A, m, 0):
            print "yes"
        else:
            print "no"

### FIXED CODE ###

import sys

def exhaustiveSearch(A, m, i, s):
    if A[i] == m:
        return True
    elif i == len(A) - 1 or m < 0 or m > s:
        return False

    return exhaustiveSearch(A, m, i + 1, s) or exhaustiveSearch(A, m - A[i], i + 1, s)

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    A = map(int, lines[1].split())
    M = map(int, lines[3].split())
    s = sum(A)

    for m in M:
        if exhaustiveSearch(A, m, 0, s):
            print "yes"
        else:
            print "no"
### BUGGY CODE ###

from collections import defaultdict

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

d = defaultdict(list)
for i in range(N):
  d[int(S[i])].append(i)
    
ans = 0
for n1 in range(10):
  if not d[n1]:continue
  for n2 in range(10):
    if not d[n2]:continue
    if min(d[n1])>max(d[n2]): continue
    for n3 in range(10):
      if not d[n3]:continue
      if min(d[n1])>max(d[n3]) or min(d[n2])>max(d[n3]):continue
      for idx in d[n2]:
        if idx>min(d[n1]) and idx<max(d[n3]):
          ans += 1
          break
            
print(ans)

### FIXED CODE ###

from collections import defaultdict

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

d = defaultdict(list)
for i in range(N):
  d[int(S[i])].append(i)
    
ans = 0
for n1 in range(10):
  if not d[n1]:continue
  for n2 in range(10):
    if not d[n2]:continue
    if d[n1][0]>d[n2][-1]: continue
    for n3 in range(10):
      if not d[n3]:continue
      if d[n1][0]>d[n3][-1] or d[n2][0]>d[n3][-1]:continue
      for idx in d[n2]:
        if idx>d[n1][0] and idx<d[n3][-1]:
          ans += 1
          break
            
print(ans)
### BUGGY CODE ###

n = int(input())
p = list(input('').split())

count = 0
count2 = 0
for i in range(1,n):
    count = 0
    for j in range(i):
        if int(p[j]) >= int(p[i]):
            count += 1
    if count == i:
        count2 += 1

print(count2 + 1)

### FIXED CODE ###

n = int(input())
p = list(input('').split())

min = 10000000000
count = 0
for i in range(n):
    if min >= int(p[i]):
        count += 1
    if min >= int(p[i]):
        min = int(p[i])

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


s = int(input())

val = s
mp = {}
i= 0
while True:
  i+=1
  if val%2==0:
    val = val//2
  else:
    val = 2*val+1
  
  if val in mp:
    print(i)
    break
  else:
    mp[val] = 1

### FIXED CODE ###


s = int(input())

val = s
mp = {s:1}
i= 1
while True:
  i+=1
  if val%2==0:
    val = val//2
  else:
    val = 3*val+1
  
  if val in mp:
    print(i)
    break
  else:
    mp[val] = 1
### BUGGY CODE ###

n=int(input())
S=["".join(sorted(input())) for i in range(n)]
Sn=set(S)
cnt=0
for s in Sn:
    if S.count(s)>=2:
        cnt+=S.count(s)*(S.count(s)-1)//2
print(cnt)
        
    


### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
for i in range(n):
  s[i] = ''.join(sorted(s[i]))
t = {}
for i in range(n):
  if s[i] in t:
    t[s[i]] += 1
  else:
    t[s[i]] = 1
print(sum(t[k] * (t[k] -1) // 2 for k in t))
### BUGGY CODE ###

N = int(input())
S = list(str(input()))
used = [0]*1000
count = 0
for i in range(N-2):
  for j in range(i+1,N-1):
    for k in range(j+1,N):
      if used[int(S[i]+S[j]+S[k])] == 0:
        count += 1
        used[int(S[i]+S[j]+S[k])] = 1
print(count)

### FIXED CODE ###

N = int(input())
S = list(str(input()))

used = [0]*1000

for i in range(1000):
  stri = str(i)
  if len(stri) == 2:
    stri = "0"+stri
  elif len(stri) == 1:
    stri = "00"+stri
  count = 0
  for j in range(N):
    if S[j] == stri[count]:
      count += 1
    if count == 3:
      used[i] = 1
      break

print(sum(used))
### BUGGY CODE ###

#--d--#
import sys,math,collections,itertools
input = sys.stdin.readline

def solve(i):#-スタートする番号-#
    visit = set([i])
    tmp = [] #訪れた場所から飛ぶ時の得点
    #tmp_sum = [] #得点の累積和
    while True:
        tmp.append(C[i-1])
        next_point = P[i-1]
        if next_point not in visit:
            visit |=set([next_point])
            i = next_point
        else:
            break
    roopLength = len(tmp)
    roop_sum = sum(tmp)
    cum_sum = list(itertools.accumulate(tmp))
    #print(roopLength,tmp,list(cum_sum))
    #print(visit)
    #-もしループで負になるなら、roopLength or Kの小さいほうの中でcum_sumの大きいもの
    if roop_sum <=0:
        ans = -float('inf')
        for i in range(min(K,roopLength)):
            ans = max(ans,cum_sum[i])
    #ループ長さｘ２がKよりおおきいなら、Kまで足し上げる
    elif roopLength * 2 >=K:
        point = 0
        ans = -float('inf')
        for i in range(K):
            point +=  tmp[i%roopLength]
            ans = max(ans,point)
    #ループ長さｘ２がKみ満たないなら、２週分残したとこまでループさせて、足し上げる
    elif roopLength *2 < K:
        point = roop_sum*(K//roopLength-1)
        ans = -float('inf')
        for i in range(roopLength+K%roopLength):
            point += tmp[i%roopLength]
            ans = max(ans,point)
    return ans


N,K=list(map(int,input().split()))
P=list(map(int,input().split()))
C=list(map(int,input().split()))
ans = -float('inf')
for i in range(N):
    point = solve(i+1)
    ans = max(point,ans)
print(ans)
    



### FIXED CODE ###

#--d--#
import sys,math,collections,itertools
input = sys.stdin.readline

def solve(i):#-スタートする番号-#
    visit = set([i])
    tmp = [] #訪れた場所から飛ぶ時の得点
    #tmp_sum = [] #得点の累積和
    while True:
        tmp.append(C[i-1])
        next_point = P[i-1]
        if next_point not in visit:
            visit |=set([next_point])
            i = next_point
        else:
            break
    roopLength = len(tmp)
    roop_sum = sum(tmp)
    cum_sum = list(itertools.accumulate(tmp))
    #print(roopLength,tmp,list(cum_sum))
    #print(visit)
    #-もしループで負になるなら、roopLength or Kの小さいほうの中でcum_sumの大きいもの
    if roop_sum <=0:
        ans = -float('inf')
        for i in range(min(K,roopLength)):
            ans = max(ans,cum_sum[i])
    #ループ長さｘ２がKよりおおきいなら、Kまで足し上げる
    elif roopLength * 2 >=K:
        point = 0
        ans = -float('inf')
        for i in range(K):
            point +=  tmp[i%roopLength]
            ans = max(ans,point)
    #ループ長さｘ２がKみ満たないなら、２週分残したとこまでループさせて、足し上げる
    elif roopLength *2 < K:
        point = roop_sum*(K//roopLength-1)
        ans = -float('inf')
        for i in range(roopLength+K%roopLength):
            point += tmp[i%roopLength]
            ans = max(ans,point)
    return ans


N,K=list(map(int,input().split()))
P=list(map(int,input().split()))
C=list(map(int,input().split()))
ans = -float('inf')
for i in range(N):
    point = solve(i+1)
    ans = max(point,ans)
print(ans)
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(4100000)
n, m, k = map(int, input().split())
F = [deque([]) for i in range(n)] #Friend
B = [deque([]) for i in range(n)] #Block
#友達関係
for i in range(m):
    a, b = map(int, input().split())
    F[a-1].append(b)
    F[b-1].append(a)

#ブロック関係
for i in range(k):
    c, d = map(int, input().split())
    B[c-1].append(d)
    B[d-1].append(c)
#print('F=',F)
#print('B=',B)

def using_DFS(p):
    if G[p] == 0:
        G[p] = num
        for j in F[p]:
            if G[j-1] == 0:
                using_DFS(j-1)
            else:   #すでに登場
                pass
    else:
        pass

#DFSで連結部分ごとのグループに分ける
G = [0] * n #Group
S = deque([])   #Size
num = 0
for i in range(n):
    if G[i] == 0:
        num += 1
        t = 0
        using_DFS(i)
        S.append(G.count(num))
    else:
        pass
#print('G=',G)
#print('S=',S)

#答えの計算
for i in range(n):
    ans = S[G[i]-1] - 1
    #ブロック関係がこの中で何人いるか
    for j in B[i]:
        if G[j-1] == G[i]:
            ans -= 1
        else:
            pass
    #直接の友達関係がこの中で何人いるか
    for k in F[i]:
        if G[k-1] == G[i]:
            ans -= 1
        else:
            pass
    print(ans)

### FIXED CODE ###

import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]
    
    rks = [None] *n
    sys.setrecursionlimit(10**9)
    # r: どの連結成分に存在するかをメモするid
    def dfs(graph,s,r):
        if rks[s] is None:
            rks[s] = r
        for i in range(len(graph[s])):
            if rks[graph[s][i]-1] is not None:
                continue
            dfs(graph, graph[s][i]-1,r)

    for i in range(m):
        a,b = map(int, input().split())
        fgraph[a-1].append(b)
        fgraph[b-1].append(a)

    # print(fgraph)
    #print(bgraph)
    # 連結成分に対してid的なindexをつける
    c = -1
    for i in range(n):
        if rks[i] is None:
            c += 1
            dfs(fgraph, i, c)
    
    for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)

    counter = Counter(rks)
    for i in range(n):
        # counter[rks[i]] 連結成分のサイズ
        # len(fgraph[i]) 友達の数
        # len(bgraph[i]) 連結成分内のブロックの数
        # 1 自分
        print(counter[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

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

n = int(input())
A = sorted(list(map(int, input().split())))
amax =max(A)
amin =min(A)
ans = 0
for i in range(amin - 1,amax + 2):
    ans = max(ans,A.count(i - 1) + A.count(i) + A.count(i + 1))
print(ans)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
lst =[0] * (10 ** 5 +10)
for i in A:
    if i > 0:
        lst[i - 1] += 1
    lst[i] += 1
    lst[i + 1] += 1
print(max(lst))
### BUGGY CODE ###

n,k=map(int,input().split())
#(i,j)=7i+j-7
x=0
for i in range(11):
    if (9*i)%11==k:
        x=i
        break
ans=0
for i in range((7*n)//11+1):
    s=11*i+x
    if s>7*n-7:
        continue
    if s<=7:
        continue
    if s%7==0 or s%7==1:
        continue
    else:
        ans+=1
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
#(i,j)=7i+j-7
x=0
for i in range(11):
    if (9*i)%11==k:
        x=i
        break
K=0
L=0
for i in range(1,78):
    if i%11!=x:
        continue
    if i%7<=1:
        continue
    K+=1
    if i<=7:
        L+=1
P=0
for i in range(1,7*(n%11)+1):
    if i%11!=x:
        continue
    if i%7<=1:
        continue
    if i>(7*(n%11)-7):
        continue
    P+=1
print(K*(n//11)+P-L)
### BUGGY CODE ###

from collections import Counter
n, m = map(int, input().split())
A = list(map(int, input().split()))
cA = Counter(A)
for i in range(m):
    b, c = map(int, input().split())
    while b>0 and min(cA)<c:
        if b>cA[min(cA)]:
            cA[c] += cA[min(cA)]; b -= cA[min(cA)]
            del cA[min(cA)]
        else:
            cA[min(cA)] -= b
            cA[c] += b
            b = 0
ans = 0
for key, val in cA.items():
    ans += key*val
print(ans)

### FIXED CODE ###

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

B = [[] for _ in range(m)]
for i in range(m):
    B[i] = list(map(int, input().split()))
B.sort(key=lambda x: -x[1])

_A = []
cnt = 0
for i in range(m):
    _A.extend([B[i][1]]*B[i][0])
    cnt += B[i][0]
    if cnt > n:
        break
A += _A
A.sort(reverse=True)
print(sum(A[:n]))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = str(input())

l_list = []
r_list = []

ans = []
for x in range(Q):
    l, r = map(int, input().split())
    sub_str = S[l-1:r]
    ans = sub_str.count('AC')
    print(ans)

### FIXED CODE ###

N, Q = map(int, input().split())
S = str(input())

l_list = []
r_list = []

s_count = [0]
for i in range(len(S) - 1):
    if S[i:i+2] == 'AC':
        s_count.append(1)
    else:
        s_count.append(0)
#print(s_count)

n_count = []
n_sum = 0
for n in s_count:
    n_sum = n_sum + n
    n_count.append(n_sum)

#print(n_count)


for x in range(Q):
    l, r = map(int, input().split())
    ans = n_count[r-1] - n_count[l-1]
    print(ans)
### BUGGY CODE ###

import sys
N,M,K=map(int,input().split())
tn=[0]*N
l=[i for i in range(N)]
for i in range(M):
    A,B=map(lambda x:int(x)-1,input().split())
    t=B
    tn[A]+=1
    tn[B]+=1
    while 1:
        if l[t]==t:
            l[t]=l[A]
            break
        l[t],t=l[A],l[t]
ln=[0]*N
for i in range(N):
    if l[i]!=i:
        c=[i]
        t=l[i]
        while 1:
            if l[t]==t:
                for j in c:
                    l[j]=t
                break
            t=l[t]
        ln[t]+=1
    else:
        ln[i]+=1
for i in range(K):
    C,D=map(lambda x: int(x)-1,input().split())
    if l[C]==l[D]:
        tn[C]+=1
        tn[D]+=1
for i in range(N):
    print(ln[l[i]]-tn[i]-1,end=" ")


### FIXED CODE ###

import sys
N,M,K=map(int,input().split())
s=[[]for i in range(N)]
tn=[0]*N
sys.setrecursionlimit(200000)
for i in range(M):
    a,b=map(int,input().split())
    s[a-1].append(b)
    s[b-1].append(a)
    tn[a-1]+=1
    tn[b-1]+=1
l=[None]*N
def hu(n,t):
    l[n]=t
    for i in s[n]:
        if l[i-1]==None:
            l[i-1]=t
            hu(i-1,t)
t=0
for i in range(N):
    if l[i]==None:
        hu(i,t)
        t+=1
c=[0]*t
for i in l:
    c[i]+=1
for i in range(K):
    a,b=map(int,input().split())
    if l[a-1]==l[b-1]:
        tn[a-1]+=1
        tn[b-1]+=1
for i in range(N):
    print(c[l[i]]-tn[i]-1,end=" ")
### BUGGY CODE ###

S = input()
N = int(input())
for i in range(N):
  X = input().split()
  if len(X) == 1:
    NS = S[::-1]
  else:
    if X[1] == "1":
      NS = X[2] + S
    else:
      NS = S + X[2]
  S = NS
print(S)


### FIXED CODE ###

S = input()
f = ""
N = int(input())
direct = 0
for i in range(N):
  X = input().split()
  if len(X) == 1:
    direct = 1 - direct
  else:
    if (X[1] == "1" and direct == 0) or (X[1] == "2" and direct == 1):
      f += X[2]
    else:
      S += X[2]
print(f[::-1]+S) if direct == 0 else print(S[::-1]+f)
### BUGGY CODE ###

n,k = map(int,input().split())
cnt = 0
for i in range(k,n+2):
    front = 0
    end = 0
    for j in range(i):
        front += j
    for j in range(n,n-i,-1):
        end += j
    if end-front+1 > 0:
        cnt += end-front+1
print(cnt)

### FIXED CODE ###

n,k = map(int,input().split())
cnt = 0
for i in range(k,n+2):
    if 0.5*(n-i)*(n-i+1) >= 0:
        minus = 0.5*(n-i)*(n-i+1)
    else:
        minus = 0
    front = 0.5*(i-1)*i
    end = 0.5*n*(n+1) - minus
    cnt += end-front+1
print(int(cnt%(10**9+7)))
### BUGGY CODE ###

n,m=map(int,input().split())
data=[]
p=[0]*n
y=[[] for _ in range(n)]
for i in range(m):
    p_i,y_i=map(int,input().split())
    data.append([p_i,y_i])
    p[p_i-1]+=1
    y[p_i-1].append(y_i)
for i in range(n):
    if p[i]!=0:
        y[i].sort()
for i in range(m):
    ans_p=data[i][0]
    ans_y=y[ans_p-1].index(data[i][1])+1
    ans_p=(str(ans_p)).zfill(6)
    ans_y=(str(ans_y)).zfill(6)
    print(ans_p+ans_y)

### FIXED CODE ###

from operator import itemgetter
n,m=map(int,input().split())
data=[]
for i in range(m):
    p_i,y_i=map(int,input().split())
    data.append([p_i,y_i,i])
data.sort()
data.append([n+1,0,m])
buf=1
for i in range(m):
    data[i].append(buf)
    if data[i][0]==data[i+1][0]:
        buf+=1
    else:
        buf=1
data.sort(key=itemgetter(2))
for i in range(m):
    ans_p=data[i][0]
    ans_y=data[i][3]
    ans_p=(str(ans_p)).zfill(6)
    ans_y=(str(ans_y)).zfill(6)
    print(ans_p+ans_y)
### BUGGY CODE ###

import numpy as np


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n = int(input())
A = np.array(list(map(int, input().split())), dtype=np.int64)
all_pattern = n * (n+1) // 2
check = all_pattern // 2
X = np.sort(A)

left = 0
right = n

while left + 1 < right:
    idx = (left+right) // 2
    x = X[idx]
    up_or_down = np.where(A >= x, 1, -1)
    cumsum = np.cumsum(up_or_down) + n

    tree = Bit(2*n+1)
    pattern = 0
    for i, p in enumerate(cumsum, 1):
        tree.add(p, 1)
        pattern += tree.sum(p)

    if pattern >= check:
        left = idx
    else:
        right = idx

print(X[left])

### FIXED CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n = int(input())
A = list(map(int, input().split()))
all_pattern = n * (n+1) // 2
check = all_pattern // 2 + bool(all_pattern % 2)
X = sorted(A)

left = 0
right = n

while left + 1 < right:
    idx = (left+right) // 2
    x = X[idx]
    up_or_down = [1 if num >= x else -1 for num in A]
    cumsum = [n]
    total = n
    for point in up_or_down:
        total += point
        cumsum.append(total)

    tree = Bit(2*n+1)
    pattern = 0
    for p in cumsum:
        pattern += tree.sum(p)
        tree.add(p, 1)

    if pattern >= check:
        left = idx
    else:
        right = idx

print(X[left])