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

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

    from itertools import accumulate
    CA = list(accumulate(A))

    mindiff = CA[-1]
    for c in range(1,N-2):
        # left side
        p = 0
        q = CA[-1]
        for i in range(0, c):
            pi = CA[i]
            qi = CA[c] - CA[i]
            if abs(pi- qi) < abs(p - q):
                p = pi; q = qi
            else:
                break

        # right side
        r = 0
        s = CA[-1]
        for i in range(c+1, N):
            ri = CA[i] - CA[c]
            si = CA[-1] - CA[i]
            if abs(ri- si) < abs(r - s):
                r = ri; s = si
            else:
                break
    
        mindiff = min(mindiff, max(p, q, r, s) - min(p, q, r, s))
    return mindiff
print(solve())

### FIXED CODE ###

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

from itertools import accumulate
CA = list(accumulate(A))

mindiff = CA[-1]
left = 0
right = 2
for c in range(1,N-1):
    # left side
    p = CA[left]
    q = CA[c] - CA[left]
    while True:
        pi = CA[left+1]
        qi = CA[c] - CA[left+1]
        if abs(pi- qi) >= abs(p - q):
            break
        p = pi; q = qi
        left += 1

    # right side
    r = CA[right] - CA[c]
    s = CA[-1] - CA[right]
    while True:
        ri = CA[right+1] - CA[c]
        si = CA[-1] - CA[right+1]
        if abs(ri- si) >= abs(r - s):
            break
        r = ri; s = si
        right += 1

    mindiff = min(mindiff, max(p, q, r, s) - min(p, q, r, s))
print(mindiff)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
	N = INT()
	A = [LIST() for _ in range(N)]

	ans = 0
	sum_ = 0
	while 1:
		delete = [0]*(N+1)
		for i in range(1, N):
			if len(A[i-1]) == 0:
				continue
			if i == A[A[i-1][0]-1][0]:
				delete[i] = 1
				delete[A[i-1][0]] = 1
		if sum(delete) == 0:
			print(-1)
			sys.exit(0)

		for i in range(1, len(delete)):
			if delete[i] == 1:
				sum_ += A[i-1].pop(0)
		ans += 1
		if sum_ == N*(N-1)*(N+1)//2:
			break
		
	print(ans)

if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N = INT()
	A = [LIST() for _ in range(N)]

	graph_out = defaultdict(list)
	graph_in = defaultdict(list)
	match_id = [[0]*N for _ in range(N)]

	def toid(i, j):  # 選手から試合IDに変換
		if i > j: i, j = j, i
		return match_id[i][j]

	cnt = 0
	for i in range(N):
		for j in range(N):
			if i < j:
				match_id[i][j] = cnt
				cnt += 1

	V = N*(N-1)//2
	gout = [[] for _ in range(V)]
	gin = [[] for _ in range(V)]
	deg = [0]*(V)
	for i in range(N):
		for j in range(N-2):
			gout[toid(i, A[i][j]-1)].append(toid(i, A[i][j+1]-1))
			deg[toid(i, A[i][j+1]-1)] += 1
			gin[toid(i, A[i][j+1]-1)].append(toid(i, A[i][j]-1))
	# トポロジカルソート
	ans = [v for v in range(V) if deg[v]==0]
	deq = deque(ans)
	used = [0]*V
	while deq:
	    v = deq.popleft()
	    for t in gout[v]:
	        deg[t] -= 1
	        if deg[t]==0:
	            deq.append(t)
	            ans.append(t)
	if any(deg):
		print(-1)
		exit()

	cnt = [0]*V  # cntが入り次数に達したら発火
	day = [0]*V
	q = deque(ans)
	ans = 0

	while q:
		n = q.popleft()
		for node in gout[n]:
			cnt[node] += 1
			if cnt[node] == len(gin[node]):
				q.append(node)
				day[node] = day[n] + 1
				ans = day[node]
	print(ans+1) 

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

S = input()

c = 0
l = len(S)
for i in range(l):
  c += S.count('01')
  S = S.replace('01','')
  c += S.count('10')
  S = S.replace('10','') 

print(c*2)

### FIXED CODE ###

S = input()

c1 = S.count("0")
c2 = S.count("1")

if c1 >= c2:
  ans =c2*2
else:
  ans=c1*2
  
print(ans)
### BUGGY CODE ###

from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
l = 1
for i in a:
    l = i * l // (gcd(i, l))

cnt = 0
for i in a:
    cnt += l // i
    cnt %= mod
print(cnt)

### FIXED CODE ###

from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
l = 1
for i in a:
    l = i * l // (gcd(i, l))

cnt = 0
for i in a:
    cnt += l // i
print(cnt % mod)
### BUGGY CODE ###

n = int(input())
a = list(input().split())
b = []
for i in range(n):
    if i%2==0:
        b = b+[a[i]]
    else:
        b = [a[i]] + b
if n%2==1:
    print(*b[::-1])
else:
    print(*b)

### FIXED CODE ###

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

if n%2==1:
    print(" ".join(a[n-1::-2]+a[1:n+1:2]))
else:
    print(" ".join(a[n::-2]+a[:n+1:2]))
### BUGGY CODE ###

def uf_find(x):
  if x == p[x]:
    return x
  else:
    p[x] = uf_find(p[x])
    return p[x]

def uf_unite(x,y):
  x = uf_find(x)
  y = uf_find(y)
  if x != y:
    if r[y]>r[x]:
      x,y = y,x
    if r[x]==r[y]:
      r[x]+= 1
    p[y] = x
    #print(r)


N, M = map(int, input().split())
p = list(range(N))
r = [0]*N

for i in range(M):
  A, B = [int(j)-1 for j in input().split()]
  uf_unite(A,B)
  #print(p)
  
#for i in range(N):
  #p[i] = uf_find(i)

q = [0]*N
for i in range(N):
  q[i] = p.count(i)
  
print(max(q))


### FIXED CODE ###

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

par = list(range(N))
rank = [1]*N
size = [1]*N

def find(x):
  if par[x] == x:
    return x
  else:
    return find(par[x])
  
def unite(x,y):
  x = find(x)
  y = find(y)
  
  if x == y:
    return
  if rank[x]<rank[y]:
    par[x]=y
    size[y]+= size[x]
  else:
    par[y] = x
    size[x] += size[y]
    if rank[x]==rank[y]:
      rank[x]+=1
    
for i in range(M):
  a,b = [int(i)-1 for i in input().split()]
  unite(a,b)
  
print(max(size))
### BUGGY CODE ###

n,a,b=map(int,input().split())
s=input()
ans=list('No'for _ in range(n))
c=a+b
for i in range(n):
    if ans[:i].count('Yes')<c:
        if s[i]=='a':
            ans[i]='Yes'
        if s[i]=='b' and s[:i].count('b')<b:
            ans[i]='Yes'
            
            

print(*ans,sep='\n')

### FIXED CODE ###

n,a,b=map(int,input().split())
s=input()
ans=list('No'for _ in range(n))
c=a+b
countY=0
countb=0
for i in range(n):
    if countY<c:
        if s[i]=='a':
            ans[i]='Yes'
            countY+=1
        if s[i]=='b' and countb<b:
            ans[i]='Yes'
            countY+=1
            countb+=1
            
print(*ans,sep='\n')
### BUGGY CODE ###

import math
N, M = [int(i) for i in input().split()]

ans = 1
for i in range(N, M):
    if M % i == 0:
        ans = M / i
        break

print(int(ans))

### FIXED CODE ###

import math
N, M = [int(i) for i in input().split()]

ans = 1
sosu = True if M % 2 == 1 else False

if M % 2 == 1:
    sqrt = int(math.ceil(math.sqrt(M)))
    for i in range(3, sqrt, 2):
        if M % i == 0:
            sosu = False
            break

if sosu == False:
    for i in range(N, M):
        if M % i == 0:
            ans = M / i
            break


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

# -*- coding: utf-8 -*-

import math
from functools import reduce

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

k = int(input())

sum = 0
for p in range(k):
    for q in range(k):
        for r in range(k):
            sum += gcd(p + 1, q + 1, r + 1)
print(sum)


### FIXED CODE ###

import math
# from functools import reduce

# def gcd(*numbers):
#     return reduce(math.gcd, numbers)

k = int(input())

sum = 0
for p in range(k):
    for q in range(k):
        n = math.gcd(p + 1, q + 1)
        for r in range(k):
            sum += math.gcd(n, r + 1)
print(sum)
### BUGGY CODE ###

from fractions import gcd
from sys import stdin

def main():
    mod = 10**9 + 7
    input = stdin.readline

    N = int(input())
    A = input().split()
    num = 1
    for n in set(A):
        num = (num*int(n))//gcd(num,int(n))

    t = 0
    for n in A:
        t = (t + num//int(n)) % mod
    print(t)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from fractions import gcd

def main():
    mod = 10**9 + 7

    N = int(input())
    A = input().split()
    AP = set(A)
    num = 1
    for n in AP:
        num = (num*int(n))//gcd(num,int(n))

    t = 0
    for n in A:
        t = (t + num//int(n))
    print(t%mod)


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

K=int(input())
i='7'
if K%2==1:
    while True:
        if int(i)%K==0:
            print(len(str(i)))
            break
        else:
            i+='7'
else:
    print('-1')

### FIXED CODE ###


K=int(input())
i=0
if K%2==0 or K%5==0:
    print('-1')

else:
    for d in range(K):
        i=(10*i+7)%K
        if i==0:
            print(d+1)
            break
### BUGGY CODE ###

N = int(input())
P = [int(input()) for _ in range(N)]

check = [0] * N
wantnext = {}
for i in range(1, N+1):
    wantnext[i] = set([i])

for i in P:
    for j in wantnext[i]:
        check[j-1] += 1
        if i < N:
            wantnext[i+1].add(j)

print(N-max(check))


### FIXED CODE ###

N = int(input())
P = [int(input()) for _ in range(N)]

check = [0] * N

for i in P:
    if check[i-1] == 0:
        if (i-2 >= 0 and check[i-2] == 0) or i == 1:
            check[i-1] = 1
        else:
            check[i-1] = 2
count = 0
ans = 0
for i in range(N):
    if check[i] == 2:
        count += 1
    else:
        ans = max(ans, count)
        count = 1
ans = max(ans, count)

print(N-ans)
### BUGGY CODE ###

#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
from heapq import heappush, heappop, heappushpop, heapify, heapreplace
from collections import defaultdict
# ---- ここまで -----------------------
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)

### FIXED CODE ###

import bisect
s = input().rstrip()
t = input().rstrip()

a_ord = ord("a")
ch_place = [[] for _ in range(26)]
for i, ch in enumerate(s):
    ch_place[ord(ch) - a_ord].append(i)

# print(ch_place)

count = 0
idx = -1 
for ch in t:
    ch_num = ord(ch) - a_ord
    if len(ch_place[ch_num]) == 0:
        print(-1)
        exit()
    place = bisect.bisect_right(ch_place[ch_num], idx)
    # print(ch_place[ch_num], idx, place)
    if place == len(ch_place[ch_num]):
        idx = ch_place[ch_num][0]
        count += 1
    else:
        idx = ch_place[ch_num][place]

# print(count, idx)
print(count * len(s) + idx + 1)
### BUGGY CODE ###

from collections import deque
n=int(input())
a=[list(map(lambda x:int(x)-1,input().split())) for _ in range(n)]
g = [[[] for _ in range(n)] for _ in range(n)]
h=[[0]*n for _ in range(n)]
for i in range(n):
	for j in range(1,n-1):
		maf = max(i,a[i][j-1])
		mif = min(i,a[i][j-1])
		mat = max(i,a[i][j])
		mit = min(i,a[i][j])
		g[mif][maf].append([mit,mat])
		h[mit][mat] += 1

st = deque([])
for i in range(n):
	for j in range(i+1,n):
		if h[i][j]==0:
			st.append([i,j])
ans=[]
while(st):
	f = st.popleft()
	ans.append(f)
	for mi,ma in g[f[0]][f[1]]:
		h[mi][ma]-=1
		if h[mi][ma] == 0:
			st.append([mi,ma])

if len(ans)!=n*(n-1)//2:
	print(-1)
	exit()

mac=0
for edge in ans:
	x=edge[0]
	y=edge[1]
	q=deque([[x,y,1]])
	while(q):
		tmp=q.popleft()
		f1=tmp[0]
		f2=tmp[1]
		c=tmp[2]
		mac=max(c,mac)
		for nn in g[f1][f2]:
			q.append([nn[0],nn[1],c+1])
print(mac)

### FIXED CODE ###

n=int(input())
a=[[int(x)-1 for x in input().split()] for _ in range(n)]

cnt=0
id=[[0]*n for _ in range(n)]
for i in range(n):
	for j in range(i+1,n):
		id[i][j] = cnt
		cnt+=1
def toid(x,y):
	return id[x][y] if x<y else id[y][x]

for i in range(n):
	for j in range(n-1):
		a[i][j] = toid(i,a[i][j])

nedge = n*(n-1)//2
g=[[]for _ in range(nedge)]
to = [0]*nedge
for i in range(n):
	for j in range(1,n-1):
		g[a[i][j-1]].append(a[i][j])
		to[a[i][j]]+=1

from collections import deque

dp=[1]*nedge
q=deque([])
cnt = 0
for i in range(nedge):
	if to[i]==0:
		q.append(i)
		cnt+=1

ans = 1
while(q):
	e = q.popleft()
	for ne in g[e]:
		dp[ne] = max(dp[ne],dp[e]+1)
		to[ne]-=1
		if to[ne]==0:
			q.append(ne)
			cnt+=1
	ans = max(ans,dp[e])

if cnt != nedge:
	print(-1)
else:
	print(ans)
### BUGGY CODE ###


#入力受け取り
n = int(input())
tourList = []
for i in range(n):
    array = list(map(int, input().strip().split()))
    tourList.append(array)

#DebugPrint

currentTime = 0
currentX = 0
currentY = 0

loop=0

for i in range(len(tourList)) :
    Time = tourList[i][0]
    X = tourList[i][1]
    Y = tourList[i][2]

    Time = Time - currentTime
    X = X - currentX
    Y = Y - currentY
    flag=False
    Z=0 #往復調整用    
    while (X+Y+Z) <= Time :
        if X+Y+Z == Time:
            flag=True
            break
        else:
            Z+=2
    
    #継続判定
    if flag == False:
        print("No")
        exit()
    
    currentTime = Time
    currentX = X
    currentY = Y

print("Yes")

    #最初の点がまず実現可能か


### FIXED CODE ###


#入力受け取り
n = int(input())
tourList = []
for i in range(n):
    array = list(map(int, input().strip().split()))
    tourList.append(array)

#DebugPrint
currentTime = 0
currentX = 0
currentY = 0

for i in range(len(tourList)) :
    Time = tourList[i][0]
    X = tourList[i][1]
    Y = tourList[i][2]

    Time = Time - currentTime
    X = X - currentX
    Y = Y - currentY
    flag=False

    NUM = abs(X)+abs(Y)
    if( (Time-NUM)%2==0 and NUM <= Time):
        flag=True

    # while (X+Y+Z) <= Time :
    #     if X+Y+Z == Time:
    #         flag=True
    #         break
    #     else:
    #         Z+=2
    
    #継続判定
    if flag == False:
        print("No")
        exit()
    
    currentTime = Time
    currentX = X
    currentY = Y

print("Yes")

    #最初の点がまず実現可能か
### BUGGY CODE ###

import sys
input = sys.stdin.readline

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
 
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
 
ab = sorted(x+y for x in a for y in b)[:-k-1:-1]
c = c[:k]
abc = []
for i in ab:
    for j in c:
        abc.append(i+j)
abc.sort(reverse=True)
 
print(*abc[:k], sep="\n")

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ab = sorted(x+y for x in a for y in b)[:-k-1:-1]
abc = sorted(x+y for x in ab[:k] for y in c)[:-k-1:-1]
print(*abc, sep='\n')
### BUGGY CODE ###

def main():
    mod = 998244353
    s, k = input().split()
    k = int(k)
    n = len(s)

    one = s.count("1")

    cnt = 0
    zero_list = []
    for i in range(n):
        if s[i] == "0":
            zero_list.append(cnt)
            cnt = 0
        else:
            cnt += 1

    z = 0

    dp = [[0]*(one+1) for _ in [0]*(one+1)]
    dp[0][0] = 1

    for i in range(len(zero_list)):
        dp2 = [[0]*(min(one, k)+1) for _ in [0]*(one+1)]
        base = zero_list[i]
        # j:何個今までに入れたか
        for j in range(one+1):
            # l:何個入れるか
            for l in range(one+1-j):
                if j+l > one:
                    continue
                if j+l < z+base:
                    continue
                # p:これまでのペナルティ
                for p in range(min(one, k)+1):
                    q = p+max(l-base, 0)
                    if q <= min(one, k) and j+l <= one:
                        dp2[j+l][q] = (dp2[j+l][q]+dp[j][p]) % mod
        z += base
        dp = dp2
    print(sum([sum(i) for i in dp]) % mod)


main()


### FIXED CODE ###

def main():
    mod = 998244353
    s, k = input().split()
    k = int(k)
    n = len(s)

    one = s.count("1")

    cnt = 0
    zero_list = []
    for i in range(n):
        if s[i] == "0":
            zero_list.append(cnt)
            cnt = 0
        else:
            cnt += 1

    z = 0
    mm = min(one, k)

    dp = [[0]*(one+1) for _ in [0]*(one+1)]
    dp[0][0] = 1

    for i in range(len(zero_list)):
        dp2 = [[0]*(mm+1) for _ in [0]*(one+1)]
        base = zero_list[i]
        # j:何個今までに入れたか
        for j in range(one+1):
            # l:何個入れるか
            for l in range(one+1-j):
                if l < z+base-j:
                    continue
                ml = max(l-base, 0)
                # p:これまでのペナルティ
                for p in range(min(one, k)+1):
                    q = p+ml
                    if q <= mm:
                        dp2[j+l][q] = (dp2[j+l][q]+dp[j][p]) % mod
                    else:
                        break
        z += base
        dp = dp2
    print(sum([sum(i) for i in dp]) % mod)


main()
### BUGGY CODE ###

def main():
    import numpy as np
    n = int(input())
    alphabet = "abcdefghijklmnopqrstuvwxyz"
    d_alpha = {j: i for i, j in enumerate(alphabet)}
    s = input()
    s = np.array([d_alpha[i] for i in s], dtype=np.int8)
    m = 0
    for i in range(1, n):
        cnt_m = 0
        cnt = 0
        t = (s[:n-i] == s[i:])
        for j in t:
            if j:
                cnt = min(cnt+1, i)
            else:
                cnt_m = max(cnt, cnt_m)
                cnt = 0
        m = max(cnt, cnt_m, m)
    print(m)


main()

### FIXED CODE ###

def main():
    n=int(input())
    s=input()
    m=0
    for i in range(1,n):
        cnt_m=0
        cnt=0
        for j in range(i,n):
            if s[j-i]==s[j]:
                cnt=min(cnt+1,i)
            else:
                cnt_m=max(cnt,cnt_m)
                cnt=0
        m=max(cnt,cnt_m,m)
    print(m)

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

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, p: "List[float]"):
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 1.0

    for i in range(N):
        for j in range(N):
            dp[i+1][j+1] += p[i] * dp[i][j]
            dp[i+1][j] += (1.0 - p[i]) * dp[i][j]
    return sum(dp[-1][(N // 2 + 1):])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    p = [ float(next(tokens)) for _ in range(N) ]  # type: "List[float]"
    result = solve(N, p)
    print(result)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, p: "List[float]"):
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 1.0

    for i in range(N):
        for j in range(N):
            dp[i+1][j+1] += p[i] * dp[i][j]
            dp[i+1][j] += (1.0 - p[i]) * dp[i][j]
    return sum(dp[-1][(N // 2 + 1):])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    p = [ float(next(tokens)) for _ in range(N) ]  # type: "List[float]"
    result = solve(N, p)
    print(result)

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

import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

reverse = 0
pre = ''
after = ''
S = input()
Q = int(input())
for i in range(Q):
    q = input()
    if q[0] == '1':
        reverse = 1 - reverse
    else:
        T, F, C = q.split()
        if (F == '1') ^ (reverse == 1):
            pre += C
        else:
            after += C
pre = pre[::-1]
S = pre + S + after
if reverse:
    S = S[::-1]
print(S)


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

reverse = 0
pre = []
after = []
S = input()
Q = int(input())
for i in range(Q):
    q = input()
    if q[0] == '1':
        reverse = 1 - reverse
    else:
        T, F, C = q.split()
        if (F == '1') ^ (reverse == 1):
            pre.append(C)
        else:
            after.append(C)
if reverse:
    after.reverse()
    ans = ''.join(after) + S[::-1] + ''.join(pre)
else:
    pre.reverse()
    ans = ''.join(pre) + S + ''.join(after)
print(ans)
### BUGGY CODE ###

import math
def solve():
    a, b, n = map(int, input().split())

    ans = 0
    for x in range(1, n+1):
        ans = max(ans, math.floor(a*x/b) - a*math.floor(x/b))


    return ans


print(solve())


### FIXED CODE ###

import math
def solve():
    a, b, n = map(int, input().split())

    if n < b:
        return math.floor(a*n/b) - a*math.floor(n/b)
    elif n >= b:
        return math.floor(a*(b-1)/b) - a*math.floor((b-1)/b)



print(solve())
### BUGGY CODE ###

n = int(input())
for i in range(1,n+1):
    c = 0
    total = n
    while 1:
        for x in range(1, i//2):
            for y in range(x, i//2):
                for z in range(y, i//2):
                    total = ((x+y)**2 + (z+y)**2 + (x+z)**2) / 2
                    if total == i:
                        if x == y == z:
                            c += 1
                            # print("b")
                        elif x == y or y == z:
                            c += 3
                        else:
                            c += 6
                        break
                    elif total>i:
                        # print("a")
                        break
                if total == i:
                    break
        if total>i:
            break
    print(c)

### FIXED CODE ###

n = int(input())
a = [0 for i in range(n)]
c = 0
total = n
for x in range(1, n//2):
    for y in range(x, n//2):
        for z in range(y, n//2):
            total = int(((x+y)**2 + (z+y)**2 + (x+z)**2) / 2)
            try:
                if x == y == z:
                    a[total-1] += 1
                elif x == y or y == z:
                    a[total-1] += 3
                else:
                    a[total-1] += 6
            except:
                break
for i in a:
    print(i)
### BUGGY CODE ###

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

for i in range(q):
  b,c = map(int,input().split())
  for j in range(n):
    if a[j] == b:
      a[j] = c
  print(sum(a))

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
ans = sum(A)
num = Counter(A)
for i in range(Q):
    b,c = map(int,input().split())

    ans += (c-b)*num[b]
    num[c] += num[b] 
    num[b] = 0
    
    print(ans)