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

s = input().rstrip()
t = input().rstrip()
len_s = len(s)
len_t = len(t)
lcs = [[""] * (len_t+1) for _ in range(len_s+1)]
for i in range(1, len_s+1):
    for j in range(1, len_t+1):
        if s[i-1] == t[j-1]:
            lcs[i][j] = lcs[i-1][j-1] + s[i-1]
        else:
            if len(lcs[i][j-1]) > len(lcs[i-1][j]):
                lcs[i][j] = lcs[i][j-1] 
            else:
                lcs[i][j] = lcs[i-1][j] 
print(lcs[-1][-1])

### FIXED CODE ###

s = input().rstrip()
t = input().rstrip()
len_s = len(s)
len_t = len(t)

# Get longest LCS num
dp = [[0] * (len_t+1) for _ in range(len_s+1)]
for i in range(1, len_s+1):
    for j in range(1, len_t+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

# Restore LCS
h, w = len_s, len_t
ans = ""
while dp[h][w] != 0:
    while dp[h][w] == dp[h-1][w]:
        h -= 1
    while dp[h][w] == dp[h][w-1]:
        w -= 1
    h -= 1
    w -= 1
    ans += t[w]

print(ans[::-1])
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
    a.append(list(map(int,input().split())))

ans=0
cnt=0
for j in range(n*n//2+1):
    f=0
    q=[]
    for i in range(n):        
        if len(a[i])>0 and len(a[a[i][0]-1])>0 and i+1==a[a[i][0]-1][0] and i<a[i][0]-1:
            #a[a[i][0]-1].pop(0)
            #a[i].pop(0)
            q.append(i)
            q.append(a[i][0]-1)
            f+=1    
            cnt+=1
    if len(q)>0:
        for k in q:
            a[k].pop(0)
            
            
    if f==0 and cnt<n*(n-1)//2:
        print(-1)
        exit()
    elif f>0:
        ans+=1
    else:
        print(ans)
        exit()


### FIXED CODE ###

from sys import setrecursionlimit as SRL, stdin

SRL(10 ** 7)
rd = stdin.readline
rrd = lambda: map(int, rd().strip().split())

q = [[]]
l = [0] * 1005
d = [0] * 1005
hv = [0] * 1005

def dfs(x,y):
    hv[x] = 1
    for i in range(l[x],n-1):

        if q[x][i] == y:
            l[x] = i+1
            hv[x] = 0

            d[q[x][i]] += 1
            d[x] += 1
            d[x] = max(d[x],d[q[x][i]])
            d[q[x][i]] = max(d[x], d[q[x][i]])

            return
        if hv[q[x][i]]:
            print(-1)
            exit(0)
        dfs(q[x][i],x)
        d[x] = max(d[q[x][i]],d[x])


    hv[x] = 0
    l[x] = n

n = int(input())
for i in range(n):
    a = list(rrd())
    q.append(a)

for i in range(1,n+1):
    dfs(i,0)

print(max(d))
### BUGGY CODE ###

n = int(input())
s = input()

num = [0,1,2,3,4,5,6,7,8,9]
memo = []
for i in num:
  for j in num:
    for k in num:
      memo.append(str(num[i]) + str(num[j]) + str(num[k]))

ans = 0

for i in memo:
  x = 0
  for j in range(n):
    if i[x] == s[j]:
      x += 1
      if x == 3:
        break
  if x == 3:
    ans += 1
    
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

num = [0,1,2,3,4,5,6,7,8,9]
memo = []
for i in num:
  for j in num:
    for k in num:
      memo.append(str(num[i]) + str(num[j]) + str(num[k]))

ans = 0

for i in memo:
  x = 0
  for j in range(n):
    if i[x] == s[j]:
      x += 1
      if x == 3:
        break
  if x == 3:
    ans += 1
    
print(ans)
### BUGGY CODE ###

from collections import Counter

N = int(input())
S = [input() for i in range(N)]
clist = Counter(S)
tmp = 0
rlist = []

for i in range(len(clist)):
	if tmp <= int(clist.most_common()[i][1]):
		tmp = int(clist.most_common()[i][1])
		rlist.append(clist.most_common()[i][0])

rlist.sort(reverse=False)

for i in range(len(rlist)):
  print(rlist[i])


### FIXED CODE ###

from collections import Counter

N = int(input())
S = [input() for _ in range(N)]
clist = Counter(S)
M = max(clist.values())
rlist = []

for i in clist.keys():
    if clist[i] == M:
        rlist.append(i)

rlist.sort(reverse=False)

for i in range(len(rlist)):
  print(rlist[i])
### BUGGY CODE ###

from math import gcd
import numpy as np

def setwise_coprime_check_fun(A_list):
    gcd_all = A_list[0]
    for i in range(N - 1):
        gcd_all = gcd(gcd_all, A_list[i + 1])
        if gcd_all == 1:
            break
    return gcd_all

def preprocess_fun(A_max):
    p_flg = [True] * (A_max + 1)
    D = [0] * (A_max + 1)
    p_flg[0] = 0
    p_flg[1] = 0
    for i in range(2, A_max + 1, 1):
        if p_flg[i]:
            for j in range(i, A_max + 1, i):
                p_flg[j] = False
                D[j] = i
    return D

def pairwise_coprime_check(A_list, D):
    p_count = [0] * (max(A_list) + 1)
    p_count_temp = [0] * (max(A_list) + 1)
    for A in A_list:
        temp = A
        while temp != 1:
            if p_count[D[temp]] == 1:
                return 0
            else:
                p_count_temp[D[temp]] = 1
            temp = temp // D[temp]
        p_count = list(np.array(p_count) + np.array(p_count_temp))
        p_count_temp = [0] * (max(A_list) + 1)
    return 1

# 標準入力
N = int(input())
A_list = list(map(int, input().split(" ")))

# 整数の最大値を取得
A_max = max(A_list)

# 本体
if(setwise_coprime_check_fun(A_list) != 1):
    print("not coprime")
else:
    D = preprocess_fun(A_max)
    if pairwise_coprime_check(A_list, D) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

### FIXED CODE ###

from math import gcd
import numpy as np

def setwise_coprime_check_fun(A_list, N):
    gcd_all = A_list[0]
    for i in range(N - 1):
        gcd_all = gcd(gcd_all, A_list[i + 1])
        if gcd_all == 1:
            break
    return gcd_all

def preprocess_fun(A_max):
    p_flg = [True] * (A_max + 1)
    D = [0] * (A_max + 1)
    p_flg[0] = False
    p_flg[1] = False
    for i in range(2, A_max + 1, 1):
        if p_flg[i]:
            for j in range(i, A_max + 1, i):
                p_flg[j] = False
                D[j] = i
    return D

def pairwise_coprime_check(A_list, D):
    p_count = [0] * (max(A_list) + 1)
    for A in A_list:
        temp = A
        d = 0
        while temp != 1:
            if p_count[D[temp]] == 1 and d != D[temp]:
                return 0
            p_count[D[temp]] = 1
            d = D[temp]
            temp = temp // D[temp]
    return 1

## 標準入力
N = int(input())
A_list = list(map(int, input().split(" ")))

# 整数の最大値を取得
A_max = max(A_list)

# 本体
if(setwise_coprime_check_fun(A_list, N) != 1):
    print("not coprime")
else:
    D = preprocess_fun(A_max)
    if pairwise_coprime_check(A_list, D) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")
### BUGGY CODE ###

x = int(input())
for i in range(1, x+1):
    if sum([j for j in range(1, i+1)]) >= x:
        print(i)
        break

### FIXED CODE ###

x = int(input())
for i in range(1, x+1):
    if i * (i+1) / 2 >= x:
        print(i)
        break
### BUGGY CODE ###

def divisors(n):
    d=[]
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            d.append(i)
            if i!=n//i:
                d.append(n//i)
    d.sort()
    return d

a = 0
n = int(input())
for i in range(1,n+1):
    a += i*len(divisors(i))
print(a)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1,n+1):
    a = n//i
    ans += i*(a*(a+1)//2)
print(ans)
### BUGGY CODE ###

import bisect

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

for i in range(m):
    x = a.pop() // 2
    bisect.insort_right(a, x)

print(sum(a))

### FIXED CODE ###

import heapq

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

heapq.heapify(a)
for i in range(m):
    x = heapq.heappop(a)
    heapq.heappush(a, (-1) * (-x // 2))

print(-sum(a))
### BUGGY CODE ###

import collections

x = input()
y = input()

c = collections.Counter(x)
d = collections.Counter(y)

chars = []
for i in c.items():
    if i[1] >= 2:
        chars.append(i[0])
for j in d.items():
    if j[1] >= 2:
        chars.append(j[0])

chars = list(set(chars))



for i in chars:
    li = []
    li_2 = []
    for j in range(len(x)):
        if i == x[j]:
            li.append(y[j])
        elif i == y[j]:
            li_2.append(x[j])
        if len(li) >= 2:
            if len(list(set(li))) == 1:
                continue
            else:
                print('No')
                exit()
        elif len(li_2) >= 2:
            if len(list(set(li_2))) == 1:
                continue
            else:
                print('No')
                exit()

print('Yes')


### FIXED CODE ###

s = input()
t = input()

alphabet_1 = [[] for _ in range(26)]
alphabet_2 = [[] for _ in range(26)]

for i in range(len(s)):
    if alphabet_1[ord(s[i])-97] == []:
        alphabet_1[ord(s[i])-97] = t[i]
    else:
        if alphabet_1[ord(s[i])-97] == t[i]:
            continue
        else:
            print('No')
            exit()

    if alphabet_2[ord(t[i])-97] == []:
        alphabet_2[ord(t[i])-97] = s[i]
    else:
        if alphabet_2[ord(t[i])-97] == s[i]:
            continue
        else:
            print('No')
            exit()

print('Yes')
### BUGGY CODE ###

from itertools import combinations

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

comb = combinations(l, 3)
ans = 0

for a, b, c in comb:
    if a < b+c and b < c+a and c < a+b:
        ans += 1

print(ans)


### FIXED CODE ###

from bisect import bisect_left

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

l.sort()

ans = 0

for i in range(n):
    for j in range(i+1, n):
        tmp = bisect_left(l, l[i]+l[j]) - 1
        ans += tmp - j

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

n = int(input())
a = []
for i in range(n):
	s = int(input())
	if s in a:
		x = a.index(s)
		a.pop(x)
	else:
		a.append(s)
print(len(a))

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
	s = int(input())
	a.append(s)
a.sort()
a.append(0)
length = 0
i = 0
while i < n:
	counter = 1
	count = 0
	for k in range(i+1,n+1):
		if a[i] != a[k] and counter%2 == 1:
			length += 1
			i = i+count+1
			break
		elif a[i] != a[k] and counter%2 == 0:
			i = i+count+1
			break
		elif a[i] == a[k]:
			counter += 1
			count += 1
print(length)
### BUGGY CODE ###

# かつっぱさん見て
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
babies=[(q,i) for i,q in enumerate(a)]
babies.sort(reverse=True)

dp=defaultdict(int)
ans=0
for l in range(n):
  for r in range(n):
    if l+r==n:
      ans=max(ans,dp[(l,r)])
      break
    act,ind=babies[l+r]
    dp[(l+1,r)]=max(dp[(l+1,r)],dp[(l,r)]+act*abs(ind-l))
    dp[(l,r+1)]=max(dp[(l,r+1)],dp[(l,r)]+act*abs(ind-(n-1-r)))

print(ans)
                    

### FIXED CODE ###

# かつっぱさん見て
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
babies=[(q,i) for i,q in enumerate(a)]
babies.sort(reverse=True)

dp=defaultdict(int)
ans=0
for l in range(n):
  for r in range(n):
    if l+r==n:
      ans=max(ans,dp[(l,r)])
      break
    act,ind=babies[l+r]
    dp[(l+1,r)]=max(dp[(l+1,r)],dp[(l,r)]+act*abs(ind-l))
    dp[(l,r+1)]=max(dp[(l,r+1)],dp[(l,r)]+act*abs(ind-(n-1-r)))

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

import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return list(map(int, input().split()))
mod = 10 ** 9 + 7

n = INT()
a = LIST()
arr = [0 for _ in range(61)]
for i in range(1, n + 1):
    bn = bin(a[i - 1])[2:]
    l = len(bn)
    for j in range(l):
        arr[j + 61 - l] += int(bn[j])
ans = 0
for i in range(61):
    ans *= 2
    arri = arr[i]
    ans += arri * (n - arri if arri != 0 else 0)
    ans %= mod
print(ans)


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return list(map(int, input().split()))
mod = 10 ** 9 + 7

n = INT()
a = LIST()
arr = [0 for _ in range(61)]
for i in range(n):
    ai = a[i]
    for j in reversed(range(61)):
        arr[j] += ai % 2
        ai //= 2
ans = 0
for i in range(61):
    ans *= 2
    arri = arr[i]
    ans += arri * (n - arri if arri != 0 else 0)
    ans %= mod
print(ans)
### BUGGY CODE ###

S = list(input())

cnt = 0
e = len(S)-1
i = 0
while i < e:
    if S[i] == 'B' and S[i+1] == 'W':
        S[i] = 'W'
        S[i+1] = 'B'
        cnt += 1
        i = max(i-2, -1)
    i += 1

print(cnt)

### FIXED CODE ###

S = list(input())

cnt = 0
t = 0
for i in range(len(S)):
    if S[i] == 'W':
        cnt += t
    else:
        t += 1

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

N = int(input())
ABCs = [
  sorted(map(int, input().split()))
  for _ in range(3)
]

def table(As, Bs):
  ib = 0
  result = []
  for a in As:
    while ib < N and Bs[ib] <= a:
      ib += 1
    result.append(ib)
  return result

def table2(Bs, Cs):
  ic = 0
  result = []
  for b in Bs:
    while ic < N and Cs[ic] <= b:
      ic += 1
    result.append(N-ic)
  return result

def f(ABCs):
  AB = table(ABCs[0], ABCs[1])
  BC = table2(ABCs[1], ABCs[2])
  acc = 0
  
  for i, bmin in enumerate(AB):
      acc += sum(BC[bmin:])
  
  return acc
  
print(f(ABCs))

### FIXED CODE ###

N = int(input())
As, Bs, Cs = [
  sorted(map(int, input().split()))
  for _ in range(3)
]

from bisect import *

def sums():
  for b in Bs:
  	yield bisect_left(As, b) * (N - bisect_right(Cs, b))

print(sum(sums()))
### BUGGY CODE ###

N=int(input())

for i in range(1,N+1):
    count=0
    for x in range(1,int(i**0.5)):
        for y in range(1,N-x**2+1):
            if x**2+y**2+x*y>=i:break
            for z in range(1,N-(x**2+y**2+x*y)+1):
                if x**2+y**2+z**2+x*y+y*z+x*z==i:count+=1
                if x**2+y**2+z**2+x*y+y*z+x*z>i:break
    print(count)

### FIXED CODE ###

N=int(input())
dic={}
for i in range(1,N+1):
    dic[i]=0
for x in range(1,int(N**0.5)):
    for y in range(1,N-x**2):
        for z in range(1,N-(x**2+y**2+x*y)):
            if x**2+y**2+z**2+x*y+x*z+y*z>N:break
            if x**2+y**2+z**2+x*y+x*z+y*z in dic:
                dic[x**2+y**2+z**2+x*y+x*z+y*z]+=1


for i in range(1,N+1):
    print(dic[i])
### BUGGY CODE ###

A, B, C, D, E, F = map(int, input().split())

water = set()
sugar = set()

for i in range(F+1):
    for j in range(F+1-A):
        w = (100*A*i) + (100*B*j)
        if w <= F:
            water.add(w)

for i in range(F+1):
    for j in range(F+1):
        s = (i*C)+(j*D)
        if s <= F:
            sugar.add(s)

per = -10000
for w in water:
    for s in sugar:
        ws = w+s
        # 砂糖水の質量合計はFg以下 and 砂糖が溶け残らない
        if (0 < ws <= F) and (s <= w*E // 100):
            if s/(ws) > per:
                per = s/(ws)
                ans = ws, s

print(ans[0], ans[1])

### FIXED CODE ###

A, B, C, D, E, F = map(int, input().split())

water = set()
sugar = set()

for i in range(0, F+1, 100*A):
    for j in range(0, F+1-A, 100*B):
        water.add(i+j)

for i in range(0, F+1, C):
    for j in range(0, F+1-C, D):
        sugar.add(i+j)

per = -1
for w in water:
    for s in sugar:
        ws = w+s
        # 砂糖水の質量合計はFg以下 and 砂糖が溶け残らない
        if 0 < ws <= F and s <= w*E // 100:
            if s/(ws) > per:
                per = s/(ws)
                ans = ws, s

print(ans[0], ans[1])
### BUGGY CODE ###

import heapq

N, K=map(int, input().split())
A=list(map(int, input().split()))
F=list(map(int, input().split()))
A=sorted(A, reverse=False)
F=sorted(F, reverse=True)

C=[[-A[i]*F[i], A[i], F[i]] for i in range(N)]

heapq.heapify(C)

for _ in range(K):
  tmp=heapq.heappop(C)
  if tmp[1]==0:
    print(0)
    exit()
    
  a=tmp[1]-1
  heapq.heappush(C, [-a*tmp[2], a, tmp[2]])
  
tmp=heapq.heappop(C)
print(-tmp[0])

### FIXED CODE ###

import math

N, K=map(int, input().split())
A=list(map(int, input().split()))
F=list(map(int, input().split()))
A=sorted(A, reverse=False)
F=sorted(F, reverse=True)

a=-1
b=max([A[i]*F[-i-1] for i in range(N)])
while b-a>1:
  tmp=(a+b)//2
  c=sum([max(0, math.ceil(A[i]-tmp/F[i])) for i in range(N)])
  if c<=K:
    b=tmp
  else:
    a=tmp
print(b)
### BUGGY CODE ###

def solve():
  n=int(input())
  arr1=list(map(int,input().split()))
  arr2=list(map(int,input().split()))
  tlist=[0]
  for val in arr1:
    tlist.append(tlist[-1]+val)
  t=tlist[-1]
  ans=0
  vlist=[0]
  for i in range(1,2*t):
    tt=i/2
    tmp=10**18
    for j in range(n):
      if tt<=tlist[j]:
        tmp=min(tmp,arr2[j]+(tlist[j]-tt))
      elif tlist[j+1]<=tt:
        tmp=min(tmp,arr2[j]+(tt-tlist[j+1]))
      else:
        tmp=min(tmp,arr2[j])
    tmp=min(tmp,tt)
    tmp=min(tmp,t-tt)
    vlist.append(tmp)
  vlist.append(0)
  for i in range(len(vlist)-1):
    ans+=(vlist[i]+vlist[i+1])/4
  print(ans)
solve()

### FIXED CODE ###

def solve():
  n=int(input())
  arr1=list(map(int,input().split()))
  arr2=list(map(int,input().split()))
  tlist=[0]
  for val in arr1:
    tlist.append(tlist[-1]+val)
  t=tlist[-1]
  ans=0
  for i in range(1,2*t):
    tt=i/2
    tmp=10**18
    for j in range(n):
      if tt<=tlist[j]:
        tmp=min(tmp,arr2[j]+(tlist[j]-tt))
      elif tlist[j+1]<=tt:
        tmp=min(tmp,arr2[j]+(tt-tlist[j+1]))
      else:
        tmp=min(tmp,arr2[j])
    tmp=min(tmp,tt)
    tmp=min(tmp,t-tt)
    ans+=tmp
  print(ans/2)
solve()
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

N = int(input())
a = list(map(int, input().split()))
assert len(a) == N

# 解説を参照
# https://img.atcoder.jp/arc101/editorial.pdf

def mergesort(S, f, t):
    if t - f <= 1:
        return 0, S[f:t]

    n1, S1 = mergesort(S, f, (f + t) // 2)
    n2, S2 = mergesort(S, (f + t) // 2, t)
    T = []
    n = 0
    i = 0
    j = 0
    while i < len(S1) and j < len(S2):
        if S1[i] <= S2[j]:
            T.append(S1[i])
            i += 1
            n += len(S2) - j
        else:
            T.append(S2[j])
            j += 1
    if i < len(S1):
        T.extend(S1[i:])
    if j < len(S2):
        T.extend(S2[j:])
    return n1 + n2 + n, T

def inversion(S):
    """リストSの転倒数"""
    n, __ = mergesort(S, 0, len(S))
    return n

def n_median_larger_than_or_equal_to(x):
    """aの部分列の中央値のうちx以上のものの個数"""

    # aの要素を -1, 1 に置換したリスト
    b = [-1 if e < x else 1 for e in a]
    # bの累積和
    S = [0]
    for e in b:
        S.append(S[-1] + e)
    # Sの転倒数
    return inversion(S)

# 条件を満たす x の最大値を2分探索で探す
lo = 1
hi = max(a)

ncomb = N * (N + 1) // 2    # 部分列の個数

while lo < hi:
    mid = (lo + hi + 1) // 2
    nm = n_median_larger_than_or_equal_to(mid)
    if nm >= (ncomb + 1) // 2:
        lo = mid
    else:
        hi = mid - 1

print(lo)


### FIXED CODE ###

#!/usr/bin/env pypy3
# -*- coding: utf-8 -*-

N = int(input())
a = list(map(int, input().split()))
assert len(a) == N

# 解説を参照
# https://img.atcoder.jp/arc101/editorial.pdf

def mergesort(S, f, t):
    global T

    if t - f <= 1:
        return 0

    mid = (f + t) // 2
    n1 = mergesort(S, f, mid)
    n2 = mergesort(S, mid, t)
    n = n1 + n2
    i = f
    j = mid
    k = f
    while i < mid and j < t:
        if S[i] <= S[j]:
            T[k] = S[i]
            i += 1
            n += t - j
        else:
            T[k] = S[j]
            j += 1
        k += 1

    while i < mid:
        T[k] = S[i]
        i += 1
        k += 1
    assert k == j
    for i in range(f, k):
        S[i] = T[i]
    return n

def inversion(S):
    """リストSの転倒数"""
    global T
    T = [0] * len(S)
    return mergesort(S, 0, len(S))

def n_median_larger_than_or_equal_to(x):
    """aの部分列の中央値のうちx以上のものの個数"""

    # aの要素を -1, 1 に置換したリスト
    b = [-1 if e < x else 1 for e in a]
    # bの累積和
    S = [0]
    for e in b:
        S.append(S[-1] + e)
    # Sの転倒数
    return inversion(S)

# 条件を満たす x の最大値を2分探索で探す
lo = 1
hi = max(a)

ncomb = N * (N + 1) // 2    # 部分列の個数

while lo < hi:
    mid = (lo + hi + 1) // 2
    nm = n_median_larger_than_or_equal_to(mid)
    if nm >= (ncomb + 1) // 2:
        lo = mid
    else:
        hi = mid - 1

print(lo)
### BUGGY CODE ###

#coding:utf-8

import sys
from collections import defaultdict

if __name__ == "__main__":
    N, M = map(int, input().split(" "))

    V = set()
    E = []
    for i in range(M):
        a, b, c = map(int, input().split(" "))
        V.add(a)
        V.add(b)
        E.append((a, b, -c))

    dist = defaultdict(lambda :10**20 + 1)
    pre = {}
    dist[1] = 0


    for i in range(1, len(V)):
        for edge in E:
            u = edge[0]
            v = edge[1]

            if dist[v] > dist[u] + edge[2]:
                dist[v] = dist[u] + edge[2]
                pre[v] = u

    is_cycle = False
    cycle_node = []
    for edge in E:
        u = edge[0]
        v = edge[1]
        if dist[u] + edge[2] < dist[v]:
            is_cycle = True
            cycle_node.append(u)

    is_inf = False
    if is_cycle:
        next_node = N
        route = []
        while next_node != 1:
            route.append(next_node)
            next_node = pre[N]
        route.append(1)

        for n in cycle_node:
            if n in route:
                is_inf = True
                break

    if is_inf:
        print ("inf")
    else:
        print (-dist[N])


### FIXED CODE ###

#coding:utf-8

import sys
from collections import defaultdict

if __name__ == "__main__":
    N, M = map(int, input().split(" "))

    V = set()
    E = []
    for i in range(M):
        a, b, c = map(int, input().split(" "))
        V.add(a)
        V.add(b)
        E.append((a, b, -c))

    dist = defaultdict(lambda :10**20 + 1)
    pre = {}
    dist[1] = 0


    for i in range(1, len(V)):
        for edge in E:
            u = edge[0]
            v = edge[1]

            if dist[v] > dist[u] + edge[2]:
                dist[v] = dist[u] + edge[2]
                pre[v] = u

    is_cycle = False
    cycle_node = []
    for edge in E:
        u = edge[0]
        v = edge[1]
        if dist[u] + edge[2] < dist[v]:
            is_cycle = True
            cycle_node.append(u)

    is_inf = False
    if is_cycle:
        route_node = N
        while route_node != 1:
            route_node = pre[route_node]
            if route_node in cycle_node:
                is_inf = True
                break


    if is_inf:
        print ("inf")
    else:
        print (-dist[N])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    s = input()[:-1]
    q = int(input())
    tmp = [input().split() for _ in range(q)]

    for t in tmp:
        if len(t) == 1:
            s = s[::-1]
        else:
            f = int(t[1])
            c = t[2]
            if f == 1:
                s = c + s
            else:
                s = s + c
                
    print(s)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque

def main():
    input = sys.stdin.readline

    s = input()[:-1]
    q = int(input())
    tmp = [input().split() for _ in range(q)]

    flag = 0
    ans = deque([s])
    for t in tmp:
        if len(t) == 1:
            flag = ~flag 
        else:
            f = int(t[1])
            c = t[2]
            if (f == 1 and flag == 0) or (f ==2 and flag == -1):
                ans.appendleft(c)
            else:
                ans.append(c)
    if flag == 0:
        print(''.join(ans))
    else:
        print(''.join(ans)[::-1])

if __name__ == '__main__':
    main()