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

text = input()
result=[0]*len(text)
letter=[]
for i in range(1,len(text)):
  if(text[i]!=text[i-1]):
    letter=letter+[i]
letter=letter+[len(text)]

##端の処理
if(text[0]=="L"):
  result[0]=letter[0]

####RRR...(n個)...RL...(m個)...Lのとき
####n+mが偶数なら(n+m)/2個ずつ
####奇数ならnが奇数のときRに(n+m+1)/2,Lに(n+m-1)/2
####nが偶数のときRに(n+m-1)/2,Lに(n+m+1)/2たまる

#はじめの文字がLのとき
if(text[0]=="L"):
  i=1
  while(i+1<len(letter)):
    n=letter[i]-letter[i-1]
    m=letter[i+1]-letter[i]
    if((n+m)%2==0):
      result[letter[i]-1]=(n+m)//2
      result[letter[i]]=(n+m)//2
    elif(n%2==1):
      result[letter[i]-1]=(n+m+1)//2
      result[letter[i]]=(n+m-1)//2   
    else:
      result[letter[i]-1]=(n+m-1)//2
      result[letter[i]]=(n+m+1)//2
    i=i+2
else:
  n=letter[0]
  m=letter[1]-letter[0]
  if((n+m)%2==0):
    result[letter[0]-1]=(n+m)//2
    result[letter[0]]=(n+m)//2
  elif(n%2==1):
    result[letter[0]-1]=(n+m+1)//2
    result[letter[0]]=(n+m-1)//2   
  else:
    result[letter[0]-1]=(n+m-1)//2
    result[letter[0]]=(n+m+1)//2 
  i=2
  while(i+1<len(letter)):
    n=letter[i]-letter[i-1]
    m=letter[i+1]-letter[i]
    if((n+m)%2==0):
      result[letter[i]-1]=(n+m)//2
      result[letter[i]]=(n+m)//2
    elif(n%2==1):
      result[letter[i]-1]=(n+m+1)//2
      result[letter[i]]=(n+m-1)//2   
    else:
      result[letter[i]-1]=(n+m-1)//2
      result[letter[i]]=(n+m+1)//2
    i=i+2
    
    
###端の処理
if(text[-1]=="R"):
  result[-1]=letter[-1]-letter[-2]
  
print(' '.join(map(str, result)))



### FIXED CODE ###

text = input()
result=[0]*len(text)
N=len(text)

####RRR...(n個)...RL...(m個)...Lのとき
####n+mが偶数なら(n+m)/2個ずつ
####奇数ならnが奇数のときRに(n+m+1)/2,Lに(n+m-1)/2
####nが偶数のときRに(n+m-1)/2,Lに(n+m+1)/2たまる

s=0
i=0
j=0
while j<N :
  while text[i]=="R" :
    i+=1
  j=i+1
  while (j<N and text[j]=="L") :
    j+=1
  if (j-s)%2==0:
    result[i-1]=(j-s)//2
    result[i]=(j-s)//2
  else:
    result[i-1]=(j-s-1)//2
    result[i]=(j-s-1)//2
    result[i-(s-i)%2]+=1
  s=j
  i=s+1

print(' '.join(map(str, result)))
### BUGGY CODE ###

from collections import deque

from sys import stdin
readline = stdin.readline

INF = float('inf')

H, W = map(int, readline().split())
Ch, Cw = map(lambda x: int(x) - 1, readline().split())
Dh, Dw = map(lambda x: int(x) - 1, readline().split())
S = [readline()[:-1] for _ in range(H)]

t = [[INF] * W for _ in range(H)]
for h in range(H):
    th = t[h]
    Sh = S[h]
    for w in range(W):
        if Sh[w] == '#':
            th[w] = -1

t[Ch][Cw] = 0
q = deque([(Ch, Cw)])
while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        ti = t[i]
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if ti[j] <= a + 1:
                continue
            ti[j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])


### FIXED CODE ###

from collections import deque

INF = float('inf')

H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(H)]

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

card = set(range(1, n+1))

card

gate = []
for i in range(m):
    l, r = map(int, input().split())
    card = card & set(range(l, r+1))

print(len(card))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
n, m = map(int, input().split())

gate = []
for i in range(m):
    l, r = map(int, input().split())
    gate.append([l, r])

gate = np.array(gate)

l = gate[:, 0].max()
r = gate[:, 1].min()

if r+1-l>0:
    print(r+1-l)
else:
    print(0)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)

n = int(input())
a = list(map(int, input().split()))
# dp = [None]*(n+1)
#dp = [[None]*(n+1) for _ in range(2)]
dp = [[None]*(2) for _ in range(n+1)]

def solve(a):
    if len(a) == 0:
        return 0
    elif len(a) == 1:
        return a[0]
    elif len(a) == 2:
        v1 = a[0] + a[1]
        v2 = -a[0] - a[1]
        return max(v1, v2)

    v1 = a[0] + solve(a[1:])
    v2 = -a[0] + solve([-a[1]] + a[2:])
    return max(v1, v2)

def solve(a, flg):
    l = len(a)
    if dp[l][flg] is not None:
        return dp[l][flg]

    if flg == 1:
        a[0] = -a[0]

    if l == 0:
        dp[l][flg] = 0
    elif l == 1:
        dp[l][flg] = a[0]
    elif l == 2:
        v1 = a[0] + a[1]
        v2 = -a[0] - a[1]
        dp[l][flg] = max(v1, v2)
    else:
        v1 = a[0] + solve(a[1:], 0)
        v2 = -a[0] + solve(a[1:], 1)
        dp[l][flg] = max(v1, v2)
        # if flg == 0:
        #     v1 = a[0] + solve(a[1:], flg)
        #     v2 = -a[0] + solve(a[1:], abs(flg - 1))
        #     dp[l][flg] = max(v1, v2)
        # else:
        #     v1 = -a[0] + solve(a[1:], flg)
        #     v2 = a[0] + solve(a[1:], abs(flg - 1))
        #     dp[l][flg] = max(v1, v2)

    return dp[l][flg]

#def solve(idx):
print(solve(a, 0))
#print(solve(a, 1))
#print(solve(a, 0))
# v1 = solve(a, 1)
# v2 = solve(a, 0)
#
# print(v1, v2)
# print(max(v1, v2))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)

n = int(input())
a = list(map(int, input().split()))
dp = [[None]*(2) for _ in range(n+1)]

dp[n-1][0] = a[n-1]
dp[n-1][1] = -a[n-1]

for i in reversed(range(n-1)):
    for j in range(2):
        #print('\n# i: ' + str(i))
        # Unexe
        unexe_unexe = a[i] + dp[i+1][0]
        exe_unexe = -a[i] + dp[i+1][1]
        dp[i][0] = max(unexe_unexe, exe_unexe)

        # Exe
        unexe_exe = a[i] + dp[i+1][1]
        exe_exe = -a[i] + dp[i+1][0]
        dp[i][1] = max(unexe_exe, exe_exe)

#print(dp)
#print(max(dp[0][0], dp[0][1]))
print(dp[0][0])
### BUGGY CODE ###

s=input()
x,y=map(int,input().split())
ss=[len(i) for i in s.split("T")]
x-=ss[0]
a=[]
b=[]
for i in range(1,len(ss)):
  if ss[i]==0:continue
  if i%2==1:b.append(ss[i])
  else:a.append(ss[i])
x=abs(x)
y=abs(y)
def check(n,a):
  dp=[[0]*40001 for _ in range(len(a)+1)]
  n+=20000
  dp[0][20000]=1
  for i in range(1,len(a)+1):
    for j in range(40001):
      if j+a[i-1]<=40000:dp[i][j+a[i-1]]|=dp[i-1][j]
      if j-a[i-1]>=0:dp[i][j-a[i-1]]|=dp[i-1][j]
  if dp[len(a)][n]==1:return True
  return False
if check(x,a) and check(y,b):print("Yes")
else:print("No") 


### FIXED CODE ###

s=input()
x,y=map(int,input().split())
ss=[len(i) for i in s.split("T")]
x-=ss[0]
a=[]
b=[]
for i in range(1,len(ss)):
  if ss[i]==0:continue
  if i%2==1:b.append(ss[i])
  else:a.append(ss[i])
x=abs(x)
y=abs(y)
if max(x,y)>8000:exit(print("No"))
def check(n,a):
  dp=[[0]*20001 for _ in range(len(a)+1)]
  n+=10000
  dp[0][10000]=1
  for i in range(1,len(a)+1):
    for j in range(20001):
      if j+a[i-1]<=20000:dp[i][j+a[i-1]]|=dp[i-1][j]
      if j-a[i-1]>=0:dp[i][j-a[i-1]]|=dp[i-1][j]
  if dp[len(a)][n]==1:return True
  return False
if check(x,a) and check(y,b):print("Yes")
else:print("No")
### BUGGY CODE ###

#!/usr/bin/env python3
# coding: utf-8
"""
about module
"""

def main():
    n, k = map(int, input().split())

    while n*2 > k:
        n = abs(n-k)
    return n

if __name__ == '__main__':
    print(main())


### FIXED CODE ###

#!/usr/bin/env python3
# coding: utf-8
"""
about module
"""


def main():
    n, k = map(int, input().split())
    if n > k:
        n = n % k

    while n * 2 > k:
        n = abs(n - k)
    return n


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

n,p = map(int,input().split())
a = list(map(int,input().split()))
z = 0
for i in range(2**n):
    x = i
    y = 0
    for j in range(n):
        if x % 2 != 0:
            y += a[j]
        x = x // 2
        if x == 0:
            break
    if y % 2 == p:
        z += 1
print(z)

### FIXED CODE ###

n,p = map(int,input().split())
a = list(map(int,input().split()))
flg = True
for i in a:
    if i % 2 != 0:
        flg = False
        break
if flg:
    if p == 0:
        print(2**n)
    else:
        print(0)
else:
    print(2**(n-1))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

## Library

import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy

## input

# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))

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

A.sort(reverse=True)

if N == 2:
    print(A[0])
    sys.exit()

if N == 3:
    print(A[0]+A[1])
    sys.exit()

B = []
B.append(A[1])
B.append(A[2])
B.append(A[2])
ans = A[0]+A[1]

for i in range(3,N):
    ans += max(B)
    B.pop(0)
    B.append(A[i])
    B.append(A[i])

print(ans)





### FIXED CODE ###

# -*- coding: utf-8 -*-

## Library

import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy

## input

# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))

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

A.sort(reverse=True)

if N == 2:
    print(A[0])
    sys.exit()

if N == 3:
    print(A[0]+A[1])
    sys.exit()

B = []
B.append(A[1])
B.append(A[2])
B.append(A[2])
ans = A[0]+A[1]

tmp = 0

for i in range(3,N):
    ans += B[tmp]
    tmp += 1
    B.append(A[i])
    B.append(A[i])

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

import sys
sys.setrecursionlimit(100005)
mod=1000000007
# https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_2

def dfs(v,a):
    w=b=1
    for u in links[v]:
        if u==a:
            continue
        cw,cb=dfs(u,v)
        w*=cw+cb
        b*=cw
        w%=mod
        b%=mod
    return w,b


n=int(input())
links=[set() for i in range(n)]

for line in sys.stdin.readlines():
    x,y=map(int, line.split())
    x-=1
    y-=1
    links[x].add(y)
    links[y].add(x)

print(sum(dfs(0,None))%mod)

### FIXED CODE ###


import sys
sys.setrecursionlimit(100005)
mod=1000000007
# https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_2

def dfs(v,a):
    w=b=1
    for u in links[v]:
        if u==a:
            continue
        cw,cb=dfs(u,v)
        w*=cw+cb
        b*=cw
        w%=mod
        b%=mod
    return w,b


n=int(input())
links=[set() for i in range(n)]

for line in sys.stdin.readlines():
    x,y=map(int, line.split())
    x-=1
    y-=1
    links[x].add(y)
    links[y].add(x)

print(sum(dfs(0,None))%mod)
### BUGGY CODE ###

import bisect

N,M=[int(a) for a in input().split()]
A=[int(a) for a in input().split()]

A.sort()
#print(A)
for i in range(M):
    if(A[len(A)-1]==0):
        continue
    score=A[len(A)-1]//2
    num = bisect.bisect_right(A,score)
    #print("score=" + str(score) +" num="+str(num))
    score=[score]
    #print(A[0:num])
    A=A[0:num] + score + A[num:-1]
    #print(A)

total=0
for i in A:
    total+=i

print(total)

### FIXED CODE ###

import bisect
import queue

N,M=[int(a) for a in input().split()]
A=[int(a) for a in input().split()]

#優先度付きキューの作成とpush
q=queue.PriorityQueue()
for i in A:
    q.put(-i)

#最大値を取り出し,1/2倍した後push
for i in range(M):
    num = - q.get()
    #print(num)
    num=num//2
    q.put(-num)

total=0
for i in A:
    total+= - q.get()

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

import fractions
n=int(input())
t = list(map(int, input().split()))
l=[0 for i in range(n)]
ans = t[0]
for i in range(1, n):
    ans = ans * t[i] // fractions.gcd(ans, t[i])
for j in range(n):
    l[j]=ans//t[j]
print(sum(l)%(10**9+7))

### FIXED CODE ###

import fractions
n=int(input())
t = list(map(int, input().split()))
x=0
ans = t[0]
for i in range(1, n):
    ans = ans * t[i] // fractions.gcd(ans, t[i])
for j in range(n):
    x+=ans//t[j]
print(x%(10**9+7))
### BUGGY CODE ###

l,r=map(int,input().split())
s=[]
i=0
j=0
if (r-l)>4038:
    while i!=(r-l)+1 and i!=2019:
        while j!=(r-l)+1 and j!=2019:
            s.append(((l+i)*(l+j))%2019)
            j+=1
        j=0
        i+=1
    print(min(s))
else:
    while i!=(r-l)+1:
        while j!=(r-l)+1:
            if i!=j:
                s.append(((l+i)*(l+j))%2019)
            j+=1
        j=0
        i+=1
    #print(s)
    print(min(s))

### FIXED CODE ###

l,r=map(int,input().split())
s=[]
i=0
j=0
if (r-l)>4038:
    while i!=(r-l)+1 and i!=2019:
        while j!=(r-l)+1 and j!=2019:
            s.append(((l+i)*(l+j))%2019)
            j+=1
        j=0
        i+=1
    print(min(s))
else:
    while i!=(r-l)+1:
        while j!=(r-l)+1:
            if i!=j:
                s.append(((l+i)*(l+j))%2019)
            j+=1
        j=0
        i+=1
    #print(s)
    print(min(s))
### BUGGY CODE ###



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

ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        ans += A[i]*A[j]
print(ans%(10**9+7))


### FIXED CODE ###

import functools
import operator

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
ans = 0
v = sum(A)
for i in range(N-1):
    v -= A[i]
    ans += A[i]*v
print(ans%mod)
### BUGGY CODE ###

import numpy as np

N, Q = map(int,input().split())
S = str(input())
A = [list(map(int,input().split())) for i in range(Q)]

L_cnt = np.zeros(N-1)
L_cnt[0] = 0
L_str = S[0]
R_cnt = np.zeros(N-1)
R_cnt[0] = 0
R_str = S[N-1]

for i in range(N-2):
  L_str = L_str + S[i+1]
  L_cnt[i+1] = L_cnt[i] + (L_str[-2:] == 'AC')
  R_str = S[N-2-i] + R_str
  R_cnt[i+1] = R_cnt[i] + (R_str[:2] == 'AC')
  #print(i, L_str)
  #print(i, R_str)

#print(L_cnt)
#print(R_cnt)
  
n_whole = S.count('AC')
for i in range(Q):
  ans = n_whole - (L_cnt[A[i][0]-1] + R_cnt[N-A[i][1]])
  print(int(ans))
  




"""
## 題意を愚直に表したもの（~10^10の計算量）
for i in range(Q):
  word = S[A[i][0]-1:A[i][1]]
  word_remove = word.replace('T', '').replace('G', '')
  ans = word_remove.count('AC')
  print(ans)
"""



### FIXED CODE ###

import numpy as np

N, Q = map(int,input().split())
S = str(input())
A = [list(map(int,input().split())) for i in range(Q)]

"""
import random
base_list = ['A', 'T', 'C', 'G']
S = ''
N = int(1e5)
Q = 1
A = [[100, 900]]
for i in range(N):
  S += random.choice(base_list)
"""

L_cnt = np.zeros(N-1)
R_cnt = np.zeros(N-1)

for i in range(N-2):
  L_cnt[i+1] = (S[i:i+2] == 'AC')
  R_cnt[i+1] = (S[N-2-i:N-i] == 'AC')

#print(L_cnt)
#print(R_cnt)
  
n_whole = S.count('AC')
L_cumsum = np.array(L_cnt).cumsum()
R_cumsum = np.array(R_cnt).cumsum()
for i in range(Q):
  ans = n_whole - (L_cumsum[A[i][0]-1] + R_cumsum[N-A[i][1]])
  print(int(ans))
  




"""
## 題意を愚直に表したもの（~10^10の計算量）
for i in range(Q):
  word = S[A[i][0]-1:A[i][1]]
  word_remove = word.replace('T', '').replace('G', '')
  ans = word_remove.count('AC')
  print(ans)
"""
### BUGGY CODE ###

a=int(input())
b=list(map(int,input().split()))
c=max(b)+1
d=[]
ans=0
for i in range(a):
  e=0
  while c-e>b[i]:
    e+=b[i]
    d+=[e]
for i in b:
    if d.count(i)==1:
      ans+=1
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
max_a = max(a)
cnt_d = [0] * (max_a + 1)

for ai in a:
    for multi in range(ai, max_a + 1, ai):
        cnt_d[multi] += 1

print(sum(cnt_d[ai] == 1 for ai in a))
### BUGGY CODE ###

from collections import Counter
N,P=map(int,input().split())
A=[]
i=2
ans=1
while P!=1:
    if P%i==0:
        A.append(i)
        P//=i
    else:
        i+=1
A=Counter(A)
for key,value in A.items():
    if value>=N:
        ans*=key**(value//N)
print(ans)

### FIXED CODE ###

n,p = map(int,input().split())
 
def pfact(m):
	pf = {}
	for i in range(2,int(m**0.5)+1):
		while m%i == 0:
			pf[i] = pf.get(i,0) + 1
			m //= i
	if m>1 : pf[m]=1
	return pf
 
ans = 1
for i, j in pfact(p).items():
	ans *= i**(j//n)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    R, C, K = map(int, input().split())
    A = [[0]*C for _ in range(R)]
    for i in range(K):
        r, c, v = map(int, input().split())
        r, c = r-1, c-1
        A[r][c] = v

    dp0 = [[0]*(C+1) for i in range(R+1)]
    dp1 = [[0]*(C+1) for i in range(R+1)]
    dp2 = [[0]*(C+1) for i in range(R+1)]
    dp3 = [[0]*(C+1) for i in range(R+1)]
    for i in range(R):
        for j in range(C):
            dp3[i][j] = max(dp3[i][j], dp2[i][j]+A[i][j])
            dp2[i][j] = max(dp2[i][j], dp1[i][j]+A[i][j])
            dp1[i][j] = max(dp1[i][j], dp0[i][j]+A[i][j])

            dp3[i][j+1] = max(dp3[i][j+1], dp3[i][j])
            dp2[i][j+1] = max(dp2[i][j+1], dp2[i][j])
            dp1[i][j+1] = max(dp1[i][j+1], dp1[i][j])
            dp0[i][j+1] = max(dp0[i][j+1], dp0[i][j])

            dp0[i+1][j] = max(dp0[i+1][j], dp0[i][j])
            dp0[i+1][j] = max(dp0[i+1][j], dp1[i][j])
            dp0[i+1][j] = max(dp0[i+1][j], dp2[i][j])
            dp0[i+1][j] = max(dp0[i+1][j], dp3[i][j])
    #print(dp)
    print(max([dp0[R-1][C-1], dp1[R-1][C-1], dp2[R-1][C-1], dp3[R-1][C-1]]))

if __name__ == '__main__':
    main()


### FIXED CODE ###

#import io, os
#input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

import sys
input = sys.stdin.buffer.readline

def main():
    R, C, K = map(int, input().split())
    A = [[0]*C for _ in range(R)]
    for i in range(K):
        r, c, v = map(int, input().split())
        r, c = r-1, c-1
        A[r][c] = v

    dp0 = [[0]*(C+1) for i in range(R+1)]
    dp1 = [[0]*(C+1) for i in range(R+1)]
    dp2 = [[0]*(C+1) for i in range(R+1)]
    dp3 = [[0]*(C+1) for i in range(R+1)]
    for i in range(R):
        for j in range(C):
            dp3[i][j] = max(dp3[i][j], dp2[i][j]+A[i][j])
            dp2[i][j] = max(dp2[i][j], dp1[i][j]+A[i][j])
            dp1[i][j] = max(dp1[i][j], dp0[i][j]+A[i][j])

            dp3[i][j+1] = max(dp3[i][j+1], dp3[i][j])
            dp2[i][j+1] = max(dp2[i][j+1], dp2[i][j])
            dp1[i][j+1] = max(dp1[i][j+1], dp1[i][j])
            dp0[i][j+1] = max(dp0[i][j+1], dp0[i][j])

            dp0[i+1][j] = max(dp0[i+1][j], dp0[i][j])
            dp0[i+1][j] = max(dp0[i+1][j], dp1[i][j])
            dp0[i+1][j] = max(dp0[i+1][j], dp2[i][j])
            dp0[i+1][j] = max(dp0[i+1][j], dp3[i][j])
    #print(dp)
    print(max([dp0[R-1][C-1], dp1[R-1][C-1], dp2[R-1][C-1], dp3[R-1][C-1]]))

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

# -*- coding:utf-8 -*-

def solve():
    S = input()
    Q = int(input())

    is_reverse = False # 反転中か？

    for _ in range(Q):
        query = input()
        if query == "1":
            is_reverse = not is_reverse
        else:
            t, f, c = query.split()
            if f == "1":
                if is_reverse:
                    # 末尾にcを追加
                    S = S + c
                else:
                    # 先頭にcを追加
                    S = c + S
            else:
                if is_reverse:
                    # 先頭に追加
                    S = c + S
                else:
                    # 末尾に追加
                    S = S + c

    if is_reverse:
        print(S[::-1])
    else:
        print(S)


if __name__ == "__main__":
    solve()


### FIXED CODE ###

# -*- coding:utf-8 -*-
from collections import deque

def solve():
    d = deque(input())
    Q = int(input())

    is_reverse = False # 反転中か？

    for _ in range(Q):
        query = input()
        if query == "1":
            is_reverse = not is_reverse
        else:
            _, f, c = query.split()

            if f == "1":
                if is_reverse:
                    # 末尾にcを追加
                    d.append(c)
                else:
                    # 先頭にcを追加
                    d.appendleft(c)
            else:
                if is_reverse:
                    # 先頭に追加
                    d.appendleft(c)
                else:
                    # 末尾に追加
                    d.append(c)

    if is_reverse:
        print("".join(reversed(list(d))))
    else:
        print("".join(d))


def solve2():
    S = list(input())
    Q = int(input())
    M = 2*10**5+10
    data = [None]*M
    data.extend(S)
    data.extend([None]*M)
    left, right = M-1, M+len(S)

    is_reverse = False

    for _ in range(Q):
        query = input()
        if query == "1":
            is_reverse = not is_reverse
        else:
            t, f, c = query.split()
            if f == "1":
                if is_reverse:
                    # 末尾にcを追加
                    data[right] = c
                    right += 1
                else:
                    # 先頭にcを追加
                    data[left] = c
                    left -= 1
            else:
                if is_reverse:
                    # 先頭に追加
                    data[left] = c
                    left -= 1
                else:
                    # 末尾に追加
                    data[right] = c
                    right += 1

    # 出力
    if is_reverse:
        print("".join(data[right-1:left:-1]))
        # for i in range(right-1, left, -1):
        #     print(data[i], end="")
    else:
        # for i in range(left+1, right):
        #     print(data[i], end="")
        print("".join(data[left+1:right]))
    # print()


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

arr = []
for i in range(int(input())):
    arr.append(int(input()))
m = 0
for i in range(len(arr)-1):
    for j in range(i+1, len(arr)):
        if i == 0 and j == 1:
            m = arr[j] - arr[i]
        else:
            m = max(m, arr[j] - arr[i])
print(m)   

### FIXED CODE ###

n = int(input())
arr = [int(input()) for i in range(n)]

m = 1 - 10**9
minv = arr[0]
for i in range(1,len(arr)):
    if arr[i] - minv > m:
        m = arr[i] - minv
    minv = min(minv, arr[i])
print(m)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
P = list(map(lambda x: int(x)-1, input().split()))
C = list(map(int, input().split()))

ans = -float("inf")

for st in range(N):
  S = []
  temp = P[st]
  S.append(C[temp])
  while temp != st:
    temp = P[temp]
    S.append(S[-1] + C[temp])
  cnt = len(S)
  loop, k = divmod(K, cnt)
  point = 0
  if S[-1] >= 0:
    if k == 0:
      loop -= 1
      k += cnt
    point += S[-1] * loop
  else:
    if loop >= 1:
      k = cnt
  ans = max(ans, point + max(S[:k]))

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(lambda x: int(x)-1, input().split()))
C = list(map(int, input().split()))

ans = -float("inf")

for st in range(N):
  S = []
  temp = P[st]
  S.append(C[temp])
  while temp != st:
    temp = P[temp]
    S.append(S[-1] + C[temp])
  cnt = len(S)
  loop, k = divmod(K, cnt)
  point = 0
  if S[-1] >= 0:
    if k == 0:
      loop -= 1
      k += cnt
    point += S[-1] * loop
  else:
    if loop >= 1:
      k = cnt
  ans = max(ans, point + max(S[:k]))

print(ans)