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

n,m,k = map(int,input().split())
num = [1 for _ in range(n)]
pre = [i for i in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  num[a] += 1
  num[b] += 1
  A = [a]
  B = [b]
  la = 1
  lb = 1
  while a != pre[a]:
    a = pre[a]
    A.append(a)
    la += 1
  while b != pre[b]:
    b = pre[b]
    B.append(b)
    lb += 1
  #print(a,b)
  if a != b:
    if la < lb:
      pre[b] = a
      for aa in A:
        pre[aa] = a
      for bb in B:
        pre[bb] = a
    else:
      pre[a] = b
      for aa in B:
        pre[aa] = b
      for bb in B:
        pre[bb] = b
root = [10**6 for _ in range(n)]
cnt = [0 for _ in range(n)]
for i in range(n):
  if root[i] < 10**6:
    cnt[root[i]] += 1
    continue
  I = int(i)
  J = [I]
  while I != pre[I]:
    I = pre[I]
    J.append(I)
  for x in J:
    root[x] = I
  cnt[I] += 1
#print(pre)
#print(root)
#print(cnt)
ans = []
for i in range(n):
  ans.append(cnt[root[i]]-num[i])
#print(ans)
for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  if root[a] == root[b]:
    ans[a] -= 1
    ans[b] -= 1
print(' '.join(map(str,ans)))

### FIXED CODE ###

n,m,k = map(int,input().split())
num = [1 for _ in range(n)]
pre = [i for i in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  num[a] += 1
  num[b] += 1
  A = [a]
  B = [b]
  la = 1
  lb = 1
  while a != pre[a]:
    a = pre[a]
    A.append(a)
    la += 1
  while b != pre[b]:
    b = pre[b]
    B.append(b)
    lb += 1
  #print(a,b)
  if a != b:
    if la > lb:
      pre[b] = a
      for aa in A:
        pre[aa] = a
      for bb in B:
        pre[bb] = a
    else:
      pre[a] = b
      for aa in B:
        pre[aa] = b
      for bb in B:
        pre[bb] = b
root = [10**6 for _ in range(n)]
cnt = [0 for _ in range(n)]
for i in range(n):
  if root[i] < 10**6:
    cnt[root[i]] += 1
    continue
  I = int(i)
  J = [I]
  while I != pre[I]:
    I = pre[I]
    J.append(I)
  for x in J:
    root[x] = I
  cnt[I] += 1
#print(pre)
#print(root)
#print(cnt)
ans = []
for i in range(n):
  ans.append(cnt[root[i]]-num[i])
#print(ans)
for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  if root[a] == root[b]:
    ans[a] -= 1
    ans[b] -= 1
print(' '.join(map(str,ans)))
### BUGGY CODE ###

from copy import deepcopy

def penalty(day, last, c):
    val = 0
    for i in range(26):
        val += c[i] * (day - last[i])
    return val

def update(day, t, q, score, c, last):
    t[day] = q
    for i in range(day, len(score)):
        last[i] = deepcopy(last[i-1])
        score[i] = score[i-1] + s[i][t[i]]
        last[i][t[i]] = i
        score[i] -= penalty(i, last[i], c)

D = int(input())
c = list(map(int, input().split()))
s = [[0]*26 for _ in range(D+1)]
for i in range(1, D+1):
    s[i] = list(map(int, input().split()))
t = [-1]*(D+1)
for i in range(1, D+1):
    t[i] = int(input()) - 1
M = int(input())

last = [[0]*26 for _ in range(D+1)]
score = [0]*(D+1)

for i in range(1, D+1):
    last[i] = deepcopy(last[i-1])
    score[i] = score[i-1] + s[i][t[i]]
    last[i][t[i]] = i
    score[i] -= penalty(i, last[i], c)

ans = [None]*M
for i in range(M):
    d, q = map(int, input().split())
    update(d, t, q-1, score, c, last)
    ans[i] = score[-1]

for v in ans:
    print(v)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

def calcScore(t, s, c):
    scores = [0]*26
    lasts = [0]*26
    for i in range(1, len(t)):
        scores[t[i]] += s[i][t[i]]
        dif = i - lasts[t[i]]
        scores[t[i]] -= c[t[i]] * dif * (dif-1) // 2
        lasts[t[i]] = i
    for i in range(26):
        dif = len(t) - lasts[i]
        scores[i] -= c[i] * dif * (dif-1) // 2
    return scores

D = int(input())
c = list(map(int, input().split()))
s = [[0]*26 for _ in range(D+1)]
for i in range(1, D+1):
    s[i] = list(map(int, input().split()))
t = [-1]*(D+1)
for i in range(1, D+1):
    t[i] = int(input()) - 1
M = int(input())

scores = calcScore(t, s, c)

ans = [None]*M
for i in range(M):
    d, q = map(int, input().split())
    t[d] = q-1
    ans[i] = sum(calcScore(t, s, c))

for v in ans:
    print(v)
### BUGGY CODE ###

import heapq

l = []

N, M = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
for i in range(N):
    for j in range(i, N):
        heapq.heappush(l, -(A[i] + A[j]))
        if i!=j:
            heapq.heappush(l, -(A[i] + A[j]))
ans = 0
for i in range(M):

    v= heapq.heappop(l)
    ans +=v
print(-ans)



### FIXED CODE ###

#!/usr/bin/env python3
import sys
from itertools import accumulate
from bisect import bisect_left

N, M = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]

A2 = sorted(A, reverse=True)
A = sorted(A)


# 必要となる左右合計の下限値 X を求める

def f1(m):
    cnt = 0
    for a1 in A2:
        tmp = bisect_left(A, m - a1)
        if tmp == N: break
        cnt += N - tmp

    return cnt >= M


l = 0
r = A2[0] * 2 + 10

while r - l > 1:
    m = (l + r) // 2
    if f1(m):
        l = m
    else:
        r = m

X = l
# print('X', X)

acc = list(accumulate(A2))  # 累積和

total_cnt = 0
ans = 0
for a in A2:
    # a を左手としたときの右手の最小値
    min_right = X - a
    if min_right > A[-1]:
        continue

    # 右手の値から出す手数を算出
    idx = bisect_left(A, min_right)
    cnt = N - idx

    # それらの全合計を加算
    ans += a * cnt + acc[cnt - 1]
    total_cnt += cnt

    # if total_cnt >= M:
    #     break
# total_cnt が大きすぎる場合は, その分だけ Xを減算. X は必要な両手合計の最小値なので, 減算すべきは必ず X*出しすぎた分 となる
if total_cnt > M:
    ans -= X * (total_cnt - M)
print(ans)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

rmax = N // R + 1
gmax = N // G + 1

ans = 0
for i in range(rmax):
    for j in range(gmax):
        if (N - (i * R + j * G)) % B == 0 and (N - (i * R + j * G)) >= 0:
            ans += 1  # (N-(i*R+j*G))//B
print(ans)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for i in range(int(N / R) + 1):
    for j in range(int((N - i * R) / G) + 1):
        if ((N - (i * R + j * G)) % B == 0):
            ans += 1
print(ans)
### BUGGY CODE ###

from collections import Counter

class Bit:
    def __init__(self, n,ls):
        self.size=n
        self.tree=[Counter() for _ in range(n+1)]
        self.ls=['']*(n+1)

    def sum(self, i, j):
        i-=1
        res=Counter()
        while j>0:
            res += self.tree[j]
            j -= j&-j
        while i>0:
            res -= self.tree[i]
            i -= i&-i
        return len(res)
    
    def add(self, i, x):
        self.ls[i] = x
        while i <= self.size:
            self.tree[i][x]+=1
            i += i & -i

    def change(self, i, x):
        original = self.ls[i]
        self.ls[i]=x
        while i <= self.size:
            self.tree[i][original] -=1
            self.tree[i][x] +=1
            i += i & -i
        

n = int(input())
s = list(input())
bit=Bit(n,s)

for i in range(n):
    bit.add(i+1, s[i])

q = int(input())
for _ in range(q):
    query, a, b = input().split()
    if query=='1':
        bit.change(int(a),b)
    else:
        ans=bit.sum(int(a), int(b))
        print(ans)


### FIXED CODE ###

from collections import Counter
def snum(x):
    return ord(x)-ord('a')

class Bit:
    def __init__(self, n,ls):
        self.size=n
        self.tree=[[0]*26 for _ in range(n+1)]
        self.ls=['']*(n+1)

    def sum(self, i, j):
        i-=1
        res=[0]*26
        for k in range(26):
            i2=i
            j2=j
            while j2>0:
                res[k] += self.tree[j2][k]
                j2 -= j2&-j2
            while i2>0:
                res[k] -= self.tree[i2][k]
                i2 -= i2&-i2
        return 26-res.count(0)
    
    def add(self, i, x):
        self.ls[i] = x
        while i <= self.size:
            self.tree[i][snum(x)]+=1
            i += i & -i

    def change(self, i, x):
        original = self.ls[i]
        self.ls[i]=x
        while i <= self.size:
            self.tree[i][snum(original)] -= 1
            self.tree[i][snum(x)] += 1
            i += i & -i
        

n = int(input())
s = list(input())
bit=Bit(n,s)

for i in range(n):
    bit.add(i+1, s[i])

q = int(input())
for _ in range(q):
    query, a, b = input().split()
    if query=='1':
        bit.change(int(a),b)
    else:
        print(bit.sum(int(a), int(b)))
### BUGGY CODE ###

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

def cost(i,j):
    return abs(h[i] - h[j])

dp=[10**9]*n
dp[0]=0

for i in range(1,n):
#    mn=10*9
    for j in range(i-k,i):
        if j>=0:
            cst = dp[j]+cost(j,i)
            if dp[i] > cst:
                dp[i]=cst
#    dp[i]=mn

print(dp[n-1])

### FIXED CODE ###

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

def cost(i,j):
    return abs(h[i] - h[j])

dp=[10**9]*n
dp[0]=0

for i in range(1,n):
    for j in range(i-k,i):
        if j>=0:
            cst = dp[j]+cost(j,i)
            if dp[i] > cst:
                dp[i]=cst

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

from collections import Counter
import copy 
n=int(input())
c=input()
cl=copy.deepcopy(c)
cl=list(cl)
d=Counter(c)
ans=0


if d["R"]==0 or d["W"]==0:
  print(0)
  exit()
swap=0
if d["R"]>=n//2:
  r=n//2
else:
  r=d["R"]
  
for i in range(r):
  indexes = [j for j, x in enumerate(cl) if x == "R"]
  #print(cl)
  if cl[i]=="W":
    cl[indexes[-1]]="W"
    cl[i]="R"
    swap+=1

#print(cl)
#print(cl[cl.index("W"):])
#print(swap)
d=Counter(cl[cl.index("W"):])
ans+=swap+d["R"]
print(ans)


### FIXED CODE ###

from collections import Counter
n=int(input())
c=input()
d=Counter(c)
w,r=Counter(c)["W"], Counter(c)["R"]
ans=0
for i in range(r):
  if c[i]=="W":
    ans+=1

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

n = int(input())
s = input()
result = []
for i in range(n):
  if i == 0:
    w = s[1:]
    ans = w.count("E")
    result.append(ans)
  if i == n-1:
    e = s[:n-1]
    ans = e.count("W")
    result.append(ans)
  else:
    e = s[:i-1]
    ans_1 = e.count("W")
    w = s[i+1:]
    ans_2 = w.count("E")
    result.append(ans_1 + ans_2)
    
print(min(result))
    

### FIXED CODE ###

n = int(input())
s = input()
result = []
w_list = []
e_list = []
w_1 = 0
e_1 = 0
for i in range(n):
  if s[i] == "W":
    w_1 += 1
    w_list.append(w_1)
    e_list.append(e_1)
  if s[i] == "E":
    e_1 += 1
    w_list.append(w_1)
    e_list.append(e_1)
  
for i in range(n):
  if i == 0:
    ans = e_list[-1] - e_list[0]
    result.append(ans)
  if i == n-1:
    ans = w_list[n-2]
    result.append(ans)
  else:
    ans_e = w_list[i-1]
    ans_w = e_list[-1] - e_list[i]
    result.append(ans_e + ans_w)
    
print(min(result))
### BUGGY CODE ###

from functools import lru_cache

def main(S):
    con = 10**9 + 7

    @lru_cache(maxsize=1024, typed=True)
    def get_c(iii):
        return [(j * iii) % 13 for j in l10]

    l10 = list(range(10))
    l13 = list(range(13))
    m13 = {i: {j: (i + j) % 13 for j in l13} for i in l13}
    c = []
    iii = 1
    for i in range(len(S)):
        s = S[len(S) - i - 1]
        if s != "?":
            c.append([(int(s) * iii) % 13])
        else:
            c.append(get_c(iii))
        iii = (iii * 10) % 13

    _tdp = {i: 0 for i in l13}
    it = iter(c)
    pdp = {i: 1 for i in next(it)}
    d = 1
    for v in it:
        tdp = _tdp.copy()
        for r in v:
            for _r, _v in pdp.items():
                tdp[m13[_r][r]] += _v
        if d == 0:
            for i in l13:
                tdp[i] = tdp[i] % con
        d = (d + 1) % 50
        pdp = tdp

    ans = pdp.get(5, 0)
    print(ans % con)

if __name__ == "__main__":
    S = input()
    main(S)

### FIXED CODE ###

S = input()
con = 10**9 + 7

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

def get_mod(S):
    c = {}
    iii = 1
    for i in range(len(S)):
        if S[len(S) - i - 1] != "?":
            iii *= 10
            iii %= 13
            continue
        c[i] = {(j * iii) % 13: 1 for j in range(0, 10)}
        iii *= 10
        iii %= 13
    return c
c = get_mod(S)

def get_tdp(pdp):
    tdp = {i: 0 for i in range(13)}
    for r in v.keys():
        for _r, _v in pdp.items():
            tdp[(_r + r) % 13] += _v
    for i in range(13):
        tdp[i] %= con
    return tdp

pdp = {i: 0 for i in range(13)}
pdp[SS] += 1
for k, v in c.items():
    pdp = get_tdp(pdp)

ans = pdp[5]
print(ans)
### BUGGY CODE ###

# 2019-11-11 16:07:35(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

digits = ['3', '5', '7']

def main():
    # 357 以上
    # 3, 5, 7 のいずれかを使わない数字の個数をnから引けばいい
    n = int(sys.stdin.readline().rstrip())

    if n < 357:
        print(0)
        sys.exit()

    count = 0
    for m in range(357, n+1):
        m = str(m)
        c3, c5, c7 = 0, 0, 0
        for d in m:
            if d == '3':
                c3 += 1
            elif d == '5':
                c5 += 1
            elif d == '7':
                c7 += 1
            else:
                break
        else:
            if c3 >= 1 and c5 >= 1 and c7 >= 1:
                count += 1

    print(count)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# 2019-11-11 16:07:35(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

shichigosan = '357'

def main():

    n = int(sys.stdin.readline().rstrip())
    
    count = 0
    for i in range(3, len(str(n)) + 1):
        sub_shichigosan = list(''.join(s) for s in itertools.product(shichigosan, repeat=i))
        for sub in sub_shichigosan:
            for d in shichigosan:
                if d in sub:
                    continue
                else:
                    break
            else:
                if 357 <= int(sub) <= n:
                    count += 1
    
    print(count)

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

n,k=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]

a.sort()

times=[0]*(n+1)
for i in a:
    times[i]+=1
times.sort()

while True:
    if times[0]==0:
        del times[0]
    else:
        break
ans=0
if len(times)>k:
    for i in range(len(times)-k):
        ans+=times[i]
print(ans)

### FIXED CODE ###

n,k=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]

a.sort()

times=[0]*(n+1)
for i in a:
    times[i]+=1
times.sort()


for i in range(n+1):
    if times[i]!=0:
        j=i
        break

ans=0
if len(times)>k-j:
    for i in range(j,len(times)-k):
        ans+=times[i]
print(ans)
### BUGGY CODE ###

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

# Alistの値段の高いモノから割引券を使った方がよい
while M > 0:
    max_index = Alist.index(max(Alist))
    Alist[max_index] = Alist[max_index]//2
    M = M - 1
print(sum(Alist))

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
Alist = list(map(lambda x: int(x) * (-1), input().split()))

heapq.heapify(Alist)
for _ in range(M):
    a = heapq.heappop(Alist) * (-1)
    a = a // 2
    heapq.heappush(Alist, a * (-1))

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

n=int(input())
s=1
a=map(int,input().split())
for i in a:
    s*=i
if s>10**18:
    s=-1
print(s)

### FIXED CODE ###

n=int(input())
s=1
a=list(map(int,input().split()))
if 0 in a:
    print(0)
else:
    for i in a:
        s*=i
        if s>10**18:
            s=-1
            break
    print(s)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  dist=[-1]*N
  dist[K]=0
  que=[K]
  while que:
    label=que.pop(0)
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist

N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1]+=[[b-1,c]]
  path[b-1]+=[[a-1,c]]
Q,K=map(int,input().split())
distance=BFS(K-1,path,N)
for i in range(Q):
  x,y=map(int,input().split())
  print(distance[x-1]+distance[y-1])


### FIXED CODE ###

from sys import stdin
input = stdin.readline
from collections import deque
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  dist=[-1]*N
  dist[K]=0
  que=deque()
  que.append(K)
  while que:
    label=que.popleft()
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist
 
N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1]+=[[b-1,c]]
  path[b-1]+=[[a-1,c]]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])
### BUGGY CODE ###

#出典
#http://d.hatena.ne.jp/mzp/20100623/lcs
#ここから完全にコピペしました
import sys
sys.setrecursionlimit(10**7)
def maxBy(f, x, y):
    if f(x) > f(y):
        return x
    else:
        return y

table = { ("","") : "" }

def lcs(xs,ys):
    if (xs,ys) in table:
        return table[(xs,ys)]

    ret = ""
    if xs == "" or ys == "":
        ret = ""
    elif xs[-1] == ys[-1]:
        ret = lcs(xs[:-1],ys[:-1]) + xs[-1]
    else:
        ret = maxBy(len,lcs(xs[:-1],ys),lcs(xs,ys[:-1]))
    table[(xs,ys)] = ret
    return ret
S=input()
T=input()
print(lcs(S,T))


### FIXED CODE ###

S=input()
T=input()
a=[ord(i) for i in S]
b=[ord(i) for i in T]
N=len(a);M=len(b)
X=[[0 for j in range(M+1)] for i in range(N+1)]
Y=[[0 for j in range(M+1)] for i in range(N+1)]
for i in range(N):
    for j in range(M):
        if a[i]==b[j]:
            X[i+1][j+1]=X[i][j]+1
            Y[i+1][j+1]=0
        elif X[i+1][j]<X[i][j+1]:
            X[i+1][j+1]=X[i][j+1]
            Y[i+1][j+1]=+1
        else:
            X[i+1][j+1]=X[i+1][j]
            Y[i+1][j+1]=-1
c=[]
i=N;j=M
while(i>0 and j>0):
    if Y[i][j]>0:
        i-=1
    elif Y[i][j]<0:
        j-=1
    else:
        c.append(a[i-1])
        i-=1
        j-=1
print("".join([chr(i) for i in c[::-1]]))
### BUGGY CODE ###

import numpy as np
N,K = map(int,input().split())
A = list(map(int,input().split()))
already_town =[1]
now_town=1
count = 0
check=False
for i in range(K):
    count =i+1
    if(A[now_town-1] in already_town):
        cicle_start_value=A[now_town-1]
        check=True
        break
    else:
        already_town.append(A[now_town-1])
        now_town = A[now_town-1]

if(check==False):
    print(now_town)
else:
    cicle_start=already_town.index(cicle_start_value)
    roop_town=already_town[cicle_start:]
    print(roop_town[(K-cicle_start)%(count-cicle_start)])


### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
already_town_check =[False]*(N+1)
already_town_check[1] = True
already_town = [1]
now_town=1
check=False
my_append = already_town.append
for i in range(K):
    check_town=A[now_town-1]
    if(already_town_check[check_town]):
        cicle_start_value=check_town
        check=True
        break
    already_town_check[check_town]=True
    my_append(check_town)
    now_town = check_town

if(check==False):
    print(now_town)
else:
    cicle_start=already_town.index(cicle_start_value)
    roop_town=already_town[cicle_start:]
    print(roop_town[(K-cicle_start)%((i+1)-cicle_start)])
### BUGGY CODE ###

N = int(input())
S = []
for i in range(N):
    s = input()
    S.append("".join(sorted(s)))

k = 0
while len(S) > 0:
    ss = S[0]
    n = S.count(ss)
    k += n*(n-1)//2
    while ss in S:
        S.remove(ss)
print(k)


### FIXED CODE ###

N = int(input())
k = 0
h = {}
for i in range(N):
    s = input()
    ss = "".join(sorted(s))
    if ss in h:
        k += h[ss]
    else:
        h[ss] = 0
    h[ss] += 1

print(k)
### BUGGY CODE ###

N=int(input())
import copy
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    return d

  
cost=[list(map(int,input().split())) for i in range(N)]
D=copy.deepcopy(cost)
E=warshall_floyd(cost)
      
if D!=E: 
  print(-1)
  exit()
D=cost
for i in range(N):
  for j in range(N):
    for k in range(N):
      a,b,c=cost[i][j],cost[j][k],cost[i][k]
      if a+b==c and a!=0 and b!=0 and c!=0:
        D[i][k]=0       
ans=0
for i in range(N):
  ans+=sum(D[i]) 
print(ans//2)


### FIXED CODE ###

N=int(input())
import copy
def warshall_floyd(N):
  d=[list(map(int,input().split())) for i in range(N)]
  D=copy.deepcopy(d)
  for k in range(N):
    for i in range(N):
      for j in range(N):
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  if d==D:
    return d
  else:
    return -1
  
E=warshall_floyd(N)
if E==-1:
  print(-1)
  exit()
  
for k in range(N):
  for i in range(N):
    for j in range(N):
      if E[i][j]!=0 and E[i][k]!=0 and E[k][j]!=0:
        if E[i][j]==E[i][k]+E[k][j]:
          E[i][j]=0       
ans=0
for i in range(N):
  ans+=sum(E[i]) 
print(ans//2)
### BUGGY CODE ###

S = list(input())
Q = int(input())
a = 0
for i in range(Q):
  q = list(input().split())
  q[0] = int(q[0])
  if q[0] == 1:
    if a == 0:
      a = 1
    else:
      a = 0
  else:
    q[1] = int(q[1])
    if (q[1] == 1 and a == 0) or (q[1] == 2 and a == 1):
      S = [q[2]] + S
    else:
      S = S + [q[2]]
if a == 1:
  S = S[::-1]
S = ''.join(S)
print(S)

### FIXED CODE ###

S = list(input())
Q = int(input())
a = 0
A = []
B = []
for i in range(Q):
  q = list(input().split())
  q[0] = int(q[0])
  if q[0] == 1:
    if a == 0:
      a = 1
    else:
      a = 0
  else:
    q[1] = int(q[1])
    if (q[1] == 1 and a == 0) or (q[1] == 2 and a == 1):
      B.append(q[2])
    else:
      A.append(q[2])
B = B[::-1]
ans = B + S + A
if a == 1:
  ans = ans[::-1]
ans = ''.join(ans)
print(ans)