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

#O(ElogV)
import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

def dis(p,q):
    cand = ((x[p]-x[q])**2+(y[p]-y[q])**2)**0.5 - r[p] - r[q]
    return max(cand,0)
    

Xs,Ys,Xt,Yt = map(int,input().split())
n = int(input())
x = [0]*(n+2)
y = [0]*(n+2)
r = [0]*(n+2)
x[0] = Xs
y[0] = Ys
x[1] = Xt
y[1] = Yt
for i in range(2,n+2):
    x[i],y[i],r[i] = map(int,input().split())
edge = [[[0,0] for j in range(n+2)]for i in range(n+2)]

for i in range(n+2):
    for j in range(i,n+2):
        edge[i][j] = [dis(i,j),j]
        edge[j][i] = [dis(i,j),i]
n += 2
res = dijkstra_heap(0)
print(res[1])

### FIXED CODE ###

Xs,Ys,Xt,Yt = map(int,input().split())
n = int(input())
p = [(Xs,Ys,0),(Xt,Yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
cost = [[0]*(n+2)for i in range(n+2)]

for i in range(n+2):
    for j in range(i,n+2):
        cost[i][j] = cost[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0)
n += 2
s = 0
#始点sから各頂点への最短距離
#n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
d = [float("inf")] * n
used = [False] * n
d[s] = 0
    
while True:
    v = -1
    #まだ使われてない頂点の中から最小の距離のものを探す
    for i in range(n):
        if (not used[i]) and (v == -1):
           v = i
        elif (not used[i]) and d[i] < d[v]:
            v = i
    if v == -1:
           break
    used[v] = True
           
    for j in range(n):
           d[j] = min(d[j],d[v]+cost[v][j])
print(d[1])
### BUGGY CODE ###

a, b, n = map(int, input().split())
if n < b:
    print((a*n)//b)
else:
    ans = -1
    for x in range(b//a, b+a):
        tmp = (a*x)//b - a*(x//b)
        if tmp > ans:
            ans = tmp
        elif tmp < ans:
            break
    print(ans)

### FIXED CODE ###

a, b, n = map(int, input().split())

def f(x):
    return (a*x)//b-a*(x//b)

if n < b:
    print(f(n))
else:
    print(f(b-1))
### BUGGY CODE ###

N = int(input())

def prime_factorize(n):
    a = []
    i = 1
    while n % (2**i) == 0:
        a.append(2**i)
        n //= (2**i)
        i += 1
    f = 3
    while True:
        i = 1
        while n%(f**i) == 0:
            if n % (f**i) == 0:
                a.append(f**i)
                n //= f**i
                i += 1
            else:
                f += 2
                break

        if n == 1:
            break

    return a

list = prime_factorize(N)

if len(list)==0:
    print(0)
else:
    print(len(list))



### FIXED CODE ###

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 = prime_factorize(N)
z = set()
cnt = 0

while len(a) > 0:
    num = a.pop(0)
    cursor = num
    while True:
        if num not in z:
            z.add(num)
            break
        elif len(a) <= 0:
            break
        elif cursor != a[0]:
            break
        num *= a.pop(0)

print(len(z))
### BUGGY CODE ###

s = input()
k = int(input())
n = len(s)

se = set()
for i in range(n):
    for j in range(i+1,n+1):
#        print(i,j,s[i:j])
        se.add(s[i:j])
#print(se)
l = sorted(list(se))
print(l[k-1])

### FIXED CODE ###

s = input()
se = (s)
k = int(input())
n = len(s)

se = set()
for i in range(n):
    for j in range(i+1,i+1+k):
#        print(i,j,s[i:j])
        se.add(s[i:j])
#print(se)
l = sorted(list(se))
print(l[k-1])
        










#TLE 
'''
se = set()
for i in range(n):
    for j in range(i+1,n+1):
#        print(i,j,s[i:j])
        se.add(s[i:j])
#print(se)
l = sorted(list(se))
print(l[k-1])
'''
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    N, M = map(int, input().split())
    arr = [list(map(int, input().split())) for i in range(M)]
    ID = [True]*N
    for arrs in arr:
        L, R = arrs
        for i in range(N):
            if L-1 <= i and i < R:
                continue
            else:
                ID[i] = False
    print(ID.count(True))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    N, M = map(int, input().split())
    maxL, minR = 0, N+1
    for i in range(M):
        L, R = map(int, input().split())
        maxL = max(L, maxL)
        minR = min(R, minR)
    ans = minR -maxL + 1
    print(ans if ans>0 else 0)

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

N=int(input())
A=[int(x) for x in input().split()]
S=[[0]*60 for x in range(N+1)]

for i,a in enumerate(A):
  c=0
  while a>0:
    if a&1!=0:
      S[i+1][c]=1
    a>>=1
    c+=1
  for c in range(60):
    S[i+1][c]+=S[i][c]

s=0
for i,a in enumerate(A[:N-1]):
  c,i=0,i+1
  while c<60:
    s+=2**c*((S[N][c]-S[i][c]) if a&1==0 else (N-S[N][c]+S[i][c]-i))
    s%=10**9+7
    a>>=1
    c+=1

print(s)


### FIXED CODE ###

N=int(input())
A=[int(x) for x in input().split()]

s=0
for c in range(60):
  m=1<<c
  bc=len([1 for x in A if x&m])
  s+=bc*(N-bc)*m
  s%=10**9+7
  
print(s)
### BUGGY CODE ###

r, g, b, n = map(int, input().split())
s_rgb = sorted([r, g, b], reverse=True)
result = 0
for i in range(int(n / s_rgb[0]) + 1)[::-1]:
    for j in range(int((n - s_rgb[0] * i) / s_rgb[1]) + 1)[::-1]:
        if s_rgb[0] * i + s_rgb[1] * j > n:
            break
        for k in range(int((n - s_rgb[0] * i - s_rgb[1] * j) / s_rgb[2]) + 1)[::-1]:
            if s_rgb[0] * i + s_rgb[1] * j + s_rgb[2] * k == n:
                result += 1
                break
print(result)

### FIXED CODE ###

r, g, b, n = map(int, input().split())
s_rgb = sorted([r, g, b], reverse=True)
count = 0
for i in range(int(n / s_rgb[0]) + 1)[::-1]:
    for j in range(int((n - s_rgb[0] * i) / s_rgb[1]) + 1)[::-1]:
        tmp = n - s_rgb[0] * i - s_rgb[1] * j
        if (tmp >= 0 and tmp % s_rgb[2] == 0):
            count += 1
print(count)
### BUGGY CODE ###

import sys
import bisect
sys.setrecursionlimit(10 ** 7)

input = sys.stdin.readline

N, Q = map(int, input().split())
STX = []
for _ in range(N):
    s, t, x = map(int, input().split())
    STX.append((s, t, x))

PEOPLE = []
for i in range(Q):
    d = int(input())
    PEOPLE.append((d, i))

ans = [-1] * Q

STX.sort(key=lambda x: x[2])

for s, t, x in STX:
    if len(PEOPLE) == 0:
        break

    i = bisect.bisect_left(PEOPLE, (s - x, -1))
    j = bisect.bisect_left(PEOPLE, (t - x, -1))

    if i == j:
        continue

    use = [PEOPLE[x][1] for x in range(i, j)]

    for k in use:
        ans[k] = x

    del PEOPLE[i:j]


print("\n".join(map(str, ans)))


### FIXED CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

N,Q = map(int,input().split())
task = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  task.append((t-x,0,x)) # xで止まらなくなる
  task.append((s-x,1,x)) # xで止まる

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) # 止まる位置を答える
answer = [-1]*Q

task.sort()

# 引っかかってる場所の管理
se = set()
se_hp = [] # heapで最小値を先頭に保つ

# 小さい時刻から順に見ていく
for a,b,c in task:
  if not b: # b == 0
    se.remove(c)
  elif b&1: # b == 1
    se.add(c)
    heappush(se_hp,c)
  else: # b == 2
    while se_hp and se_hp[0] not in se:
      heappop(se_hp)
    answer[c] = se_hp[0] if se_hp else -1

print('\n'.join(map(str,answer)))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

MOD = 998244353  # type: int


class ModOperator:
    def __init__(self, MOD: int = 10 ** 9 + 7):
        self.MOD = MOD
        self.factorials = [1, 1]

    # x^n % MOD
    def mod_pow(self, x: int, n: int):
        bi = str(format(n, "b"))
        res = 1
        a = x
        for i in range(len(bi)):
            if n >> i & 1:
                res = (res * a) % self.MOD
            a = (a * a) % self.MOD
        return res
    
    # x! % MOD
    def mod_fact(self, x: int):
        if x < len(self.factorials):
            return self.factorials[x]
        else:
            res = self.factorials[-1]
            for i in range(len(self.factorials), x + 1):
                res = res * i % self.MOD
                self.factorials.append(res)
        return res % self.MOD

    # inverse of a number
    def mod_inv(self, x: int):
        return self.mod_pow(x, self.MOD - 2)
    
    # conmination nCk
    def mod_comb(self, n: int, k: int):
        numerator = self.mod_fact(n)
        denomintator1 = self.mod_fact(k)
        denomintator2 = self.mod_fact(n - k)
        denomintator = denomintator1 * denomintator2 % self.MOD
        return numerator * self.mod_inv(denomintator) % self.MOD

def main():
    N, M, K = map(int, input().split())

    op = ModOperator(MOD)
    sum = 0
    for i in range(K + 1):
        sum += M * op.mod_pow(M - 1, N - 1 - i) * op.mod_comb(N - 1, i)
    print(sum % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 998244353  # type: int


class ModOperator:
    def __init__(self, MOD: int = 10 ** 9 + 7):
        self.MOD = MOD
        self.factorials = [1, 1]

    # x^n % MOD
    def mod_pow(self, x: int, n: int):
        bi = str(format(n, "b"))
        res = 1
        a = x
        for i in range(len(bi)):
            if n >> i & 1:
                res = (res * a) % self.MOD
            a = (a * a) % self.MOD
        return res
    
    # x! % MOD
    def mod_fact(self, x: int):
        if x < len(self.factorials):
            return self.factorials[x]
        else:
            res = self.factorials[-1]
            for i in range(len(self.factorials), x + 1):
                res = res * i % self.MOD
                self.factorials.append(res)
        return res % self.MOD

    # inverse of a number
    def mod_inv(self, x: int):
        return self.mod_pow(x, self.MOD - 2)
    
    # conmination nCk
    def mod_comb(self, n: int, k: int):
        numerator = self.mod_fact(n)
        denomintator1 = self.mod_fact(k)
        denomintator2 = self.mod_fact(n - k)
        denomintator = denomintator1 * denomintator2 % self.MOD
        return numerator * self.mod_inv(denomintator) % self.MOD

def main():
    N, M, K = map(int, input().split())

    op = ModOperator(MOD)
    sum = 0
    for i in range(K + 1):
        sum += M * op.mod_pow(M - 1, N - 1 - i) * op.mod_comb(N - 1, i)
    print(sum % MOD)


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

N = int(input())
ans = 0
P = []
P.append(N)
for i in range(N-1):
    P.append(i+1)

for i in range(N):
    ans = ans + (P[i] % (i+1))

print(ans)

### FIXED CODE ###

N = int(input())
ans = N*(N-1)//2
print(ans)
### BUGGY CODE ###

N = int(input())
S = [input() for _ in range(N)]
 
T = sorted(set(S))
t = len(T)
l = [0] * t
 
for i in range(t):
  l[i] = S.count(T[i])
  
for i in range(t):
  if l[i] == max(l):
    print(T[i])

### FIXED CODE ###

from collections import Counter

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

S = Counter(S).most_common()
l = []
for i in S:
  if i[1] == S[0][1]: l.append(i[0])

l = sorted(l)
for i in l:
  print(i)
### BUGGY CODE ###

from collections import Counter
from functools import reduce
from operator import or_


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())
lcm = Counter()
for _ in range(N):
    factors = Counter(prime_factorize(int(input())))
    for key, value in factors.items():
        if lcm[key] < value:
            lcm[key] = value
ans = 1
for key, value in lcm.items():
    ans *= key ** value
print(ans)


### FIXED CODE ###

from fractions import gcd
from functools import reduce


def lcm(a, b):
    return (a * b) // gcd(a, b)


N = int(input())
T = list(int(input()) for _ in range(N))

print(reduce(lcm, T))
### BUGGY CODE ###

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

ans=0
for i in range(0,N-1):
    for j in range(i+1,N):
        ans+=A[i]^A[j]

print(ans%(10**9+7))
        


### FIXED CODE ###

#与えられる変数
N=int(input())
A=list(map(int,input().split()))
mod=10**9+7
ans=0

#Aの各要素の2進数表記した時のi番目の数について見ていく（Aの要素は最大でも2の60乗だから0≦i≦60）
#XORは2進数表記した時の2つの数が違うとき,その桁の数を1とする
#2進数表記したi番目の数が異なる場合の数がその桁での和として表現できる
#その場合の数は(0の個数)×(1の個数)で表現できる
for i in range(61):
    yes=sum([1 for a in A if (a>>i)&1])
    no=N-yes
    ans+=(1<<i)*yes*no

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

import math
N = int(input())

def search(n):
    global N
    for x in range(1, int(math.sqrt(n)) + 1):
        if n - x*x <= 0:
            return None
        for y in range(1, int(math.sqrt(n)) + 1):
            if n - x*x - y*y - x*y <= 0:
                break
            z = binarySearch(n, x, y)
            if z:
                return (x, y, z)


def binarySearch(n, x, y):
    global N
    right = -1
    left = N + 1
    while(abs(right - left) > 1):
        z = left + (right - left) // 2
        l = x*x + y*y + z*z + x*y + y*z + z*x
        if l == n:
            return z
        elif l < n:
            right = z
        else:
            left = z
        # print(right, left, z)
    return None

for n in range(1, N+1):
    ans = search(n)
    if ans == None:
        print(0)
        continue
    ans = len(set(ans))
    if ans == 1:
        print(1)
    elif ans == 2:
        print(3)
    else:
        print(6)

### FIXED CODE ###

N = int(input())
ans = [0]*10010

for x in range(1, 105):
    for y in range(1, 105):
        for z in range(1, 105):
            v = x*x + y*y + z*z + x*y + y*z + z*x
            if v <= 10005:
                ans[v] += 1
for i in range(1, N+1):
    print(ans[i])
### BUGGY CODE ###


n=input()
s=input()
ans=0

for ii in range(1000):
    v = str(ii).zfill(3)
    #print(v[0])
    s2=s
    #print("s=",v)
    for j in range(3):
        f=0
        for i in range(len(s2)):
            if s2[i] == v[j]:
                s2=s2[i+1:]
                f=1
                #print("aa",s2)
                break

        if f == 0 :
            break

    if f == 1:
        ans += 1
        #print(v)

print(ans)


### FIXED CODE ###

n=int(input())
s=input()
ans=0

for ii in range(1000):
    v = str(ii).zfill(3)
    start=0
    f=0
    
    for j in range(3):
        idx=s.find(v[j],start)
        if idx > -1:
            start = idx + 1
            f+=1
        else:
            break

    if f == 3:
        ans += 1

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


def sum_lr(l, r, cnt):
    cnt += 1
    lr = l + r
    if lr < 10:
        l = lr
        return l, cnt
    else:
        l = lr // 10
        r = lr % 10
        return sum_lr(l, r, cnt)

def dc_compression(d, c, ret, cnt):
    if c == 1:
        ret.append((d, 1))
        return ret, cnt
    
    if c % 2 == 1:
        ret.append((d, 1))
        c -= 1
    d, tmp_cnt = sum_lr(d, d, 0)
    c = c // 2
    cnt += tmp_cnt * c
    #print(d, c, ret, cnt)
    return dc_compression(d, c, ret, cnt)
    
    
    
        

M = int(input())

nums = []
l = 0
cnt = 0
for _ in range(M):
    d, c = map(int, input().split())
    tmp_nums, tmp_cnt= dc_compression(d,c,[], 0)
    nums += tmp_nums
    cnt += tmp_cnt
    
for d, c in nums:
    for _ in range(c):
        l, tmp_cnt = sum_lr(l,d,0)
        cnt += tmp_cnt

print(cnt-1)

### FIXED CODE ###

def sum_lr(l, r, cnt):
    cnt += 1
    lr = l + r
    if lr < 10:
        l = lr
        return l, cnt
    else:
        l = lr // 10
        r = lr % 10
        return sum_lr(l, r, cnt)

from collections import defaultdict
aaa = defaultdict(lambda:{})
for l in range(10):
    for r in range(10):
        aaa[l][r] = sum_lr(l,r,0)
        

def dc_compression(d, c, ret, cnt):
    if c == 1:
        ret.append((d, 1))
        return ret, cnt
    
    if c % 2 == 1:
        ret.append((d, 1))
        c -= 1
    d, tmp_cnt = aaa[d][d]
    c = c // 2
    cnt += tmp_cnt * c
    #print(d, c, ret, cnt)
    return dc_compression(d, c, ret, cnt)
    
    
    
        

M = int(input())

nums = []
l = 0
cnt = 0
import sys
input = sys.stdin.readline
for _ in range(M):
    d, c = map(int, input().split())
    tmp_nums, tmp_cnt= dc_compression(d,c,[], 0)
    for t,_ in tmp_nums:
        nums.append(t)
    
    cnt += tmp_cnt
    
#print(nums)    
    
for d in nums:
    l, tmp_cnt = aaa[l][d]
    cnt += tmp_cnt

print(cnt-1)
### BUGGY CODE ###

from pprint import pprint as pp
from functools import lru_cache
import math
"""
問題文
「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。
Q 個のクエリが与えられます。
クエリ i(1≦i≦Q) では奇数 li,ri が与えられるので、li≦x≦ri かつ 2017に似た数 となる奇数 x の個数を求めてください。
制約
    1≦Q≦105
    1≦li≦ri≦105
    li,ri は奇数
    入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q
l1 r1
:
lQ rQ
出力
i 行目 (1≦i≦Q) に、クエリ i の答えが x 個のとき、x を出力せよ。
"""
q=int(input())
lr_ary = []
for _ in range(q):
  lr_ary.append(list(map(int, input().split())))

@lru_cache(maxsize=400000)
def is_prime(n):
    if n == 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    sqrt_n = int(math.floor(math.sqrt(n)))
    for i in range(3, sqrt_n + 1, 2):
        if n % i == 0:
            return False
    return True

for l,r in lr_ary:
    ret=0
    for x in range(l,r+1,2):
        if is_prime(x) and is_prime((x+1)/2):
            ret += 1
    print(ret)

### FIXED CODE ###

from pprint import pprint as pp
from functools import lru_cache
import math
"""
問題文
「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。
Q 個のクエリが与えられます。
クエリ i(1≦i≦Q) では奇数 li,ri が与えられるので、li≦x≦ri かつ 2017に似た数 となる奇数 x の個数を求めてください。
制約
    1≦Q≦105
    1≦li≦ri≦105
    li,ri は奇数
    入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q
l1 r1
:
lQ rQ
出力
i 行目 (1≦i≦Q) に、クエリ i の答えが x 個のとき、x を出力せよ。
"""

prime = [True] * 100000
prime[0] = False
prime[1] = False
for i in range(2,len(prime)):
    if prime[i]:
        for j in range(i*2, len(prime), i):
            prime[j] = False
prime2017 = [0] * 100000
prime2017[0] = 0
prime2017[1] = 0
prime2017[2] = 0
ruiseki=0
for x in range(3,len(prime)):
    if prime[x] and prime[int((x+1)/2)]:
        ruiseki+=1
    prime2017[x] = ruiseki
q=int(input())
lr_ary = []
for _ in range(q):
    l,r=list(map(int, input().split()))
    print(prime2017[r]-prime2017[l-1])
### BUGGY CODE ###

from collections import deque
S = (input())
A = deque([0])
cnt = deque([0]*2019)
cnt.appendleft(1)
n = 0
t = 1
for i in reversed(S):
    x = int(i)
    n += x*t
    A.append(n%2019)
    cnt[n%2019] += 1
    t *= 10
cnt2 = [i*(i-1)//2 for i in cnt]
print(sum(cnt2))


### FIXED CODE ###

S = input()
cnt = [0]*2019
cnt[0] = 1
n = 0
t = 1
for i in reversed(S):
    n += int(i)*t
    n %= 2019
    cnt[n] += 1
    t *= 10
    t %= 2019
print(sum(i*(i-1)//2 for i in cnt))
### BUGGY CODE ###

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

edge_array = []

for _ in range(M):
    A, B, C = map(int, input().split())
    edge_array.append([A-1, B-1, C-P])
# print(edge_dic)

INF = 10 ** 10

ans_array = [-INF] * N

ans_array[0] = 0
last_ans_change = -1

for i in range(N*3):
    change_flag = 0
    for edge in edge_array:
        a, b, c = edge
        if ans_array[b] < ans_array[a] + c:
            ans_array[b] = ans_array[a] + c
            change_flag = 1
            if b == N - 1:
                last_ans_change = i
    if change_flag == 0:
        break

if last_ans_change >= N * 2:
    ans = -1
else:
    ans = max(0, ans_array[N-1])

print(ans)


### FIXED CODE ###

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

edge_dic = {}

for _ in range(M):
    A,B,C = map(int,input().split())
    if not A - 1 in edge_dic:
        edge_dic[A-1] = [[B-1,C-P]]
    else:
        edge_dic[A-1].append([B-1,C-P])

# print(edge_dic)

INF = 10 ** 10

ans_array = [-INF] * N
can_visit = [0] * N
ans_array[0] = 0
can_visit[0] = 1 
last_ans_change = -1

for i in range(N*2):
    change_flag = 0
    for key, value in edge_dic.items():
        if can_visit[key] == 0:
            continue
        for v in value:
            goal, cost = v
            if ans_array[goal] < ans_array[key] + cost:
                ans_array[goal] = ans_array[key] + cost
                if i >= N:
                    ans_array[goal] = INF
                can_visit[goal] = 1
                change_flag = 1
                if goal == N - 1:
                    last_ans_change = i
                    if i >= N:
                        print(-1)
                        exit()
    if change_flag == 0:
        break


ans = max(0,ans_array[N-1])

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

import sys
input = sys.stdin.readline

S=list(input()[:-1])
Q=int(input()[:-1])
f=0

for _ in range(Q):
    q=input().split()
    if int(q[0])==1:
        f = (f+1)%2
    if int(q[0])==2:
        if int(q[1])==1:
            if f==0:
                SS=[q[2]]
                SS.extend(S)
                S=SS
            else:
                S.append(q[2])
        else:
            if f==0:
                S.append(q[2])
            else:
                SS=[q[2]]
                SS.extend(S)
                S=SS
if f==0:
    print("".join(S))
else:
    print("".join(S[::-1]))

### FIXED CODE ###

import sys
input = sys.stdin.readline

S=list(input()[:-1])
Q=int(input()[:-1])
f=0
back=[]
forward=[]

for _ in range(Q):
    q=input().split()
    if int(q[0])==1:
        f = (f+1)%2
    if int(q[0])==2:
        if int(q[1])==1:
            if f==0:
                forward.append(q[2])
            else:
                back.append(q[2])
        else:
            if f==0:
                back.append(q[2])
            else:
                forward.append(q[2])

if f==0:
    print("".join(forward[::-1]+S+back))
else:
    print("".join((forward[::-1]+S+back)[::-1]))