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

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

    n, m, s, t = map(int, input().split())
    uvab = [list(map(int, input().split())) for _ in [0]*m]

    import numpy as np
    import scipy.sparse as sp
    data = [a for u, v, a, b in uvab]
    row = [u-1 for u, v, a, b in uvab]
    col = [v-1 for u, v, a, b in uvab]
    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int64)
    yen = sp.csgraph.dijkstra(matrix, indices=s-1, directed=False)

    data = [b for u, v, a, b in uvab]
    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int64)
    snk = sp.csgraph.dijkstra(matrix, indices=t-1, directed=False)

    cost = yen+snk
    m = cost[-1]
    for i in range(n-1, -1, -1):
        m = min(m, cost[i])
        cost[i] = m

    cost = 10**15-cost

    for i in cost:
        print(int(i))

main()


### FIXED CODE ###

n,m,s,t=map(int,input().split())
uvab=[list(map(int,input().split())) for _ in [0]*m]
g_yen=[[] for _ in [0]*n]
[g_yen[u-1].append([v-1,a]) for u,v,a,b in uvab]
[g_yen[v-1].append([u-1,a]) for u,v,a,b in uvab]

g_snk=[[] for _ in [0]*n]
[g_snk[u-1].append([v-1,b]) for u,v,a,b in uvab]
[g_snk[v-1].append([u-1,b]) for u,v,a,b in uvab]

import heapq
def dijkstra(g,start):
    inf=10**15
    dist=[inf for _ in [0]*n]
    h=[(0,start)]
    heapq.heapify(h)
    while h:
        d,i=heapq.heappop(h)
        if dist[i]==inf:
            dist[i]=d
            for x,y in g[i]:
                heapq.heappush(h,(d+y,x))
    return dist

yen=dijkstra(g_yen,s-1)
snk=dijkstra(g_snk,t-1)

cost=[yen[i]+snk[i] for i in range(n)]
m=cost[-1]
for i in range(n-1,-1,-1):
    m=min(m,cost[i])
    cost[i]=m
    
for i in cost:
    print(10**15-i)
### BUGGY CODE ###


n = int(input())
T = [0]*n
A = [0]*n
Tvote = [0]*n
Avote = [0]*n

for i in range(n):
    T[i], A[i] = map(int,input().split())

for k in range(n):
    if k == 0:
        Tvote[k] = T[k]
        Avote[k] = A[k]
    else:
        j = 1
        while Tvote[k-1]>j*T[k] or Avote[k-1]>j*A[k]:
            j += 1
        Tvote[k] = j*T[k]
        Avote[k] = j*A[k]

#print("---Tvote:{}".format(Tvote))
#print("---Avote:{}".format(Avote))
print(Tvote[n-1]+Avote[n-1])

### FIXED CODE ###

import math
n = int(input())
T = [0]*n
A = [0]*n
Tvote = [0]*n
Avote = [0]*n

for i in range(n):
    T[i], A[i] = map(int,input().split())

for k in range(n):
    if k == 0:
        Tvote[k] = T[k]
        Avote[k] = A[k]
    else:
        '''
        j = math.ceil(max(Tvote[k-1]/T[k],Avote[k-1]/A[k]))
        print(Tvote[k-1]/T[k])
        print(Avote[k-1]/A[k])
        print(max(Tvote[k-1]/T[k],Avote[k-1]/A[k]))
        print(j)
        print(Avote[k-1], A[k]*j)
        print(bool(Avote[k-1]<A[k]*j))
        print(bool(j>Avote[k-1]/A[k]))
        '''
        j = int(min(Tvote[k-1]//(-T[k]),Avote[k-1]//(-A[k])))*-1
        #普通に割り算やると誤差で死ぬ（floatがむずい。）
        # // は整数の除算で常に負の無限大方向に丸められる
        #一度も float になることがないはずなので、正しい計算結果が出る
        #https://paiza.hatenablog.com/entry/2017/08/01/Python3%E3%81%A7%E5%B7%A8%E5%A4%A7%E3%81%AA%E6%B5%AE%E5%8B%95%E5%B0%8F%E6%95%B0%E8%A8%88%E7%AE%97%E3%81%AE%E7%B5%90%E6%9E%9C%E3%81%8C%E5%A4%89%E3%81%A0%E3%81%A3%E3%81%9F%E3%81%AE%E3%81%A7%E7%90%86
        #正の無限大方向に丸めたいので-1かけてから計算して（丸めて）あとで-1かける。その際Av/AとTv/Tの比較も逆をとるのに注意
#        j = 1
#        while Tvote[k-1]>j*T[k] or Avote[k-1]>j*A[k]:
#            j += 1
#これは投票数が多すぎるのでTLE
        Tvote[k] = j*T[k]
        Avote[k] = j*A[k]
#    print("---input:{}:{}--vote{}:{}--diff{}".format(T[k],A[k],Tvote[k],Avote[k],bool(T[k]/A[k]==Tvote[k]/Avote[k])))   

#print("---Tvote:{}".format(Tvote))
#print("---Avote:{}".format(Avote))
#print('hoge')
#for i in range(n):
#    print(Tvote[i],Avote[i])
print(Tvote[n-1]+Avote[n-1])
### BUGGY CODE ###

#! python3
# coding:utf-8
 
def main():
    n = int(input())
    for i in range(1,n+1):
        cnt=0
    
        for x in range(1,100):
            for y in range(1,100):
                for z in range(1,100):
                    eq = x**2 + y**2 + z**2 + x*y + y*z + z*x
                    
                    if eq == i:
                        cnt+=1
        print(cnt)
if __name__ == "__main__":
    main() 

### FIXED CODE ###

#! python3
# coding:utf-8
 
def main():
    n = int(input())
    ans = [0 for _ in range(n)]
    for x in range(1,100):
        for y in range(1,100):
            for z in range(1,100):
                eq = x**2 + y**2 + z**2 + x*y + y*z + z*x
                if eq < n+1:
                    ans[eq-1]+=1
    for i in ans:   
        print(i)

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

import collections
INF = 10**18
h,w = map(int,input().split())
li = [list(input()) for i in range(h)]
koho = []
d = [[-1]*w for i in range(h)]
q = collections.deque([])
for i in range(h):
    for j in range(w):
        if li[i][j] == "#":
            d[i][j] = 0
            q.append([i,j])
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while q:
    p = q.popleft()
    y = p[0]
    x = p[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<w and 0<=ny<h:
            if d[ny][nx] == -1:
                q.append([ny,nx])
                d[ny][nx] = d[y][x] + 1
ans = -1
for i in range(h):
    for j in range(w):
        ans = max(ans,d[i][j])
print(ans)

### FIXED CODE ###

import collections
INF = 10**18
h,w = map(int,input().split())
li = [list(input()) for i in range(h)]
koho = []
d = [[-1]*w for i in range(h)]
q = collections.deque([])
for i in range(h):
    for j in range(w):
        if li[i][j] == "#":
            d[i][j] = 0
            q.append([i,j])
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while q:
    p = q.popleft()
    y = p[0]
    x = p[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<w and 0<=ny<h:
            if d[ny][nx] == -1:
                q.append([ny,nx])
                d[ny][nx] = d[y][x] + 1
ans = -1
for i in range(h):
    for j in range(w):
        ans = max(ans,d[i][j])
print(ans)
### BUGGY CODE ###

import numpy as np
from sys import stdin
input = stdin.readline
N = int(input())
A = list(map(int, input().split()))
number = np.zeros(N, dtype = int)
total = 0
for i in range(N):
  tmp = A.count(i + 1)
  total += tmp * (tmp -1) // 2
  number[i] = tmp
for i in range(N):
  number[i] = total - number[i] + 1
for j in A:
  print(number[j-1])


### FIXED CODE ###

import numpy as np
from sys import stdin
input = stdin.readline
N = int(input())
A = list(map(int, input().split()))
number = np.zeros(N, dtype = int)
total = 0

dic = {}
a = sorted(A)
now_key = a[0]
value = 1
dic[now_key] = 1
for i in range(1,N):
  if a[i] == now_key:
    value += 1
  else:
    dic[now_key] = value
    if value >= 2:
      total += value * (value-1) // 2
    now_key = a[i]
    value = 1
dic[now_key] = value
if value >= 2:
  total += value * (value-1)//2
for j in A:
  print(total - dic[j] + 1)
### BUGGY CODE ###

#!/usr/bin/env python3
 
 
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    a = input()
    Q = int(input())
    qs = [input().split() for _ in range(Q)]
    ans = a
    revcount = 0
    for q in qs:
        if len(q) == 1:
            revcount += 1
        else:
            if int(q[1]) == 1:
                if revcount % 2 == 0:
                    ans = q[2] + ans
                else:
                    ans = ans + q[2]
            else:
                if revcount % 2 == 0:
                    ans = ans + q[2]
                else:
                    ans = q[2] + ans
    if revcount % 2 == 1:
        ans = ans[::-1]
    print(ans)
    return
 
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
from collections import deque


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    a = input()
    Q = int(input())
    qs = [input().split() for _ in range(Q)]
    ans = deque(a)
    revcount = 0
    for q in qs:
        if len(q) == 1:
            revcount += 1
        else:
            if int(q[1]) == 1:
                if revcount % 2 == 0:
                    ans.appendleft(q[2])
                else:
                    ans.append(q[2])
            else:
                if revcount % 2 == 0:
                    ans.append(q[2])
                else:
                    ans.appendleft(q[2])
    if revcount % 2 == 1:
        ans.reverse()
    print(''.join(list(ans)))
    return


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

n = int(input())
h = list(map(int,input().split()))
count = 0
done = False
while done == False:
    for i in range(n):
        if h[i] >= 0:
            h[i] -= 1
        
        if i > 0 and h[i] < 0 and h[i-1] >= 0:
            count += 1

        if i == n-1 and h[i] >= 0:
            count += 1
    if max(h) == 0:
        done = True
print(count)


### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
count = 0
done = False
while done == False:
    for i in range(n):
        if h[i] >= 0:
            h[i] -= 1
        
        if i > 0 and h[i] < 0 and h[i-1] >= 0:
            count += 1

        if i == n-1 and h[i] >= 0:
            count += 1
    if max(h) <= 0:
        done = True
print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
  n, k = map(int, input().split())
  T = [[] for _ in range(n)]
  E = []
  for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)
    E.append((a, b))
  d = k//2
  def dfs(vs):
    dist = [-1]*n
    stack = []
    cnt = 0
    for v in vs:
      stack.append(v)
      dist[v] = 0
    while stack:
      v = stack.pop()
      for nv in T[v]:
        if dist[nv] == -1:
          dist[nv] = dist[v] + 1
          if dist[nv] > d:
            cnt += 1
            if cnt >= ans:
              return cnt
          stack.append(nv)
    return cnt
  ans = n
  if k%2 == 0:
    for i in range(n):
      ans = min(ans, dfs([i]))
  else:
    for l in E:
      ans = min(ans, dfs(l))
  print(ans)
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

n, k = map(int, input().split())
T = [[] for _ in range(n)]
E = []
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
  E.append((a, b))
d = k//2
def dfs(vs):
  dist = [-1]*n
  stack = []
  cnt = 0
  for v in vs:
    stack.append(v)
    dist[v] = 0
  while stack:
    v = stack.pop()
    for nv in T[v]:
      if dist[nv] == -1:
        dist[nv] = dist[v] + 1
        if dist[nv] > d:
          cnt += 1
        stack.append(nv)
  return cnt
ans = n
if k%2 == 0:
  for i in range(n):
    ans = min(ans, dfs([i]))
else:
  for l in E:
    ans = min(ans, dfs(l))
print(ans)
### BUGGY CODE ###

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

A=[0]
INPUT=map(int,input().split())
for i in INPUT:
    A.append(i)

dist=[1]
pre=[]
num=0
K_cp=K
while dist:
    tele=dist.pop()
    if tele in pre:
        flg=False
        break
    dist.append(A[tele])
    num+=1
    if num==K:
        flg=True
        break
    pre.append(tele)
    K_cp-=1

if not flg:
    start=pre.index(tele)
    cir=pre[start:]
    cir_len=len(cir)
    dist_num=(K_cp%cir_len)
    dist.append(cir[dist_num])
    flg=True

if flg:
    print(dist.pop())

### FIXED CODE ###

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

array=map(int,input().split())

A=list(array)
A.insert(0,0)

visit=0
root=[]
visited=1
once=0
while True:
    if visit & (0b1<<visited):
        break
    root.append(visited)
    visit|=0b1<<visited
    once+=1
    visited=A[visited]

roop=root[root.index(visited):]
if K<once:
    print(root[K])
else:
    order=K-once
    print(roop[order%len(roop)])
### BUGGY CODE ###

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

a = [int(input()) for i in range(n[2])]
kk = n[1]-n[2]


for i in range(n[0]):
    if kk+a.count(i+1) <= 0:
        print('No')
    else:
        print('Yes')


### FIXED CODE ###

import collections
n = list(map(int,input().split()))

a = [int(input()) for i in range(n[2])]
kk = n[1]-n[2]


counter = collections.Counter(a)

for i in range(n[0]):
    if kk+counter[i+1] <= 0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

import itertools

x,y,z,k=(int(i) for i in input().split())
#print(x,y,z,k)
a=list(int(i) for i in input().split())
#a.sort(reverse=True)
b=list(int(i) for i in input().split())
#b.sort(reverse=True)
c=list(int(i) for i in input().split())
#c.sort(reverse=True)
#print(a,b,c)

#a=[int(i) for i in range(1000,-1,-1)]
#b=[int(i) for i in range(1000,-1,-1)]
#c=[int(i) for i in range(1000,-1,-1)]
x=list(itertools.product(a,b))
for i in range(len(x)):
  x[i]=x[i][0]+x[i][1]
x.sort(reverse=True)
if len(x) > 3000:
  x=x[:3000]
#print(len(x))
x=list(itertools.product(x,c))
#print(x)
for i in range(len(x)):
  x[i]=x[i][0]+x[i][1]
x.sort(reverse=True)

for i in range(k):
  print(x[i])


### FIXED CODE ###

#import itertools

x,y,z,k=(int(i) for i in input().split())
#print(x,y,z,k)
a=list(int(i) for i in input().split())
a.sort(reverse=True)
b=list(int(i) for i in input().split())
b.sort(reverse=True)
c=list(int(i) for i in input().split())
c.sort(reverse=True)
#print(a,b,c)

#k=3000
#a=[int(i) for i in range(1000)]
#b=[int(i) for i in range(1000)]
#c=[int(i) for i in range(1000)]
x=[]
for h in range(len(a)):
    for i in range(len(b)):
        if (h+1)*(i+1) <=k:
            for j in range(len(c)):
                if (h+1)*(i+1)*(j+1) <=k:
                    x.append(a[h]+b[i]+c[j])

x.sort(reverse=True)
for i in range(k):
  print(x[i])
### BUGGY CODE ###

S = input()
K = int(input())

d = {}
for i in range(len(S)):
    for j in range(i+1,len(S)+1):
        s = S[i:j]
        if s in d.keys():
            pass
        else:
            d[s] = 0

d = sorted(d.keys())
print(d[K-1])

### FIXED CODE ###

S = input()
K = int(input())

d = {}
for i in range(len(S)):
    for j in range(i+1,i+K+1):
        s = S[i:j]
        if s in d.keys():
            pass
        else:
            d[s] = 0

d = sorted(d.keys())
print(d[K-1])
### BUGGY CODE ###

from queue import deque


def dijkstra(s, d):
    queue = deque([(0, s)])
    paint = set()
    while queue:
        cost, v = queue.popleft()
        if cost > d:
            break
        paint.add(v)
        queue.extend((cost + 1, u) for u in links[v] if u not in paint)
    return paint


n, m = map(int, input().split())
links = [None] + [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    links[a].add(b)
    links[b].add(a)

q = int(input())
queries = [map(int, input().split()) for _ in range(q)]
painted = set()
colors = [0] * (n + 1)
while queries:
    v, d, c = queries.pop()
    paint = dijkstra(v, d) - painted
    for i in paint:
        colors[i] = c
    painted |= paint

for c in colors[1:]:
    print(c)


### FIXED CODE ###

from queue import deque


def paint(s, d, c):
    queue = deque([(d, s)])
    while queue:
        remains, v = queue.popleft()
        if painted[v] >= remains:
            continue
        if colors[v] == 0:
            colors[v] = c
        painted[v] = remains
        if remains:
            queue.extend((remains - 1, u) for u in links[v])


n, m = map(int, input().split())
links = [None] + [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    links[a].add(b)
    links[b].add(a)

q = int(input())
queries = [map(int, input().split()) for _ in range(q)]
colors = [0] * (n + 1)
painted = [-1] * (n + 1)
while queries:
    paint(*queries.pop())

for c in colors[1:]:
    print(c)
### BUGGY CODE ###

# coding: utf-8
# Here your code !
a=input()
b=a.split(" ")
N=int(b[0])
M=int(b[1])
in2=[]
out2=[]
for i in range(M):
    c=input()
    d=c.split(" ")
    in1=int(d[0])
    out=int(d[1])
    if in1==1:
        in2.append(str(out))
    elif out==N:
        out2.append(str(in1))
#print(in2)
#print(out2)
len_in2=len(in2)
for q in range(len_in2):
    if in2[q] in out2:
        print("POSSIBLE")
        break
    elif q+1==len_in2:
        print("IMPOSSIBLE")
    else:
        continue

### FIXED CODE ###

a=input()
b=a.split(" ")
N=int(b[0])
M=int(b[1])
in2=[]
out2=[]
for i in range(M):
    c=input()
    d=c.split(" ")
    in1=int(d[0])
    out=int(d[1])
    if in1==1:
        in2.append(str(out))
    elif out==N:
        out2.append(str(in1))
        
in2_set=set(in2)
out2_set=set(out2)
matched_list=list(in2_set & out2_set)
#print(matched_list)
if len(matched_list)==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")
### BUGGY CODE ###

N = int(input())
list = [int(input()) for i in range(N)]
if sorted(list)[-1] == sorted(list)[-2]:
    list2 = [max(list) for i in range(N)]
    print("\n".join(map(str,list2)))
else:
    list2 = [max(list) for i in range(list.index(max(list)))]
    list2.append(sorted(list)[-2])
    list3 = [max(list) for j in range(list.index(max(list))+1,N)]
    list2.extend(list3)
    print("\n".join(map(str,list2)))

### FIXED CODE ###

N = int(input())
list = [int(input()) for i in range(N)]
if sorted(list)[-1] == sorted(list)[-2]:
    list2 = [max(list)]*N
    print("\n".join(map(str,list2)))
else:
    list2 = [max(list)]*list.index(max(list))
    list2.append(sorted(list)[-2])
    list3 = [max(list)]*(N-list.index(max(list))-1)
    list2.extend(list3)
    print("\n".join(map(str,list2)))
### BUGGY CODE ###

import sys
import numpy as np

N, M = input().split()

N = int(N)
M = int(M)

cnt = 0

NM = np.zeros([N])
B = np.zeros([N])

for i in range(M):
    A = input().split()
    B[int(A[0])-1:int(A[1])] = 1
    NM += B
    B = np.zeros([N])


print(np.sum(NM==M))


### FIXED CODE ###

N, M = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]

left = 1
right = N

for l, r in LR:
    left = max(left, l)
    right = min(right, r)

ans = right - left

print(ans + 1 if ans >= 0 else 0)
### BUGGY CODE ###

# coding:utf-8

INF = float('inf')


def inpl(): return list(map(int, input().split()))


def binary_search(A, x):
    low = 0
    high = len(A) - 1
    mid = (low + high) // 2

    while low <= high:
        if A[mid] == x:
            break
        elif A[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
        mid = (low + high) // 2

    if mid < 0:
        return 0
    else:
        return mid


N = int(input())

A = inpl()
B = A[:]

# 累積和
for i in range(1, N):
    B[i] = B[i] + B[i - 1]

ans = INF
for mid in range(2, N - 1):
    L = B[:mid]
    R = B[mid:]
    R = [R[i] - L[-1] for i in range(len(R))]
    # print(L)
    # print(R)

    sum_list = []
    for li in [L, R]:
        if len(li) == 2:  # R, Lの要素数が2の場合の分け方は1通り
            sum_list.append(li[0])
            sum_list.append(li[1] - li[0])
            continue

        # 真ん中の切れ込みが固定されている時のRとLの切れ込みの決定
        mid = binary_search(li, li[-1] // 2)

        diff1 = abs(2 * li[mid] - li[-1])
        diff2 = abs(2 * li[mid + 1] - li[-1])

        if diff1 < diff2:
            sum_list.append(li[mid])
            sum_list.append(li[-1] - li[mid])
        else:
            sum_list.append(li[mid + 1])
            sum_list.append(li[-1] - li[mid + 1])

    ans = min(ans, max(sum_list) - min(sum_list))

print(ans)

### FIXED CODE ###

# coding:utf-8

INF = float('inf')


def inpl(): return list(map(int, input().split()))


N = int(input())

A = inpl()
B = A[:]

# 累積和
for i in range(1, N):
    B[i] = B[i] + B[i - 1]

ans = INF
mid_l = 0
mid_r = 2
t = B[-1]
for mid in range(1, N - 1):
    while mid_l < mid and abs(2 * B[mid_l] - B[mid]) >= abs(2 * B[mid_l + 1] - B[mid]):
        mid_l += 1
    while mid_r < N - 1 and abs(2 * B[mid_r] - B[mid] - t) >= abs(2 * B[mid_r + 1] - B[mid] - t):
        mid_r += 1

    p = B[mid_l]
    q = B[mid] - p
    r = B[mid_r] - p - q
    s = t - r - p - q

    ans = min(ans, max(p, q, r, s) - min(p, q, r, s))

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

import math
K = int(input())
ans = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            ans += math.gcd(math.gcd(a,b),c)
print(ans)

### FIXED CODE ###

import math
K = int(input())
ans = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            ans += math.gcd(math.gcd(a,b),c)
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3

s = input()
head = 1 #1:forward, -1: reverse

q = int(input())

for i in range(q):
    ql = input()
    if ql[0] == '1':
        head *= -1
    elif ql[0] == '2':
        (op, f, c) = ql.split()
        ht = 1
        if f == '1':
            ht = head
        else:
            #f == '2':
            ht = head * -1

        if ht == 1:
            s = c + s
        else:
            s = s + c


if head == 1:
    print(s)
else:
    print(s[::-1])


### FIXED CODE ###

#!/usr/bin/python3
from collections import deque

s = input()
head = 1 #1:forward, -1: reverse

q = int(input())
sl = [ s[i] for i in range(len(s)) ]
sq = deque(sl)


for i in range(q):
    ql = input()
    if ql[0] == '1':
        head *= -1
    elif ql[0] == '2':
        (op, f, c) = ql.split()
        ht = 1
        if f == '1':
            ht = head
        else:
            #f == '2':
            ht = head * -1

        if ht == 1:
            sq.appendleft(c)
        else:
            sq.append(c)


if head == 1:
    print(''.join(sq))
else:
    print(''.join(reversed(sq)))
### BUGGY CODE ###

if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    a.sort(reverse=True)
    ans = 0
    dict = {}
    for i in a:
        if len(dict) > 0:
            ans+=max(dict)
            if dict[max(dict)] ==1:
                dict.pop(max(dict))
            else:
                dict[max(dict)]-=1
            if i in dict:
                dict[i]+=2
            else:
                dict[i]=2


        else:
            dict[i]=1


    print(ans)



### FIXED CODE ###

if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    a.sort(reverse=True)
    ans = 0
    count = 0
    for i in a:
        if ans ==0:
            ans+=i
            count+=1
        else:
            if count == n-2:
                ans+=i
                break
            elif count == n-3:
                ans+=i*2
                break
            else:
                ans+=i*2
                count+=2

    if n ==2:
        ans= max(a)

    print(ans)