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

import sys
input = sys.stdin.readline
class Unionfind:
    def __init__(self,n):
        self.per = [i for i in range(n)]
        self.rank = [0]*n

    def find(self, x):
        if self.per[x] == x:
            return x
        else:
            self.per[x] = self.find(self.per[x])
            return self.per[x]

    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.per[x] = y
        else:
            self.per[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

N = int(input())
cityx = []
cityy = []
for i in range(N):
    x,y = map(int,input().split())
    cityx.append([x,i])
    cityy.append([y,i])
cityx.sort()
cityy.sort()
side = []
for i in range(N-1):
    side.append([cityx[i+1][0]-cityx[i][0], cityx[i+1][1], cityx[i][1]])
    side.append([cityy[i+1][0]-cityy[i][0], cityy[i+1][1], cityy[i][1]])
side.sort()
ans = 0
uf = Unionfind(N)
for cost, x, y in side:
    if uf.same_check(x,y):
        continue
    ans += cost
    uf.union(x,y)

print(ans)



### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
cityx = [[0,i]for i in range(N)]
cityy = [[0,i]for i in range(N)]
for i in range(N):
    x,y = map(int,input().split())
    cityx[i][0] = x
    cityy[i][0] = y

cityx.sort()
cityy.sort()
side = []
for i in range(N-1):
    side.append([cityx[i+1][0]-cityx[i][0], cityx[i+1][1], cityx[i][1]])
    side.append([cityy[i+1][0]-cityy[i][0], cityy[i+1][1], cityy[i][1]])
side.sort()
ans = 0
per = [i for i in range(N)]
rank = [0]*N
def find(x):
    if per[x] == x:
        return x
    else:
        per[x] = find(per[x])
        return per[x]

ans = 0

for cost,x,y in side:
    x = find(x)
    y = find(y)
    if x != y:
        ans += cost
        if rank[x] < rank[y]:
            per[x] = y
        else:
            per[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

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

import sys

import numpy as np

readline = sys.stdin.buffer.readline


def main():
    N = int(readline())
    A = [0] + list(map(int, readline().split()))
    A = np.array(A)
    C = np.zeros(N + 1, dtype=np.int32)

    if A[-1] == 1:
        C[-1] == 1

    for j in range(N, 0, -1):
        cnt = np.sum(C[j::j])

        if cnt % 2 == 0:
            if A[j] == 0:
                C[j] = 0
            else:
                C[j] = 1
        else:
            if A[j] == 0:
                C[j] = 1
            else:
                C[j] = 0

    ans = np.sum(C)
    print(ans)
    if ans != 0:
        for i, c in enumerate(C):
            if c == 1:
                print(i)


main()


### FIXED CODE ###

import sys

import numpy as np

readline = sys.stdin.buffer.readline


def main():
    N = int(readline())
    A = [0] + list(map(int, readline().split()))
    A = np.array(A)
    C = np.zeros(N + 1, dtype=np.int32)

    if A[-1] == 1:
        C[-1] == 1

    for j in range(N, 0, -1):
        cnt = np.count_nonzero(C[j::j])
        C[j] = (cnt % 2) ^ A[j]

    ans = np.sum(C)
    print(ans)
    if ans != 0:
        B = np.arange(N + 1)
        li = B[C == 1]
        print(*li, sep='\n')


main()
### BUGGY CODE ###

ans = {}

roop = input()
for k in range(roop):
    str1 = raw_input()
    str2 = raw_input()
    for i in range(len(str1)):
        ans[i, -1] = 0
    for j in range(len(str2)):
        ans[-1, j] = 0
    ans[-1, -1] = 0
    for i in range (len(str1)):
        for j in range(len(str2)):
            if(str1[i] == str2[j]):
                ans[i, j] = ans[i - 1, j - 1] + 1
            else:
                ans[i, j] = max(ans[i - 1, j], ans[i, j - 1])
    print ans[len(str1) - 1, len(str2) - 1]

### FIXED CODE ###

def LCS():
    str1 = raw_input()
    str2 = raw_input()
    
    after = [0] * (len(str2) + 1)
    
    for i in xrange(1, len(str1) + 1):
        before = after + []
        for j in xrange(1, len(str2) + 1):
             if str1[i - 1] == str2[j - 1]:
                 after[j] = before[j - 1] + 1
             elif after[j - 1] > before[j]: #this is equal to 'max(after[j - 1], before[j])'
                 after[j] = after[j - 1]
    return after[j]

n = input()
for k in xrange(n):
    print LCS()
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
b = 1
for i in range(N):
  b *= a[i]
if b > 10 ** 18:
  print(-1)
else:
  print(b)

### FIXED CODE ###

import sys
n = input()
list_num =list(map(int,input().split()))
output = 1
if 0 in list_num:
    print(0)
    sys.exit()
for i in list_num:
    output = output * i
    if output > 10 ** 18:
        print(-1)
        sys.exit()
print(output)
### BUGGY CODE ###

from collections import defaultdict

vertice,edge,source = map(int,input().split(" "))
link = [[] for n in range(vertice)]
weight = defaultdict(dict)
for e in range(edge):
    i,j,w = map(int,input().split(" "))
    link[i].append(j)
    weight[i].update({j:w})
#print(weight,link)
for v in range(vertice):
    goal = v
    queue = [[source,0]]
    went = set()
    while queue != []:
        here,now_cost = queue.pop()
        if here == goal:
            print(now_cost)
            break

        can_go = link[here]
        not_went = set(can_go) - went
        #print(v,here,now_cost,not_went,queue)
        for nw in not_went:
            next_cost = now_cost + weight[here][nw]
            queue.append([nw,next_cost])
        went = went | {here}
        queue.sort(key=lambda x:x[1],reverse=True)
    else:
        print("INF")
            
                

### FIXED CODE ###

import sys
from heapq import heappush, heappop
readline = sys.stdin.readline
from collections import defaultdict
vertices, edges, start = map(int, readline().split())
connect = defaultdict(list)
cost = defaultdict(dict)
answer = ["INF" for n in range(vertices)]
for _ in range(edges):
    s, t, w = map(int, readline().split())
    connect[s].append(t)
    cost[s].update({t:w})
 
 
now = start
weight = 0
p_queue = []
heappush(p_queue, (0, now))
visited = set()
while p_queue:
    weight, now = heappop(p_queue)
    if now in visited:
        continue
    visited |= {now}
    answer[now] = weight
    for c in connect[now]:
        if c not in visited:
            heappush(p_queue, (weight + cost[now][c], c))
for a in answer:
    print(a)
### BUGGY CODE ###

from itertools import groupby
from operator import itemgetter

x,y,z,k = (int(x) for x in input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]
# key, group
ga0 = [{'val':key, 'cnt':len(list(group))} for key, group in groupby(a)]
ga = list(reversed(sorted(ga0, key=itemgetter('val'))))
gb = list(reversed(sorted([{'val':key, 'cnt':len(list(group))} for key, group in groupby(b)], key=itemgetter('val'))))
gc = list(reversed(sorted([{'val':key, 'cnt':len(list(group))} for key, group in groupby(c)], key=itemgetter('val'))))

lga, lgb = len(ga), len(gb)
ia,ib = 0,0
ca,cb = ga[0]['cnt'],gb[0]['cnt']
while ca*cb < k:
    if ia == lga-1 and ib == lgb-1:
        break
    elif ia == lga-1:
        ib += 1
        cb += gb[ib]['cnt']
    elif ib == lgb-1:
        ia += 1
        ca += ga[ia]['cnt']
    elif ga[ia+1]['val'] + gb[ib]['val'] >= ga[ia]['val'] + gb[ib+1]['val']:
        ia += 1
        ca += ga[ia]['cnt']
    else:
        ib += 1
        cb += gb[ib]['cnt']
d = []
for va in ga:
    for vb in gb:
        d.append((va['val']+vb['val'],va['cnt']*vb['cnt']))
gd0 = [{'val':key, 'cnt':sum(c_ for _, c_ in list(group))} for key, group in groupby(d,itemgetter(0))]
gd = list(reversed(sorted(gd0, key=itemgetter('val'))))[:k]

lgc, lgd = len(gc), len(gd)
ic,id = 0,0
cc,cd = gc[0]['cnt'],gd[0]['cnt']
while cc*cd < k:
    if ic == lgc-1 and id == lgd-1:
        break
    elif ic == lgc-1:
        id += 1
        cd += gd[id]['cnt']
    elif id == lgd-1:
        ic += 1
        cc += gc[ic]['cnt']
    elif gc[ic+1]['val'] + gd[id]['val'] >= gc[ic]['val'] + gd[id+1]['val']:
        ic += 1
        cc += gc[ic]['cnt']
    else:
        id += 1
        cd += gd[id]['cnt']
r = []
for vc in gc:
    for vd in gd:
        r.append((vc['val']+vd['val'],vc['cnt']*vd['cnt']))
gr0 = [{'val':key, 'cnt':sum(c_ for _, c_ in list(group))} for key, group in groupby(r,itemgetter(0))]
gr = list(reversed(sorted(gr0, key=itemgetter('val'))))[:k]
i = 0
for vr in gr:
    for j in range(vr['cnt']):
        print(vr['val'])
        i += 1
        if i == k:
            exit


### FIXED CODE ###

import heapq
x,y,z,k = (int(x) for x in input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
# heap
h = []
g = set()
heapq.heappush(h, (-(a[0]+b[0]+c[0]),0,0,0))
for i in range(k):
    q,ia,ib,ic = heapq.heappop(h)
    print(-q)
    ja,jb,jc = ia+1,ib,ic
    if ja<x and (ja,jb,jc) not in g:
        heapq.heappush(h, (-(a[ja]+b[jb]+c[jc]),ja,jb,jc))
        g.add((ja,jb,jc))
    ja,jb,jc = ia,ib+1,ic
    if jb<y and (ja,jb,jc) not in g:
        heapq.heappush(h, (-(a[ja]+b[jb]+c[jc]),ja,jb,jc))
        g.add((ja,jb,jc))
    ja,jb,jc = ia,ib,ic+1
    if jc<z and (ja,jb,jc) not in g:
        heapq.heappush(h, (-(a[ja]+b[jb]+c[jc]),ja,jb,jc))
        g.add((ja,jb,jc))
### BUGGY CODE ###

from collections import deque
import numpy as np
n,m,k=map(int,input().split())
link=[[] for _ in range(n)]
block=[[]  for _ in range(n)]
ans=[]
s=[]
for i in range(m):
    a,b=map(int,input().split())
    link[a-1].append(b-1)
    link[b-1].append(a-1)
for i in range(k):
  a,b=map(int,input().split())
  block[a-1].append(b-1)
  block[b-1].append(a-1)
for i in range(n):#スタートの選び方
    visited=[]
    q=deque([i])
    while len(q)>0:
        x=q.pop()
        visited.append(x)
        for j in link[x]:
            if j not in visited:
              if j not in q:
                q.append(j)
    ans.append(len(visited))
    s.append(visited)
res=[]
for i in range(n):
  l=len((set(link[i]+block[i])&set(s[i])))+1
  res.append(l)
print(*(np.array(ans)-np.array(res)))

### FIXED CODE ###

class UnionFind():
    def __init__(self,n):
      self.n=n
      self.root=[-1]*(n+1)
      self.rank=[0]*(n+1)
      
    def find(self,x):
      if self.root[x]<0:
        return x
      else:
        self.root[x]=self.find(self.root[x])
        return self.root[x]
    
    def unite(self,x,y):
      x=self.find(x)
      y=self.find(y)
      if x==y:
        return 0
      elif self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      else:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
          
    def Same(self,x,y):
      return self.find(x)==self.find(y)
    
    def size(self,x):
      return -self.root[self.find(x)]
import sys
input=sys.stdin.buffer.readline
n,m,k=map(int,input().split())
link=UnionFind(n)
f=[0]*n
block=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    link.unite(a,b)
    f[a]+=1
    f[b]+=1
for _ in range(k):
    a,b=map(int,input().split())
    block[a-1].append(b-1)
    block[b-1].append(a-1)
ans=[]
for i in range(n):
  ret=link.size(i)-f[i]-1
  for j in block[i]:
    if link.Same(i,j):
      ret-=1
  ans.append(ret)
print(*ans)
### BUGGY CODE ###

from collections import defaultdict

n = int(input())
s_list = []
d_list = []
cnt = 0
for i in range(n):
    s_list.append(str(input()))
    
    d = defaultdict(int)
    for j in range(len(s_list[i])):
        d[s_list[i][j]] += 1

    if i >= 1:
        if d in d_list:
            cnt += d_list.count(d)
    d_list.append(d)
    
print(cnt)


### FIXED CODE ###


from collections import Counter

N = int(input())
S = [''.join(map(str,(sorted(str(input()))))) for i in range(N)]
counter = Counter(S)

answer = sum(x*(x-1)//2 for x in counter.values())
print(answer)
### BUGGY CODE ###

def main():
    n,d,a = map(int,input().split())
    l = [list(map(int,input().split())) for i in range(n)]
    l.sort()
    count = 0
    import math

    i = 0
    

    while True:
        sn = i
        s = l[i][0]
        mi = math.ceil(l[i][1]/a)
        count += mi
        
        l1 = 0
        while i < n and l[i][0] <= s+2*d:
            
            l[i][1] -= mi*a
            if l[i][1] > 0:
                if l1 == 0:
                    l1 = i
            i += 1
            
        if l1 > 0:
            i = l1
        else:
            if i == n:
                print(count)
                exit()
    
if __name__ == "__main__":
    main()



### FIXED CODE ###

def main():
    n,d,a = map(int,input().split())
    l = [list(map(int,input().split())) for i in range(n)]
    l.sort()
    count = 0
    from collections import deque

    i = 0
    area = deque([])
    damage = deque([])
    total_damage = 0
    count = 0
    ans = 0
    for pos,hp in l:
        while area:
            ar = area[0]
            if ar < pos:
                area.popleft()
                power = damage.popleft()
                total_damage -= power
            else:
                break
        if hp <= total_damage:
            continue
        else:
            count = (hp-total_damage+a-1)//a
            ans += count
            total_damage += count*a
            area.append(pos+2*d)
            damage.append(count*a)

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

from functools import lru_cache
from math import gcd

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


@lru_cache(None)
def func(*x):
    n = len(x)
    if n == 2:
        return gcd(x[0], x[1])
    elif n == 1:
        return x[0]
    return gcd(func(*x[:n//2]), func(*x[n//2:]))


ans = 0
for i in range(N):
    tmp = A[i]
    A[i] = A[i+1 if i < N-1 else 0]
    ans = max(ans, func(*A))
    A[i] = tmp
print(ans)

### FIXED CODE ###

from itertools import accumulate
from math import gcd

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

l = list(accumulate(A[:-1], gcd, initial=0))
r = list(accumulate(A[::-1], gcd, initial=0))
print(max(gcd(l[i], r[N-i-1]) for i in range(N)))
### BUGGY CODE ###

def main():
    n = int(input())
    s = input().rstrip()
    sets_l = [set() for _ in range(n)]
    sets_r = [set() for _ in range(n)]
    sets_l[0].add(s[0])
    for i in range(1, len(s)):
        #sets_l[i] = sets_l[i] | sets_l[i-1]
        for j in range(i+1):
            sets_l[i].add(s[j:i+1])
    sets_r[n-1].add(s[n-1:])
    for i in reversed(range(len(s)-1)):
        sets_r[i] = sets_r[i] | sets_r[i+1]
        for j in reversed(range(i, len(s))):
            sets_r[i].add(s[i:j+1])
    ans = 0
    for i in range(i, len(s)-1):
        for v in sets_l[i]:
            if v in sets_r[i+1]:
                if ans < len(v):
                    ans = len(v)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

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

import collections
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n = int(input())
A = list(map(int, input().split()))
f2 = 0
f4 = 0
for a in A:
    c = collections.Counter(prime_factorize(a))
    if c[2] == 1:
        f2 += 1
    elif c[2] >= 2:
        f4 += 1
if n -f2//2 *2 -f4 *3 <= 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
f2 = 0
f4 = 0
f_another = 0
for a in A:
    #c = collections.Counter(prime_factorize(a))
    if a%4 == 0:
        f4 += 1
    elif a%2 == 0:
        f2 += 1
    else:
        f_another +=1
if n%2 == 0 and (n -f2//2 *2 -f4 *2 <= 0):
    print('Yes')
elif n%2 == 1 and (n -f2//2 *2 -f4 *2 <= 1):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

N = int(input())
S =  input()
max_length = 0
for i in range(N):
    j = i + 1
    while S[i:j] in S[j:N]:
        current_length = j-i
        if current_length > max_length:
            max_length = current_length
        j += 1
    '''
    #for j in range(i+1,N):
        if S[i:j] in S[j:N]:
            continue
        else:
            current_length = j-i-1
            if current_length > max_length:
                max_length = current_length
            break
    '''
print(max_length)

### FIXED CODE ###

n = int(input())
S = input()
N = [0]*n
j = 0
 
for i in range(n):
  while S[i:j] in S[j:n]:
    N[i] = j-i
    j += 1
    
print(max(N))
### BUGGY CODE ###

s = input()

count = 0
while True:
    sn = s + '\n'
    for i in range(len(s)):
        if sn[i-1] + sn[i] == '10' or sn[i-1] + sn[i] == '01':
            s = sn[:i-1] + sn[i+1:len(sn)-1]
            count += 1
            break
    if len(s) == 0 or all(c == '0' for c in s) or all(c == '1' for c in s):
        break

print(count * 2)

### FIXED CODE ###

s = input()

zero = s.count('0')
one = s.count('1')

print(2 * min(zero, one))
### BUGGY CODE ###

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

for i in range(1,n+1):
    count = 0
    for j in all:
        if(i == j ):
            count += 1
    print(count)






### FIXED CODE ###

n = int(input())
all = list(map(int,input().split()))
result ={}
for i in range(n):
    result[i] = 0

for i in all:
    result[i-1] += 1

#print(result)
for i in range(n):
    print(result[i])
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
r = N//R
g = N//G
ans = 0

for i in range(r+1):
  for j in range(g+1):
    tmp = N - R*i - G*j
    if tmp >= 0 and tmp%B == 0:
      ans += 1
      
print(ans)

### FIXED CODE ###

R,G,B,N=map(int,input().split())
ans=0
 
for i in range(N//R+1):
    for j in range((N-R*i)//G+1):
        b=N-(R*i+G*j)
        if b==0 or  b%B==0: 
            ans+=1
 
print(ans)
### BUGGY CODE ###

import math

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

for _ in range(m):
    max_index = prices.index(max(prices))
    prices[max_index] = prices[max_index] / 2

total = 0
for price in prices:
    total += math.floor(price)

print(total)


### FIXED CODE ###

import math
import heapq

n, m = map(int, input().split())
prices = list(map(int, input().split()))
hq = []


def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)


def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt


# 優先度付キューの作成
for price in prices:
    _heappush_max(hq, price)

# 割引適用
for _ in range(m):
    target = _heappop_max(hq)
    _heappush_max(hq, target/2)

total = 0
for price in hq:
    total += math.floor(price)

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

_ = int(input())
members = input()

counts = []
for i in range(len(members)):
    count=0
    for j in range(len(members)):
        if i == j:
            continue
        else:
            if (members[j] == 'W' and i<j) or (members[j] == 'E' and i>j):
                continue
            else:
                count+=1
        if counts:
            if count > min(counts):
                break
    counts.append(count)
print(min(counts))

### FIXED CODE ###

n = int(input())
members = input()
m_e = members.count("E")
cost = m_e
costs = []
for i in range(n):
    if members[i]=="E":
        cost-=1
    if (i!=0 and members[i-1]=="W"):
        cost+=1
    costs.append(cost)
print(min(costs))
### BUGGY CODE ###

import  fractions
from functools import reduce
import sys
input = sys.stdin.readline
def main():
    n=int(input())
    a=list(map(int,input().split()))
    # tmp = lcm(*a)
    mod=pow(10,9) + 7
    m=0
    ans=0
    tmp = a[0]
    for i in range(1,len(a)):
        tmp = (tmp*a[i]) // fractions.gcd(tmp,a[i])
    
    for i,v in enumerate(a):
        m=tmp//v
        ans+=m
    ans = ans % mod
    print(ans)


if __name__=='__main__':
    main()


### FIXED CODE ###

import  fractions
from functools import reduce
import sys
input = sys.stdin.readline
def main():
    n=int(input())
    a=list(map(int,input().split()))
    # tmp = lcm(*a)
    mod=pow(10,9) + 7
    m=0
    ans=0
    tmp = a[0]
    for i in range(1,len(a)):
        tmp = (tmp*a[i]) // fractions.gcd(tmp,a[i])
    
    for i,v in enumerate(a):
        m=tmp//v
        ans+=m
    ans = ans % mod
    print(ans)


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

import sys

d, g = [int(x) for x in input()[:-2].split()]
pc = [[int(x) for x in input()[:-2].split()] for _ in range(d)]

def dfs(choice):
    if len(choice) == d:
        if sum(x * (i + 1) + (ci if x == pi else 0) for i, (x, (pi, ci)) in enumerate(zip(choice, pc))) >= g:
            return sum(choice)
        else:
            return sys.maxsize
    else:
        return min(dfs(choice[:] + [x]) for x in range(pc[len(choice)][0] + 1))

print(dfs([]))


### FIXED CODE ###

import itertools
import math
import sys

d, g = [int(x) for x in input()[:-2].split()]
pc = [[int(x) for x in input()[:-2].split()] for _ in range(d)]

def search(choice):
    total = sum(((i + 1) * p + c) * chosen for i, ((p, c), chosen) in enumerate(zip(pc, choice)))
    count = sum(p * chosen for (p, _), chosen in zip(pc, choice))

    if total < g:
        partial = d - list(reversed(choice)).index(0)
        partial_count = math.ceil((g - total) / partial)
        if partial_count <= pc[partial - 1][0]:
            count += partial_count
        else:
            count = sys.maxsize

    return count

print(min(search(choice) for choice in itertools.product(*([0, 1] for _ in range(d)))))
### BUGGY CODE ###

from collections import deque
s = input()
sque = deque(s)
q = int(input())
que = []
for i in range(q):
    que.append(list(map(str,input().split())))
    if(len(que[i])==3):
        if que[i][1] == '1':
            sque.appendleft(que[i][2])
        else:
            sque.append(que[i][2])
    else:
        sque.reverse()
print("".join(list(sque)))

### FIXED CODE ###

from collections import deque
s = input()
sque = deque(s)
q = int(input())
que = [0] * q
flg = False
for i in range(q):
    que[i] = (list(map(str,input().split())))
    if(len(que[i])==3):
        if que[i][1] == '1':
            if flg:
                sque.append(que[i][2])
            else:
                sque.appendleft(que[i][2])
        else:
            if flg:
                sque.appendleft(que[i][2])
            else:
                sque.append(que[i][2])
    else:
        if flg:
            flg = False
        else:
            flg = True
if flg:
    sque.reverse()
    print("".join(list(sque)))
else:
    print("".join(list(sque)))