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

import itertools
n,m,r=map(int,input().split())
rx=[int(i) for i in input().split()]
inf=100000000
wf=[[inf]*n for i in range(n)]
for i in range(n):
    wf[i][i]=0

for i in range(m):
    a,b,c=map(int,input().split())
    wf[a-1][b-1]=c
    wf[b-1][a-1]=c

for k in range(n):
    for i in range(n):
        for j in range(n):
            if wf[i][j]>wf[i][k]+wf[k][j]:
                wf[i][j]=wf[i][k]+wf[k][j]
cnt=0
l=list(itertools.permutations([i for i in range(r)]))
cnt=inf
for i in l:
    cnt_sub=0
    for j in range(r-1):
        cnt_sub+=wf[rx[i[j]]-1][rx[i[j+1]]-1]
    cnt=min(cnt,cnt_sub)
print(cnt)


### FIXED CODE ###

import itertools
n,m,r=map(int,input().split())
rx=[int(i) for i in input().split()]
inf=100000000
wf=[[inf]*n for i in range(n)]
for i in range(n):
    wf[i][i]=0

for i in range(m):
    a,b,c=map(int,input().split())
    wf[a-1][b-1]=c
    wf[b-1][a-1]=c

for k in range(n):
    for i in range(n):
        for j in range(n):
            if wf[i][j]>wf[i][k]+wf[k][j]:
                wf[i][j]=wf[i][k]+wf[k][j]
cnt=0
l=list(itertools.permutations([i for i in range(r)]))
cnt=inf
for i in l:
    cnt_sub=0
    for j in range(r-1):
        cnt_sub+=wf[rx[i[j]]-1][rx[i[j+1]]-1]
    cnt=min(cnt,cnt_sub)
print(cnt)
### BUGGY CODE ###

import collections
import math

def combinations_count(n, r):
    if n < 2:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
a_list = list(map(int, input().split()))
a_col = collections.Counter(a_list)
c_dic = {}
sm = 0
for c in a_col:
    sm += combinations_count(a_col[c], 2)

for a in a_list:
    if a in c_dic:
        print(c_dic[a])
    else:
        ans = sm - combinations_count(a_col[a], 2) + combinations_count(a_col[a] - 1, 2)
        print(ans)
        c_dic[a] = ans

### FIXED CODE ###

import collections
import math

def combinations_count(n, r):
    if n < 2:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
a_list = list(map(int, input().split()))
a_col = collections.Counter(a_list)
c_dic = {}
sm = sum([c * (c - 1) for c in a_col.values()]) // 2
for a in a_list:
    if a in c_dic:
        print(c_dic[a])
    else:
        ans = sm - combinations_count(a_col[a], 2) + combinations_count(a_col[a] - 1, 2)
        print(ans)
        c_dic[a] = ans
### BUGGY CODE ###

H,W = map(int,input().rstrip().split())
M = [[False for _ in range(W)]for _ in range(H)]
que = []
k = [0,0,0]
for i in range(H):
    S = input()
    for i2 in range(W):
        if S[i2] == "#":
            M[i][i2] = True
            que.append([i,i2,0])
while len(que) != 0:
    k = que[0]
    if(k[0] + 1 != H and M[k[0] + 1][k[1]] == False):
        M[k[0] + 1][k[1]] = True
        que.append([k[0] + 1,k[1],k[2] + 1])
    if(k[0] - 1 != -1 and M[k[0] - 1][k[1]] == False):
        M[k[0] - 1][k[1]] = True
        que.append([k[0] - 1,k[1],k[2] + 1])
    if(k[1] + 1 != W and M[k[0]][k[1] + 1] == False):
        M[k[0]][k[1] + 1] = True
        que.append([k[0],k[1] + 1,k[2] + 1])
    if(k[1] - 1 != -1 and M[k[0]][k[1] - 1] == False):
        M[k[0]][k[1] - 1] = True
        que.append([k[0],k[1] - 1,k[2] + 1])
    que.pop(0)
print(k[2])

### FIXED CODE ###

H,W = map(int,input().rstrip().split())
M = [[False for _ in range(W)]for _ in range(H)]
que = []
k = [0,0,0]
counter = 0
for i in range(H):
    S = input()
    for i2 in range(W):
        if S[i2] == "#":
            M[i][i2] = True
            que.append([i,i2,0])
while counter != H * W:
    k = que[counter]
    if(k[0] + 1 != H and M[k[0] + 1][k[1]] == False):
        M[k[0] + 1][k[1]] = True
        que.append([k[0] + 1,k[1],k[2] + 1])
    if(k[0] - 1 != -1 and M[k[0] - 1][k[1]] == False):
        M[k[0] - 1][k[1]] = True
        que.append([k[0] - 1,k[1],k[2] + 1])
    if(k[1] + 1 != W and M[k[0]][k[1] + 1] == False):
        M[k[0]][k[1] + 1] = True
        que.append([k[0],k[1] + 1,k[2] + 1])
    if(k[1] - 1 != -1 and M[k[0]][k[1] - 1] == False):
        M[k[0]][k[1] - 1] = True
        que.append([k[0],k[1] - 1,k[2] + 1])
    counter += 1
print(k[2])
### BUGGY CODE ###

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

a = 1
for i in list_input:
    a *= i

if a > pow(10, 18):
    print(-1)
else:
    print(a)


### FIXED CODE ###

import sys

n = int(input())
list_input = list(map(int, sys.stdin.readline().strip().split()))

if 0 in list_input:
    print(0)
    exit()

a = 1
for i in list_input:
    a *= i
    if a > pow(10, 18):
        break


if a > pow(10, 18):
    print(-1)
else:
    print(a)
### BUGGY CODE ###

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

count = 0
for i in range(n-1):
  for j in range(i+1,n):
    count += (a[i] ^ a[j])
    count %= 10 ** 9 + 7
  
print(count)

### FIXED CODE ###

MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
 
one_count = [0] * 61
for v in a:
  count = 0
  while v != 0:
    if v % 2 == 1:
      one_count[count] += 1
      
    count += 1
    v //= 2
  
 
ans = 0
for i in range(len(one_count)):
  ans += (one_count[i] * (n - one_count[i]) * (2 ** i))
  ans %= MOD
  
print(ans)
### BUGGY CODE ###

from copy import deepcopy
def solve():
  R, C, K = map(int, input().split())
  item = [[0]*C for _ in range(R)]
  for i in range(K):
    r,c,v = map(int, input().split())
    item[r-1][c-1] = v
  dp1 = [[0]*4 for _ in range(C+1)]
  dp2 = [[0]*4 for _ in range(C+1)]
  for i in range(1,R+1):
    for j in range(1,C+1):
      for k in range(4): #横から取らない
        dp2[j][k] = dp2[j-1][k]
      #上から取らない
      dp2[j][0] = max(dp2[j][0],max(dp1[j]))
      if item[i-1][j-1]>0:
        #上からとる
        dp2[j][1] = max(dp2[j][1],max(dp1[j])+item[i-1][j-1])
        for k in range(1,4): #横から取る
          dp2[j][k] = max(dp2[j][k],dp2[j-1][k-1]+item[i-1][j-1])
      dp1 = deepcopy(dp2)
  ans = max(dp2[-1])
  return ans
print(solve())

### FIXED CODE ###

import sys
input = sys.stdin.readline
def solve():
  R, C, K = map(int, input().split())
  item = [[0]*C for _ in range(R)]
  for i in range(K):
    r,c,v = map(int, input().split())
    item[r-1][c-1] = v
  dp = [[[0]*(C+1) for _ in range(R+1)] for _ in range(4)]
  for i in range(1,R+1):
    for j in range(1,C+1):
      for k in range(4): #横から取らない
        dp[k][i][j] = dp[k][i][j-1]
      #上から取らない
      dp[0][i][j] = max(dp[0][i][j],dp[-1][i-1][j])
      if item[i-1][j-1]>0:
        #上からとる
        dp[1][i][j] = max(dp[1][i][j],dp[-1][i-1][j]+item[i-1][j-1])
        for k in range(1,4): #横から取る
          dp[k][i][j] = max(dp[k][i][j],dp[k-1][i][j-1]+item[i-1][j-1])
      for k in range(1,4):
        dp[k][i][j] = max(dp[k-1][i][j],dp[k][i][j])
  ans = 0
  for k in range(4):
    ans = max(ans,dp[k][-1][-1])
  return ans
print(solve())
### BUGGY CODE ###

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

def dp(cost):
    for x in range(1,N):
        for k in range(1,K+1):
            if x - k >= 0 :
                cost[x] = min( cost[x-k] + abs( h[x] - h[x-k] ) , cost[x] )
            else:
                break
    return 0

def solve():
    cost = [float('inf')] * N
    cost[0] = 0
    dp(cost)
    print(cost[N-1])
    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

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

def dp(cost):
    for x in range(1,N):
        for k in range(max(x-K,0),x):
            cost[x] = min(cost[x] , cost[k] + abs( h[x] - h[k] ) )
        # cost[x] =  min( [ cost[k] + abs( h[x] - h[k] ) for k in range(max(x-K,0),x) ] ) 
    return 0

def solve():
    cost = [float('inf')] * N
    cost[0] = 0
    dp(cost)
    print(cost[N-1])
    return 0

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

def binary_search(cards,n,number):
    low=0
    high=len(cards)-1

    while high-low>1:
        mid=(low+high)//2
        base=cards[mid]
        if base==number:
            for i in range(n):
                cards.insert(mid,number)
            return cards,mid
        if base<number:
            low=mid
        else:
            high=mid

    if cards[high]==cards[low]:
        if number>cards[high]:
            for i in range(n):
                cards.insert(high+1, number)
        else:
            for i in range(n):
                cards.insert(low, number)
    else:
        for i in range(n):
            cards.insert(high,number)
    return cards,mid

#1 3 5 7 9 11 <=8
#1 3 [5] 7 9 11 <= 8
#1 3 (5) 7 9 (11) <=8
#1 3 5 [7] 9 11 <= 8
#1 3 5 (7) 9 (11) <= 8
#1 3 5 7 [9] 11 <= 8
#1 3 5 (7) (9) 11
#1 3 5 [7] 9 11 <=8
#1 3 5 (7)

def main():
    inp1=list(map(lambda x:int(x),input().split()))
    cards=list(map(lambda x:int(x),input().split()))
    N=inp1[0]
    M=inp1[1]
    B=[]
    C=[]
    for i in range(M):
        changes=list(map(lambda x:int(x),input().split()))
        B.append(changes[0])
        C.append(changes[1])

    cb=zip(C,B)
    cb=sorted(cb,reverse=True)
    C,B=zip(*cb)

    hand=[]
    for i in range(M):
        hand.extend([C[i] for j in range(B[i])])

    cards.sort()

    pointer=0
    for i in range(N):
        if pointer>=len(hand):
            break
        if hand[pointer]>cards[i]:
            cards[i]=hand[pointer]
            pointer+=1
        else:
            break

    print(sum(cards))

if __name__=="__main__":
    main()

### FIXED CODE ###

from heapq import heappush,heappop

def main():
    inp1=list(map(lambda x:int(x),input().split()))
    cards=list(map(lambda x:int(x),input().split()))
    cards_heap=[]
    for i in cards:
        heappush(cards_heap,i)

    N=inp1[0]
    M=inp1[1]
    B=[]
    C=[]
    for i in range(M):
        changes=list(map(lambda x:int(x),input().split()))
        B.append(changes[0])
        C.append(changes[1])

    cb=zip(C,B)
    cb=sorted(cb,reverse=True)


    for C,B in cb:
        for _ in range(B):
            a=heappop(cards_heap)
            if C>a:
                heappush(cards_heap,C)
            else:
                heappush(cards_heap,a)
                break

    print(sum(cards_heap))

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

def check_l3(l):
    
    if l[0] < l[1] + l[2] and l[1] < l[0] + l[2] and l[2] < l[1] + l[0]:
        return 1
    else:
        return 0
    



N = int(input())

L = list(map(int , input().split(" ")))

L3 = []

i = 0
j = i + 1
k = j + 1

for i in range(N-2):
    for j in range(j,N-1):
        
        for k in range(k,N):
            l3 = [L[i],L[j],L[k]]
            if l3 not in L3:
                L3.append(l3)
            k = k + 1

        j = j + 1
        k = j + 1
    i = i + 1
    j = i + 1
    k = j + 1

# print(L3) #!!!!!!!

result = 0
for i in range(len(L3)):
    result += check_l3(L3[i])
print(result)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
# 昇順ソート 
l.sort()
# バイセクションサーチ（二分探索法）のライブラリbisect 
from bisect import bisect_left
# 満たされるべき条件は、a<b<c  a+b>c 
ans = 0
for i in range(n):
  for j in range(i+1, n):
    # ソートした最初の2つの数を足す
    t = l[i]+l[j]
    # bisect_left(対象リスト, 探したい値, lo=左側のインデックス, hi=右側のインデックス)
    # 2つの数の和と同じ数が、リストの何番目に入るかが求められる
    idx = bisect_left(l, t)
    # idxは、a+b=cになる境目
    # idx-(j+1)は a+b>c の条件をみたす、数がいくつあるかを計算している。
    ans += max(0, idx-j-1)
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
 
n,w=map(int,input().split())
dp=[0]*(w+1)
c,p=map(int,input().split())
dp[c]=p
 
def ans(n,w):
  for _ in range(1,n):
    c,p=map(int,input().split())
    for j in range(w,c-1,-1):
      if dp[j]<dp[j-c]+p:
        dp[j]=dp[j-c]+p
  return max(dp)
print(ans(n,w))

### FIXED CODE ###

import sys
input=sys.stdin.readline
 
n,w=map(int,input().split())
dp=[0]*(w+1)
 
def ans(n,w):
  for _ in range(n):
    c,p=map(int,input().split())
    for j in range(w,c-1,-1):
      tmp=dp[j-c]+p
      if dp[j]<tmp:
        dp[j]=tmp
  return max(dp)
print(ans(n,w))
### BUGGY CODE ###

N = int(input())
S = input()
count = 0

#for i in range(0,N-2):
#    for j in range(i+1,N-1):
#        if S[i] != S[j]:
#            for k in range(j+1,N):
#                if j-i != k-j:
#                    if S[j] != S[k] and S[k] != S[i]:
#                        count += 1
#print(count)

r = list()
g = list()
b = list()

for i in range(N):
    if S[i] == "R":
        r.append(i)
    elif S[i] == "G":
        g.append(i)
    else:
        b.append(i)

bb = len(b)
gg = len(g)
rr = len(r)

for i in range(bb):
    for j in range(gg):
        for k in range(rr):
            if abs(r[k] - g[j]) == abs(g[j] - b[i]) or abs(g[j] - b[i]) == abs(b[i] - r[k]) or abs(b[i] - r[k]) == abs(r[k] - g[j]):
                count += 1
sum = len(r) * len(g) * len(b) - count
print(sum)


### FIXED CODE ###

N = int(input())
S = "A"
S += input()
r = 0
g = 0
b = 0
k = 0
for i in range(1, N+1):
    if S[i] == "R":
        r += 1
    elif S[i] == "G":
        g += 1
    else:
        b += 1

sum = r * g * b
for i in range(1, N-1):
    for j in range(i+1,N):
        k = 2*j - i
        if k <= N:
            if S[j] != S[i] and S[k] != S[j] and S[i] != S[k]:
                sum -= 1

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

import math
k = int(input())
ans = 0

for i in range(1,k+1):
    for j in range(1,k+1):
        for m in range(1,k+1):
           
            ans +=math.gcd(math.gcd(i,j),m)

print(ans)

### FIXED CODE ###

import math
k = int(input())
ans = 0

for i in range(1,k+1):
    for j in range(1,k+1):
        for m in range(1,k+1):
           
            ans +=math.gcd(math.gcd(i,j),m)

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

from collections import Counter
from operator import mul
from functools import reduce

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


def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

for k in range(N):
  sum_k = 0
  temp_c = c.copy()
  temp_c[A[k]] -= 1
  for v in temp_c.values():
    if v > 1:
      sum_k += cmb(v,2)
  print(int(sum_k))

### FIXED CODE ###

from collections import Counter
from scipy.misc import comb

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

num = 0
for v in c.values():
  if v > 1:
      num += comb(v, 2,exact=True)
for k in range(N):
  print(int(num - (c[A[k]]-1)))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, K: int, p: "List[int]"):
    max = -1
    arr_max = []
    for i, v in enumerate(p):
        arr = p[i:i+K]
        m = sum(arr)
        if m > max:
            max = m
            arr_max = arr
    print(sum([calc(i) for i in arr_max]))


def calc(n: int):
    return sum(range(1, n+1)) / n


# 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():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    p = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, p)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, K: int, p: "List[int]"):
    M = m = sum(p[:K])
    for i in range(N-K):
        m = m - p[i] + p[i + K]
        M = max(M, m)
    print((1*K+M)/2)



# 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():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    p = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, p)


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

n,k = map(int,input().split())
a = [0]+list(map(int,input().split()))

know = []
now = 1
cnt = 0
while 1:
    if now in know: break
    know.append(now)
    now = a[now]

start = a[know[-1]]
for i,num in enumerate(know):
    if num == start: loop = know[i:] ; break

#print(know,start,loop)

cnt = len(loop)
if k>=len(know):
    k -= len(know)
    ans = loop[k%cnt]

else:
    ans = know[k]

print(ans)


### FIXED CODE ###

n,k = map(int,input().split())
a = [0]+list(map(int,input().split()))

def bin(arr,val):
    left,right = 0,len(arr)-1
    while left<=right:
        mid = (left+right)//2
        if arr[mid]==val: return 1
        elif arr[mid]<val: left = mid + 1
        else: right = mid - 1
    return 0

know = []
now = 1
while not bin(know, now):
    know.append(now)
    now = a[now]

start = a[know[-1]]
for i,num in enumerate(know):
    if num == start: loop = know[i:] ; break

#print(know,start,loop)

if k < len(know):
    ans = know[k]
else:
    k -= len(know)
    ans = loop[k%len(loop)]

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

n, k = map(int, input().split())
while n > abs(n - k):
    n = abs(n - k)

print(n)

### FIXED CODE ###

n, k = map(int, input().split())
print(min(n%k, k-n%k))
### BUGGY CODE ###

N = int(input())
A = [int(n) for n in 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 = [int(i) for i in input().split()]
mod = 10**9 + 7
sum_A = sum(A)
ans = 0
for i in A:
  ans += i * (sum_A := sum_A - i) % mod
  
print(ans % mod)
### BUGGY CODE ###

N, M = map(int, input().split())
check_1 = []
check_N = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        check_1.append(b)
    if b == N:
        check_N.append(a)
        
flag = False
for i in sorted(set(check_1)):
    if i in check_N:
        flag = True
        break
        
if flag:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

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

check_1 = []
check_N = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        check_1.append(b)
    if b == N:
        check_N.append(a)
        
if len(list(set(check_1) & set(check_N))) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

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

result=0

for j in range(N-1):
    for k in range(j+A[j]+1,N):
        if k-j==A[k]+A[j]:
            result +=1

print(result)

### FIXED CODE ###

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

result=0

D={}

for j in range(N):
    if j+A[j] in D:
        D[j+A[j]] += 1
    else:
        D[j+A[j]]=1

for j in range(N):
    if j-A[j] in D:
        result += D[j-A[j]]

print(result)
### BUGGY CODE ###

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

s = 1
for x in a:
  s *= x
if s > 1000000000000000000:
  print(-1)
else:
  print(s)


### FIXED CODE ###

import sys

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

if 0 in a:
  print(0)
  sys.exit(0)

s = 1
for x in a:
  s *= x
  if s > 1000000000000000000:
    break
if s > 1000000000000000000:
  print(-1)
else:
  print(s)
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
    Query = list(map(str, input().split()))
    if Query[0] == "1":
        S = S[::-1]
    elif Query[1] == "1":
        S = Query[2] + S
    else:
        S = S + Query[2]
print(S)


### FIXED CODE ###

import collections
S = input()
Q = int(input())
q = collections.deque()
q.append(S)
inversion = True
for i in range(Q):
    Query = list(map(str, input().split()))
    if Query[0] == "1":
        inversion = not(inversion)
    elif Query[1] == "1":
        if inversion:
            q.appendleft(Query[2])
        else:
            q.append(Query[2])
    else:
        if inversion:
            q.append(Query[2])
        else:
            q.appendleft(Query[2])

if inversion:
    print("".join(q))
else:
    print("".join(q)[::-1])
### BUGGY CODE ###

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

dp = [0] * n

def func(x):
    return sum(range(x+1)) / x

for i in range(n):
    if i - k >= 0:
        dp[i] = dp[i - 1] - func(P[i - k]) + func(P[i])
    else:
        dp[i] = sum([func(p) for p in P[:i + 1]])

print(max(dp))

### FIXED CODE ###

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

dp = [0] * n
m = {}

def func(x):
    return m.get(x, sum(range(x+1)) / x)
    #return sum(range(x+1)) / x

for i in range(n):
    if i - k >= 0:
        dp[i] = dp[i - 1] - func(P[i - k]) + func(P[i])
    else:
        dp[i] += func(P[i]) + dp[i-1]

print(max(dp))
### BUGGY CODE ###

# coding: utf-8

S = input()
Q = int(input())
# print("S:{}".format(S))
# print("Q:{}".format(Q))
query = []

for i in range(Q):
    query.append(input().split())
# for i in query:
#     print(i)
new_s=""
leng= len(S)
for i in query:
    if len(i) == 1:
        S = S[::-1]
    else:
        if i[1]=="1":
            S = i[2]+S
        else:
            S = S+i[2]
print(S)


### FIXED CODE ###

# coding: utf-8

S = input()
Q = int(input())

query = []

for i in range(Q):
    query.append(input().split())


bool = True
pre =''
suf =''

for i in query:
    if len(i) == 1:
        bool = not(bool)

    else:
        if i[1]=="1":
            if bool:
                pre = i[2]+pre
            else:
                suf += i[2]
        else:
            if bool:
                suf += i[2]
            else:
                pre = i[2]+pre

S = pre+ S +suf
print(S) if bool else print(S[::-1])
### BUGGY CODE ###

n, m = map(int, input().split())
a = list([int(x) for x in input().split()])

for i in range(m):
    a[a.index(max(a))] = max(a)//2
print(sum(a))


### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = [-int(x) for x in input().split()]
heapq.heapify(a)

for i in range(m):
    l = -heapq.heappop(a)
    heapq.heappush(a, -(l//2))
    
print(-sum(a))
### BUGGY CODE ###

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

r = s.count('R')
g = s.count('G')
b = s.count('B')

ans = r * g * b

for i in range(0,n-2):
    for j in range(1,int(n/2)+1):
        if i + j + j <= n-1:
            if s[i] != s[i+j] and s[i] != s[i+j+j] and s[i+j] != s[i+j+j] :
                ans = ans - 1

print(ans)

### FIXED CODE ###

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

r = s.count('R')
g = s.count('G')
b = s.count('B')

ans = r * g * b

for i in range(0,n-2):
    for j in range(1,int((n-i)/2)+1):
        if i + j + j <= n-1:
            if s[i] != s[i+j] and s[i] != s[i+j+j] and s[i+j] != s[i+j+j] :
                ans = ans - 1

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

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

def main():
    l = [1 if a[0] >= j else 0 for j in range(K+1)]
    s = a[0]
    for i in range(1,N):
        t = 0
        lt = l
        l = [0] * (K + 1)
        s += a[i]
        for j in range(min(K+1, s+1)):
            if j == 0:
                t = 1
                l[j] = 1
            else:
                if j <= a[i]:
                    t += lt[j]
                else:
                    t += (lt[j] - lt[j - a[i] - 1])
                l[j] += t
    return l[-1] % (10 ** 9 + 7)
            
print(main())


### FIXED CODE ###

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

def main():
    l = [1 if a[0] >= j else 0 for j in range(K+1)]
    lt= [0] * (K+1)
    s = a[0]
    for i in range(1,N):
        lt, l = l, lt
        s += a[i]
        l[0] = 1
        t = 1
        for j in range(1, a[i]+1):
                t += lt[j]
                l[j] = t
        for j in range(a[i]+1, min(K+1, s+1)):
                t += (lt[j] - lt[j - a[i] - 1])
                l[j] = t
    return l[-1] % (10 ** 9 + 7)
            
print(main())