Harryxun/sft_time huggingface dataset:
### 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
for i in range(m):
    a, b = map(int, input().split())
    F[a-1].append(b)
    F[b-1].append(a)

#DFSで連結部分ごとのグループに分ける
G = [0] * n #Group
gid = 0 #group id

#DFSを行うための関数
def using_DFS(p):
    if G[p] == 0:
        G[p] = gid
        for j in F[p]:
            if G[j-1] == 0:
                using_DFS(j-1)
            else:   #すでに登場
                pass
    else:
        pass

for i in range(n):
    if G[i] == 0:
        gid += 1
        using_DFS(i)
    else:
        pass
#print('G=',G)
#print('S=',S)

#ブロック関係
BinG = [deque([]) for i in range(n)] #Block in Group
for i in range(k):
    c, d = map(int, input().split())
    if G[c-1] == G[d-1]:
        BinG[c-1].append(d)
        BinG[d-1].append(c)
    else:
        pass
#print('F=',F)
#print('B=',B)

for i in range(n):
    ans = G.count(G[i]) - 1 - len(F[i]) - len(BinG[i])
    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())
S = input()

diff_dic = {}
diff_dic[('R', 'G')] = []
diff_dic[('R', 'B')] = []
diff_dic[('G', 'R')] = []
diff_dic[('G', 'B')] = []
diff_dic[('B', 'G')] = []
diff_dic[('B', 'R')] = []

R_lst = [0] * N
G_lst = [0] * N
B_lst = [0] * N

r_cnt = 0
g_cnt = 0
b_cnt = 0

cnt = 0
for i in range(N):
    if S[i] == 'R':
        r_cnt += 1
    elif S[i] == 'G':
        g_cnt += 1
    else:
        b_cnt += 1

    R_lst[i] = r_cnt
    G_lst[i] = g_cnt
    B_lst[i] = b_cnt

    for j in range(i):
        d = i - j
        if (S[i] == 'R' and S[j] == 'G') or (S[i] == 'G' and S[j] == 'R'):
            if j - 1 >=0 and B_lst[j - 1] > 0:
                cnt += B_lst[j - 1]
                if j - d >= 0 and S[j - d] == 'B':
                    cnt -= 1

        if (S[i] == 'G' and S[j] == 'B') or (S[i] == 'B' and S[j] == 'G'):
            if j - 1 >=0 and R_lst[j - 1] > 0:
                cnt += R_lst[j - 1]
                if j - d >= 0 and S[j - d] == 'R':
                    cnt -= 1

        if (S[i] == 'B' and S[j] == 'R') or (S[i] == 'R' and S[j] == 'B'):
            if j - 1 >= 0 and G_lst[j - 1] > 0:
                cnt += G_lst[j - 1]
                if j - d >= 0 and S[j - d] == 'G':
                    cnt -= 1

print(cnt)



### FIXED CODE ###

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

diff_dic = {}
diff_dic[('R', 'G')] = []
diff_dic[('R', 'B')] = []
diff_dic[('G', 'R')] = []
diff_dic[('G', 'B')] = []
diff_dic[('B', 'G')] = []
diff_dic[('B', 'R')] = []

R_lst = [0] * N
G_lst = [0] * N
B_lst = [0] * N

r_cnt = 0
g_cnt = 0
b_cnt = 0

cnt = 0
for i in range(N):
    if S[i] == 'R':
        r_cnt += 1
    elif S[i] == 'G':
        g_cnt += 1
    else:
        b_cnt += 1

    R_lst[i] = r_cnt
    G_lst[i] = g_cnt
    B_lst[i] = b_cnt

    for j in range(i):
        d = i - j
        if (S[i] == 'R' and S[j] == 'G') or (S[i] == 'G' and S[j] == 'R'):
            if j - 1 >=0 and B_lst[j - 1] > 0:
                cnt += B_lst[j - 1]
                if j - d >= 0 and S[j - d] == 'B':
                    cnt -= 1

        if (S[i] == 'G' and S[j] == 'B') or (S[i] == 'B' and S[j] == 'G'):
            if j - 1 >=0 and R_lst[j - 1] > 0:
                cnt += R_lst[j - 1]
                if j - d >= 0 and S[j - d] == 'R':
                    cnt -= 1

        if (S[i] == 'B' and S[j] == 'R') or (S[i] == 'R' and S[j] == 'B'):
            if j - 1 >= 0 and G_lst[j - 1] > 0:
                cnt += G_lst[j - 1]
                if j - d >= 0 and S[j - d] == 'G':
                    cnt -= 1

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

x,y = map(int,input().split())
def combinations_count(n, r): #組み合わせ(nCr)
    import math
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
if 1/2 <= y/x <= 2 and (x+y)/3 % 1 == 0:
    yy = (x+y)/3
    u = y - yy
    r = yy - u
    print(combinations_count(yy, min(r,yy-r))%(10**9+7))
else:
    print(0)

### FIXED CODE ###

x,y = map(int,input().split())
def comb(n,m,p=10**9+7):
    if n < m : return 0
    if n < 0 or m < 0:return 0
    m = min(m, n-m)
    top = bot = 1
    for i in range(m):
        top = top*(n-i) % p
        bot = bot*(i+1) % p
    bot = pow(bot, p-2, p)
    return top*bot % p
if 1/2 <= y/x <= 2 and (x+y)/3 % 1 == 0:
    yy = int((x+y)/3)
    u = int(y - yy)
    r = int(yy - u)
    print(comb(yy,r)%(10**9+7))
else:
    print(0)
### BUGGY CODE ###

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

import collections
import copy

ans = 0

for i in range(len(A)):
  ans = 0
  list = copy.copy(A)
  list.pop(i)
  c = collections.Counter(list)
  #for v in c.values():
  #  ans += (v*(v-1)/2)
  a = sum([int((i*i-i)/2) for i in c.values()])
  print(a)
  #print(int(ans))

### FIXED CODE ###

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

tot = 0
c = collections.Counter(copy.copy(A))
for v in c.values():
  tot += (v*(v-1)/2)

for n in A:
  ans = tot
  ans -= c[n]*(c[n]-1)/2
  ans += (c[n]-1)*(c[n]-2) / 2 
  print(int(ans))
### BUGGY CODE ###

a, b, k = map(int, input().split())
r = [x for x in range(a, b + 1)]
for x in sorted(set(r[:k]) | set(r[-k:])):
    print(x)


### FIXED CODE ###

a, b, k = map(int, input().split())
r = range(a, b + 1)
for x in sorted(set(r[:k]) | set(r[-k:])):
    print(x)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())[:-1]
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,S = map(int,input().split())
MOD = 998244353
A = list(map(int,input().split()))
dp = [[0]*(S+1) for _ in range(N)]
if A[0] <= S:
    dp[0][A[0]] = 1
dp[0][0] = 2
for i in range(1,N):
    a = A[i]
    for j in range(S+1):
        dp[i][j] += 2*dp[i-1][j]
        if j - a < 0:
            continue
        else:
            dp[i][j] += dp[i-1][j-a]
        dp[i][j] %= MOD
print(dp[N-1][S]%MOD)

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())[:-1]
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]

N,S = map(int,input().split())
MOD = 998244353
A = list(map(int,input().split()))
dp = [[0]*(S+1) for _ in range(N)]
if A[0] <= S:
    dp[0][A[0]] = 1
dp[0][0] = 2
for i in range(1,N):
    a = A[i]
    for j in range(S+1):
        dp[i][j] += 2*dp[i-1][j] % MOD
        if j - a < 0:
            continue
        else:
            dp[i][j] += dp[i-1][j-a]
        dp[i][j] %= MOD
print(dp[N-1][S])
### BUGGY CODE ###

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

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

# c = [ i for i in a if i%2!=0 ]
# if len(c)!=0:
#     print(0)
#     exit()

b = list(map( lambda x : x//2 , a ))

# print(a)
# print(b)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

chls = []
for i in range(n):
    f = factorization(a[i])
    num2 = f[0][1]
    chls.append(num2)
if len(list(set(chls)))!=1:
    print(0)
    exit()

from fractions import gcd
from functools import reduce

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

l = lcm_list(b)
# print(l)
# if l>m:
#     print(0)
#     exit()

pmax = (m-l) // (2*l)
# print(pmax)

ans = pmax + 1

print(ans)

### FIXED CODE ###

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

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

# c = [ i for i in a if i%2!=0 ]
# if len(c)!=0:
#     print(0)
#     exit()

b = list(map( lambda x : x//2 , a ))

# print(a)
# print(b)

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])

#     if temp!=1:
#         arr.append([temp, 1])

#     if arr==[]:
#         arr.append([n, 1])

#     return arr

# chls = []
# for i in range(n):
#     f = factorization(a[i])
#     num2 = f[0][1]
#     chls.append(num2)
# if len(list(set(chls)))!=1:
#     print(0)
#     exit()

def count2inNumber(n):
    count = 0
    while n%2==0:
        n //= 2
        count += 1
    return count

chls = []
for i in range(n):
    count = count2inNumber(a[i])
    chls.append(count)
if len(list(set(chls)))!=1:
    print(0)
    exit()

from fractions import gcd
from functools import reduce

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

l = lcm_list(b)
# print(l)
# if l>m:
#     print(0)
#     exit()

pmax = (m-l) // (2*l)
# print(pmax)

ans = pmax + 1

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

N, M = map(int, input().split())
ls = [[int(x) for x in input().split()] for _ in range(N)]

q = [[0] for _ in range(M)]
for a, b in ls:
    if a <= M:
        q[M-a].append(b)

# print(q)

pool = [0]
answer = 0
for x in reversed(q):
    x.append(sorted(pool, reverse=True)[0])
    m = max(x)
    answer += m
    pool += x
    pool.remove(m)
    

print(answer)

### FIXED CODE ###

N, M = map(int, input().split())
ls = [[int(x) for x in input().split()] for _ in range(N)]


q = [[0] for _ in range(M)]
for a, b in ls:
    if a <= M:
        q[M-a].append(b*-1)

# print(q)

from heapq import heappop, heappush

pool = []
answer = 0
for x in reversed(q):
    for y in x:
        heappush(pool, y)
    m = heappop(pool)*-1
    answer += m
    

print(answer)
### BUGGY CODE ###

n,m,k=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
AS=[0]
BS=[0]
r=[]
for i in A:
  if i+AS[-1]>k:
    break
  AS.append(i+AS[-1])
for i in B:
  if i+BS[-1]>k:
    break
  BS.append(i+BS[-1])
for i in range(len(AS)):
  for j in range(len(BS)):
    if AS[i]+BS[j]<=k:
      r.append(i+j)
print(sorted(r)[-1])

### FIXED CODE ###

n,m,k=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
AS=[0]
BS=[0]
r=0
for i in A:
  if i+AS[-1]<=k:
    AS.append(i+AS[-1])
  else:
    break
    
for i in B:
  if i+BS[-1]<=k:
    BS.append(i+BS[-1])
  else:
    break
    
j=len(BS)-1
for i in range(len(AS)):
  while AS[i]+BS[j]>k:
    j-=1
  r=max(r,i+j)
print(r)
### BUGGY CODE ###

import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    F = [int(f) for f in input().split()]
    A.sort(reverse = True)
    F.sort()
    low, high = -1, 10 ** 13
    while high - low > 1:
        mid = (low + high) // 2
        count = 0
        for i in range(N):
            counterF = mid // F[i] 
            if counterF < A[i]: count += A[i] - counterF
        if count <= K: high = mid
        else: low = mid
    print(high)
         
    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    F = [int(f) for f in input().split()]
    A.sort(reverse = True)
    F.sort()
    low, high = -1, 10 ** 12 + 1
    while high - low > 1:
        mid = (low + high) // 2
        count = 0
        for i in range(N):
            if A[i] * F[i] > mid: count += A[i] - (mid // F[i])
        if count > K: low = mid
        else: high = mid
    print(high)

    return 0

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

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

mod = 10**9+7


def p(m,n):
    a = 1
    for i in range(n):
        a = a*(m-i)
    return a

def p_mod(m,n,mod):
    a = 1
    for i in range(n):
        a = a*(m-i) % mod
    return a

def c(m,n):
    return p(m,n) // p(n,n)

def c_mod(m,n,mod):
    return (p_mod(m,n,mod)*pow(p_mod(n,n,mod),mod-2,mod)) % mod

C = [0]*(N-K+1)  #C[i] = (N-i-1)C_(K-1),予め二項係数を計算しておく
for i in range(N-K+1):
    if i == 0:
        C[i] = c_mod(N-1,K-1,mod)
    else:
        C[i] = C[i-1]*(N-K-i+1)*pow(N-i,mod-2,mod)

#各Aの元が何回max,minに採用されるかを考える

ans = 0
for i in range(N-K+1):
    ans -= (A[i]*C[i]) % mod

A.reverse()
for i in range(N-K+1):
    ans += (A[i]*C[i]) % mod

print(ans % mod)

### FIXED CODE ###

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

mod = 10**9+7


def p(m,n):
    a = 1
    for i in range(n):
        a = a*(m-i)
    return a

def p_mod(m,n,mod):
    a = 1
    for i in range(n):
        a = a*(m-i) % mod
    return a

def c(m,n):
    return p(m,n) // p(n,n)

def c_mod(m,n,mod):
    return (p_mod(m,n,mod)*pow(p_mod(n,n,mod),mod-2,mod)) % mod

C = [0]*(N-K+1)  #C[i] = (N-i-1)C_(K-1),予め二項係数を計算しておく
for i in range(N-K+1):
    if i == 0:
        C[i] = c_mod(N-1,K-1,mod)
    else:
        C[i] = (C[i-1]*(N-K-i+1)*pow(N-i,mod-2,mod)) % mod

#各Aの元が何回max,minに採用されるかを考える

ans = 0
for i in range(N-K+1):
    ans -= (A[i]*C[i]) % mod

A.reverse()
for i in range(N-K+1):
    ans += (A[i]*C[i]) % mod

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

import sys
N=int(input())
L=list(map(int,input().split()))
L.sort(reverse=True)
total = 0
def bisect_left_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番左側のidxとなる。
    '''
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok


for i in range(N):
  for j in range(i + 1, N):
    a = L[i] - L[j]
    total += max(bisect_left_reverse(L, a) - j - 1, 0)

print(total)


### FIXED CODE ###

import sys
from bisect import bisect_left
N=int(input())
L=list(map(int,input().split()))
L.sort()
total = 0
for i in range(N):
  for j in range(i + 1, N):
    a = L[i] + L[j]
    total += max(bisect_left(L, a) - j - 1, 0)

print(total)
### BUGGY CODE ###

def main():
    from collections import namedtuple

    Ratio = namedtuple('Ratio', 'gold, silver copper')

    def convert(n, Rfrm, Rto):
        Df = Ratio(*(t - f for f, t in zip(Rfrm, Rto)))

        ret = n

        g_max = n // Rfrm.gold if Df.gold > 0 else 0
        for g in range(g_max + 1):
            dg = Df.gold * g
            s_max = (n - Rfrm.gold * g) // Rfrm.silver if Df.silver > 0 else 0
            for s in range(s_max + 1):
                ds = Df.silver * s
                b = (n - Rfrm.gold * g - Rfrm.silver * s) // Rfrm.copper if Df.copper > 0 else 0

                db = Df.copper * b
                ret = max(ret, n + dg + ds + db)

        return ret

    n = int(input())
    Ra = Ratio(*map(int, input().split()))
    Rb = Ratio(*map(int, input().split()))

    ret = convert(n=n, Rfrm=Ra, Rto=Rb)
    ret = convert(n=ret, Rfrm=Rb, Rto=Ra)
    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

N = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())

# A : ドングリと金属に変える
# B : 全部ドングリに変える
# B : ドングリと金属に変える（無駄な操作でロスがないので、いったんドングリ化してよい）
# A : ドングリに変える

dp1 = list(range(N + 1))  # dp1[巣から持ってきたドングリ数] = 取引所 B で持てる最大ドングリ数
dp1[0] = 0
for i in range(N + 1):
    if i >= ga:
        dp1[i] = max(dp1[i], dp1[i - ga] + gb)
    if i >= sa:
        dp1[i] = max(dp1[i], dp1[i - sa] + sb)
    if i >= ba:
        dp1[i] = max(dp1[i], dp1[i - ba] + bb)

N = dp1[N]
dp2 = list(range(N + 1))  # dp2[取引所 B から持ってきたドングリ数] = 巣に持ち帰れる最大ドングリ数
for i in range(N + 1):
    if i >= gb:
        dp2[i] = max(dp2[i], dp2[i - gb] + ga)
    if i >= sb:
        dp2[i] = max(dp2[i], dp2[i - sb] + sa)
    if i >= bb:
        dp2[i] = max(dp2[i], dp2[i - bb] + ba)
print(dp2[N])
### BUGGY CODE ###

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

from bisect import insort

for _ in range(m):
    x = A.pop()//2
    insort(A, x)

print(sum(A))


### FIXED CODE ###

n, m = map(int, input().split())
A = list(map(int, input().split()))
A = map(lambda x: x * (-1), A)
A = sorted(A)

from heapq import heappush, heappop

for _ in range(m):
    x = heappop(A)
    heappush(A, (-1*x)//2*(-1))

print(sum(A)*(-1))
### BUGGY CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(2*(10**5))

N, Q = map(int, input().split())
E = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
visit = [False]*N
ans = [0]*N
for i in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x


def dfs(v, road):
    if not visit[v]:
        visit[v] = True
        for nxt in E[v]:
            ans[nxt] += ans[v]
            dfs(nxt, road[:])


dfs(0, [])
print(*ans)


### FIXED CODE ###

from collections import defaultdict

N, Q = map(int, input().split())
E = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
ans = [0]*N
for i in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x

for i in range(N):
    for t in E[i]:
        ans[t] += ans[i]
print(*ans)
### BUGGY CODE ###

s=input()
Q=int(input())
for i in range(Q):
    q=input()
    if q[0]=='1':
        s=s[::-1]
    elif q[2]=='1':
        s=q[4]+s
    elif q[2]=='2':
        s=s+q[4]
print(s)

### FIXED CODE ###

from collections import deque
s=deque(list(input()))
Q=int(input())
count = 0
for i in range(Q):
    q=input()
    if q[0]=='1':
        count += 1
    elif (q[2]=='1' and count%2==0) or (q[2]=='2' and count%2==1):
        s.appendleft(q[4])
    elif (q[2]=='2' and count%2==0) or (q[2]=='1' and count%2==1):
        s.append(q[4])

if count%2==0:
    print(''.join(s))
else:
    print(''.join(reversed(s)))
### BUGGY CODE ###



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

def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)):
        g = gcd_core(g, arr[i])
    return g


def lcm_core(a,b):
    g = gcd_core(a,b)
    return (a*b)//g

def lcm(arr):
    if len(arr) == 1:
        return arr[0]
    else:
        newl = []
        ind = 0
        while True:
            if ind + 1 < len(arr):
                newl.append(lcm_core(arr[ind],arr[ind+1]))
                ind += 2
            else:
                newl.append(arr[ind])
                ind += 1
            if ind >= len(arr):
                break
        return lcm(newl)


n = int(input())

if n == 1:
    print(1)
else:
    arr = list(map(int,input().split()))
    l = lcm(arr)
    m = 10**9+7
    l,mcnt = l%m,l//m
    ans = 0
    for i in range(n):
        temp1 = l // arr[i] + (m // arr[i]) * mcnt
        temp2 = l % arr[i] + (m % arr[i]) * mcnt
        temp2 = temp2 // arr[i]
        ans += temp1 + temp2
        ans %= m
    ans %= m
    print(ans)


### FIXED CODE ###

import fractions
from functools import reduce

def gcd(*numbers):
  return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
  return reduce(fractions.gcd, numbers)

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

mod = 10 ** 9 + 7

l = lcm_list(A)

ans = 0

for i in range(N):
  ans += l // A[i]

ans = ans % mod

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

import sys
input = sys.stdin.readline
N, M, Q = [int(_) for _ in input().split()]

lr = [[0] * (N + 1) for _ in range(N + 1)]

for _ in range(M):
    l, r = [int(_) for _ in input().split()]
    lr[l][r] += 1

# for i in range(1, N + 1):
#     print(lr[i][1:])
for _ in range(Q):
    p, q = [int(_) for _ in input().split()]
    ans = 0
    for i in range(p, q + 1):
        for j in range(i, q + 1):
            ans += lr[i][j]
    print(ans)


### FIXED CODE ###

import sys

input = sys.stdin.readline
N, M, Q = [int(_) for _ in input().split()]

lr = [[0] * (N + 1) for _ in range(N + 1)]

for _ in range(M):
    l, r = [int(_) for _ in input().split()]
    lr[l][r] += 1
for i in range(1, N + 1):
    for j in range(1, N + 1):
        lr[i][j] += lr[i][j - 1]

# for i in range(1, N + 1):
#     print(lr[i][1:])
for _ in range(Q):
    p, q = [int(_) for _ in input().split()]
    ans = 0
    for i in range(p, q + 1):
        ans += lr[i][q] - lr[i][p - 1]
    print(ans)
### BUGGY CODE ###

s=input()
q=int(input())
dp=["" for i in range(q+1)]
dp[0]=s
flag=0
for i in range(q):
  ques=list(input().split())
  if ques[0]=="1":
    dp[i+1]=dp[i]
    flag+=1
  else:
    if ques[1]=="1":
      if flag%2==0:
        dp[i+1]=ques[2]+dp[i]
      else:
        dp[i+1]=dp[i]+ques[2]
    else:
      if flag%2==0:
        dp[i+1]=dp[i]+ques[2]
      else:
        dp[i+1]=ques[2]+dp[i]
if flag%2==1:
  ans=dp[q][::-1]
else:
  ans=dp[q]
print(ans)

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())
ans = deque(S)
revcnt = 0
for i in range(Q):
    data = list(input().split())
    if data[0] == '1':
        revcnt += 1
        continue

    if data[1] == '1':
        if revcnt % 2 == 0:
            ans.appendleft(data[2])
        else:
            ans.append(data[2])
    else:
        if revcnt % 2 == 0:
            ans.append(data[2])
        else:
            ans.appendleft(data[2])

if revcnt % 2 != 0:
    print(''.join(reversed(list(ans))))
else:
    print(''.join(list(ans)))