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

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, k = na()
a = na()
f = na()
a.sort()
f.sort()

def ok(h, a, f, k):
    n = len(a)
    s = 0
    for i in range(n):
        s += max(0, a[i]-h//f[n-1-i])
    return s <= k


low = -1; high = 2000000000000
while high - low > 1:
    h = high+low>>1
    if ok(h, a, f, k):
        high = h
    else:
        low = h
print(high)

### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, k = na()
a = na()
f = na()
a.sort()
f.sort()

def ok(h, a, f, k):
    n = len(a)
    s = 0
    for i in range(n):
        s += max(0, a[i]-h//f[n-1-i])
    return s <= k


low = -1; high = 2000000000000
while high - low > 1:
    h = high+low>>1
    if ok(h, a, f, k):
        high = h
    else:
        low = h
print(high)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int,input().split())
S = list(input())[:-1]
for i in range(Q):
    count = 0
    l, r = map(int, input().split())
    tmp = S[l-1:r]
    for j in range(len(tmp)-1):
        if tmp[j] == "A" and tmp[j+1] == "C":
            count += 1
    print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int,input().split())
S = list(input())[:-1]
list_Sum = [0]*(N+1)
for i in range(1, N):
    list_Sum[i+1] = list_Sum[i]
    if S[i-1] == "A" and S[i] == "C":
        list_Sum[i+1] += 1
for i in range(Q):
    l, r = map(int,input().split())
    print(list_Sum[r]-list_Sum[l])
### BUGGY CODE ###


s = input()
k = int(input())
dd = {}
if len(s) == 1:
    print(s)
    exit()
for i in range(len(s)):
    dd[s[i]] = 1
for i in range(len(s)-1):
    for j in range(i+1, len(s)):
        dd[s[i:j+1]] = 1
li = []
for key in dd:
    li.append(key)
li.sort()
print(li[k-1])

### FIXED CODE ###

from collections import defaultdict
s = input()
k = int(input())
dd = {}
if len(s) == 1:
    print(s)
    exit()
for i in range(len(s)):
    dd[s[i]] = 1
for i in range(len(s)-1):
    for j in range(i+1, len(s)):
        if j-i+1 <= k:
            dd[s[i:j+1]] = 1
li = []
for key in dd:
    li.append(key)
li.sort()
print(li[k-1])
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
q = int(input())

a = Counter(a)
for _ in range(q):
    b, c = map(int, input().split())
    a[c] += a[b]
    del a[b]
    ans = [x * y for x, y in a.items()]
    print(sum(ans))

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
q = int(input())
total = sum(a)

a = Counter(a)
for _ in range(q):
    b, c = map(int, input().split())
    total += a[b] * c
    total -= a[b] * b
    a[c] += a[b]
    del a[b]
    print(total)
### BUGGY CODE ###

def f(a, b, ans, s):
    if len(a) == 0:
        print(ans)
        exit()
    if max(a) >= max(b):
        i = a.index(max(a))
        ans += a[i] * s
        a.pop(i)
        b.pop(i)
    else:
        i = b.index(max(b))
        ans += a[i] * s
        a.pop(i)
        b.pop(i)
    f(b, a, ans, (-1) * s)


def main():
    N = int(input())
    A = []
    B = []
    for _ in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
    f(A, B, 0, 1)


main()


### FIXED CODE ###

def main():
    N = int(input())
    ab = [[int(i) for i in input().split()] for _ in range(N)]
    ab = sorted(ab, key=lambda x: x[0] + x[1], reverse=True)
    ans = 0
    for i in range(N):
        if i % 2 == 0:
            ans += ab[i][0]
        else:
            ans -= ab[i][1]
    print(ans)


main()
### BUGGY CODE ###

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

ans = 0
for i in range(n):
    for j in range(i+1, n):
        if abs(j-i) == a[i]+a[j]:
            ans += 1
print(ans)

### FIXED CODE ###

import sys
# sys.stdin = open('input.txt')

# i < j
# j - i == Ai + Aj
# j - Aj == i + Ai

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

ans = 0
# key: i + Ai, value: count
d = {}

for j in range(n):
    a1 = j - a[j]
    try:
        ans += d[a1]
    except KeyError:
        d[a1] = 0

    a2 = j + a[j]
    try:
        d[a2] += 1
    except KeyError:
        d[a2] = 1

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

s = input()
origin = len(s)

for i in range(origin//2):
    s = s.replace("01", "")
    s = s.replace("10", "")

print(origin - len(s))

### FIXED CODE ###

s = input()

c0 = s.count("0")
c1 = s.count("1")

print(min(c0, c1)*2)
### BUGGY CODE ###

#初期入力
S = input()
Q = int(input())
FQ_dic ={i:tuple() for i in range(Q)}
    
for i in range(Q):
    FQ_dic[i] =tuple(input().split())
    
#
rev =0
for fq in FQ_dic.values():
    if      fq[0] =="1":
                rev +=1
    elif    fq[0] =="2":
        if      fq[1]=="1": #後ろにつける
            if rev %2 ==0:
                    S = fq[2] + S
            if rev %2 ==1:
                    S = S +fq[2] 
        elif    fq[1] =="2": #前につける
            if rev %2 ==0:
                    S = S + fq[2]
            if rev %2 ==1:        
                    S = fq[2] + S
if rev %2 ==0:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

#前・左につける変数、後ろ・右につける変数を用意して最後に足す
#前・左は最後にひっくり返す（abc ⇒cba)

#初期入力
import sys
input = sys.stdin.readline
S = input()
S=S.strip("\n")
Q = int(input())
FQ_dic={}
for i in range(Q):
    FQ_dic[i] =input().split()

rev =0
front =""
back =""

for i in range(Q):
   # print(S) 

    if FQ_dic[i][0] =="1": #逆転する
                rev +=1
    else:                   #逆転なし  
        if FQ_dic[i][1]=="1":     #前=左につける 
            if rev %2 ==0:
                front += FQ_dic[i][2]
            else:
                back  += FQ_dic[i][2]  
        else: #                      #後ろ=右につける
            if rev %2 ==0:
                back  += FQ_dic[i][2]  
            else:        
                front += FQ_dic[i][2]
front =front[::-1]
S =front + S + back

if rev %2 ==0:
    print(*S,sep="")
else:
    print(*S[::-1],sep="")
### BUGGY CODE ###

# ABC 066 C
N = int(input())
A = input().split()

tmp = []
for i,a in enumerate(A):
    if i %2!=0:
        tmp.insert(0,a)
    else:
        tmp.append(a)
if N%2!=0:
    tmp=tmp[::-1]
print(' '.join(tmp))

### FIXED CODE ###

# ABC 066 C
N = int(input())
A = input().split()
from collections import deque

tmp = deque([])
for i,a in enumerate(A):
    if i %2!=0:
        tmp.appendleft(a)
    else:
        tmp.append(a)
if N%2!=0:
    tmp.reverse()
print(' '.join(tmp))
### BUGGY CODE ###

import sys
from math import sqrt, gcd, ceil, log
from bisect import bisect
from collections import defaultdict
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

# sys.setrecursionlimit(10**6)



def solve():
	s = inp().strip();# dic = defaultdict(int)
	sett = set(); sett.add(0)
	ans = 0; cum = 0
	for i in range(len(s)-1, -1, -1):

		cum += (int(s[i])*(10**(len(s)-i-1)% 2019)) % 2019
		cum %= 2019
		# print((int(s[i])*(10**(len(s)-i-1)% 2019)) % 2019, i, cum)
		if cum in sett:
			ans += 1
		sett.add(cum)
	# print(sett)
	print(ans)






if __name__ == "__main__":
	solve()

### FIXED CODE ###

import sys
from math import sqrt, gcd, ceil, log
from bisect import bisect
from collections import defaultdict
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

# sys.setrecursionlimit(10**6)



def solve():
	s = inp().strip();
	dic = defaultdict(int); dic[0] = 1
	# sett.add(0)
	ans = 0; cum = 0
	for i in range(len(s)-1, -1, -1):
		cum += (int(s[i])*pow(10, (len(s)-i-1), 2019)) % 2019
		cum %= 2019
		dic[cum] += 1
	# print(dic)
	for i in dic:
		ans += ((dic[i])*(dic[i]-1))//2
	print(ans)






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

A, B, N = map(int,input().split())
MAX = -10**18
d = min(B,N)
for i in range(0,d+1):
    a = (A *i) //B -A * (i//B)
    MAX = max(a,MAX)
print(MAX)

### FIXED CODE ###

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

if N >= B:
    x = B -1
else:
    x = N
MAX = 0
# for i in range(1,N+1):
#     MAX = max(MAX, (A*i)//B - A*(i//B))
# print(MAX)


ans = (A*x)//B - A*(x//B)
print(ans)
### BUGGY CODE ###

N = int(input())

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

for i in range(N):
  end = 0
  mim = 0
  for j in range(len(S[i])):
    if S[i][j] == "(":
      end += 1
    else :
      end -= 1
    mim = min(mim,end)
  
  if end >= 0:
    S_p.append((mim, end))
  else:
    S_n.append((end-mim, end))
  
S_p.sort(reverse=True)
S_n.sort(reverse=True)
#print(S_p)
#print(S_n)

check = 0
flag = True
for i in range(len(S_p)):
  if check + S_p[i][0] >= 0:
    check += S_p[i][1]
  else:
    flag = False
    break
  #print(check)
  
for i in range(len(S_n)):
  if check + S_n[i][1] - S_n[i][0] >= 0:
    check += S_n[i][1]
  else:
    flag = False
    break
  #print(check)
  
if check == 0 and flag:
  flag = True
else:
  flag = False

print("Yes" if flag else "No")

### FIXED CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()

N = int(input())

S_p = []
S_n = []

for i in range(N):
  end = 0
  mim = 0
  for c in input():
    if c == "(":
      end += 1
    else :
      end -= 1
    mim = min(mim,end)
  
  if end >= 0:
    S_p.append([mim, end])
  else:
    S_n.append([end-mim, end])
  
S_p.sort(reverse=True)
S_n.sort(reverse=True)
#print(S_p)
#print(S_n)

check = 0
flag = True
for i in range(len(S_p)):
  if check + S_p[i][0] >= 0:
    check += S_p[i][1]
  else:
    flag = False
    break
  #print(check)
  
for i in range(len(S_n)):
  if check + S_n[i][1] - S_n[i][0] >= 0:
    check += S_n[i][1]
  else:
    flag = False
    break
  #print(check)
  
if check == 0 and flag:
  flag = True
else:
  flag = False

print("Yes" if flag else "No")
### BUGGY CODE ###

import bisect

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
for _ in range(m):
    am = a.pop()
    am = am // 2
    bisect.insort_left(a, am)
    
print(sum(a))
    

### FIXED CODE ###

import heapq

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
b = []
heapq.heappush(b,0)
for _ in range(m):
    bm = -b[0]
    if len(a) != 0 and a[-1] > bm:
        am = a.pop()
        am = am // 2
        heapq.heappush(b,-am)
    else:
        bm = -heapq.heappop(b)
        bm = bm // 2
        heapq.heappush(b,-bm)
        
    
print(sum(a)-sum(b))
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
max_a = max(a)

for i in range(len(a)):
    if a[i] != max_a or a.count(a[i]) > 1:
        print(max_a)
        continue
    print(sorted(a)[-2])

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
max_a = max(a)
second_a = sorted(a)[-2]
max_count = a.count(max_a) - 1
if max_count:
    [print(max_a) for _ in range(len(a))]
else:
    [print(max_a) if a[i] != max_a else print(second_a) for i in range(len(a))]
### BUGGY CODE ###

a,b,c = map(int, input().split())
k = int(input())

i = 0
while i < k:
  if a >= b:
    b = b * 2
    i += 1
  if c >= b:
    c = c * 2
    i += 1

if a < b < c:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

a,b,c = map(int, input().split())
k = int(input())
 
i = 0
while a >= b:
  b = b * 2
  i += 1

j = 0
while b >= c:
  c = c * 2
  j += 1
  
if i + j <= k:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline
def main():
  ## input
  N,Q = map(int, readl().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, readl().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [int(readl().rstrip()) for _ in range(Q)] + [10**10]
  ans = []

  for x,s,t in sorted(STX):
    l = bisect_left(Dn,s)
    r = l
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans


if __name__ == "__main__":
  ans = main()
  while(len(ans)>0):
    print(heappop(ans)[1])    


### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

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


N,K = map(int,input().split())
P_List=list(map(int,input().split()))
#print(N,K)
#print(P_List)

def Kitaichi(p):
    result = 0
    for i in range(p):
        result += (i+1)*1/p
    #print(p,result)
    return result

pre_max=0
temp_max=0
max_num=0
for j in range(N-(K-1)):
    for k in range(K):
        #temp_max += P_List[j+k]
        temp_max += Kitaichi(P_List[j+k])
    #print(temp_max)

    if pre_max < temp_max:
        pre_max = temp_max
        max_num = j
    temp_max=0

#print('max_num:',max_num)
#result = 0
#for l in range(K):
#    result += Kitaichi(P_List[max_num+l])

#print(result)
print(pre_max)

### FIXED CODE ###


N,K = map(int,input().split())
P_List=list(map(int,input().split()))
#print(N,K)
#print(P_List)

def Kitaichi(p):
    result = 0
    for i in range(p):
        result += (i+1)*1/p
    #print(p,result)
    return result

def Kitaichi2(p):
    return (p+1)*0.5

kitaichi_list=[]
ruisekiwa_list=[]
ruisekiwa=0
for a in range(N):
    kitaichi_list.append(Kitaichi2(P_List[a]))
    ruisekiwa += Kitaichi2(P_List[a])
    ruisekiwa_list.append(ruisekiwa)

#print(kitaichi_list)
#print(ruisekiwa_list)
pre_max=0
temp_max=0
max_num=0
for j in range(N-(K-1)):
    if j == 0:
        temp_max = ruisekiwa_list[j+K-1] - 0
    else:
        temp_max = ruisekiwa_list[j+K-1] - ruisekiwa_list[j-1]
    

    if pre_max < temp_max:
        pre_max = temp_max
    temp_max=0

print(pre_max)
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split()))
ans = []*(n-1)
for i in range (1,n+1):
    print(a.count(i))



### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
ans = [0]*n
for i in a:
    ans[i-1]+=1
print(*ans)
### BUGGY CODE ###

N,M = map(int,input().split())
to = [[] for _ in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1
  to[a].append(b)
start,end = map(int,input().split())
start -= 1;end -= 1
#print(to)
INF = float("inf")
Stack = [(start,0)] #今の点、何歩目か
visit = [[INF,INF,INF] for _ in range(N)] #三歩目、一歩目、二歩目
visit[start][0] = 0
while Stack: #今の点、けんけんぱのどれか、一個前に止まった点
  v,step = Stack.pop()
  now = visit[v][step]
  step = (step+1)%3 #ここでstep+1歩目でvへ行く
  for w in to[v]:
    if visit[w][step] <= now:
      continue
    Stack.append((w,step)) #step歩目でwにいて次vへ行く。
    if step %3 == 0:
      visit[w][step] = min(visit[w][step],now+1)
    else:
      visit[w][step] = min(visit[w][step],now)
#print(visit)
if visit[end][0] == INF:
  ans = -1
else:
  ans = visit[end][0]
print(ans)

### FIXED CODE ###

from collections import deque
N,M = map(int,input().split())
to = [[] for _ in range(N*3)]
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1
  to[a*3].append(b*3+1)
  to[a*3+1].append(b*3+2)
  to[a*3+2].append(b*3)
start,end = map(int,input().split())
start -= 1;end -= 1
#print(to)
INF = float("inf")
Q = deque([start*3])
visit = [INF for _ in range(N*3)]
visit[start*3] = 0
while Q:
  v = Q.popleft()
  for w in to[v]:
    if visit[w] != INF:
      continue
    visit[w] = visit[v]+1
    if w == end*3:
      print(visit[w]//3)
      exit()
    Q.append(w) #step歩目でwにいて次vへ行く。

#print(visit)
if visit[end*3] == INF:
  ans = -1
else:
  ans = visit[end*3]//3
print(ans)
### BUGGY CODE ###

def main():
    s = input()
    q = int(input())

    rev = False
    for i in range(q):
        tfc = input().split()

        if tfc[0] == '1':
            rev = not rev
        else:
            f = tfc[1]
            c = tfc[2]
            if (f == '1' and not rev) or (f != '1' and rev):
                s = c + s
            else:
                s = s + c

    if rev:
        s = s[::-1]

    print(s)

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque

def main():
    s = input()
    q = int(input())

    Q = deque(s)
    rev = False
    for i in range(q):
        tfc = input().split()

        if tfc[0] == '1':
            rev = not rev
        else:
            f = tfc[1]
            c = tfc[2]
            if (f == '1' and not rev) or (f != '1' and rev):
                Q.appendleft(c)
            else:
                Q.append(c)

    if rev:
        print(''.join(list(Q)[::-1]))
    else:
        print(''.join(Q))

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

import sys
input = sys.stdin.readline
from itertools import accumulate

n, m, q = map(int, input().split())
S = [[0]*(m+1)] + [[0] + list(map(int, list(input().rstrip()))) for _ in range(n)]
B = [[0]*(m+1) for _ in range(n+1)]
U = [[0]*(m+1) for _ in range(n+1)]
L = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
  for j in range(1, m+1):
    if S[i][j]:
      U[i][j] = S[i-1][j]
      L[i][j] = S[i][j-1]
for i in range(1, n+1):
  B[i] = tuple(accumulate(S[i]))
  U[i] = tuple(accumulate(U[i]))
  L[i] = tuple(accumulate(L[i]))
B = list(zip(*B))
U = list(zip(*U))
L = list(zip(*L))
for j in range(1, m+1):
  B[j] = tuple(accumulate(B[j]))
  U[j] = tuple(accumulate(U[j]))
  L[j] = tuple(accumulate(L[j]))
B = tuple(zip(*B))
U = tuple(zip(*U))
L = tuple(zip(*L))
def calc_b(x1, y1, x2, y2):
  return B[x2][y2] - B[x1-1][y2] - B[x2][y1-1] + B[x1-1][y1-1]
def calc_u(x1, y1, x2, y2):
  return U[x2][y2] - U[x1][y2] - U[x2][y1-1] + U[x1][y1-1]
def calc_l(x1, y1, x2, y2):
  return L[x2][y2] - L[x1-1][y2] - L[x2][y1] + L[x1-1][y1]

for _ in range(q):
  x1, y1, x2, y2 = map(int, input().split())
  res = calc_b(x1, y1, x2, y2) - (calc_u(x1, y1, x2, y2) + calc_l(x1, y1, x2, y2))
  print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m, q = map(int, input().split())
S = [[0]*(m+1)] + [[0] + list(map(int, list(input().rstrip()))) for _ in range(n)]
B = [[0]*(m+1) for _ in range(n+1)]
U = [[0]*(m+1) for _ in range(n+1)]
L = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
  for j in range(1, m+1):
    B[i][j] = B[i-1][j] + B[i][j-1] - B[i-1][j-1] + S[i][j]
    U[i][j] = U[i-1][j] + U[i][j-1] - U[i-1][j-1] + U[i][j]
    L[i][j] = L[i-1][j] + L[i][j-1] - L[i-1][j-1] + L[i][j]
    if S[i][j]:
      U[i][j] += S[i-1][j]
      L[i][j] += S[i][j-1]
    
def calc_b(x1, y1, x2, y2):
  return B[x2][y2] - B[x1-1][y2] - B[x2][y1-1] + B[x1-1][y1-1]
def calc_u(x1, y1, x2, y2):
  return U[x2][y2] - U[x1][y2] - U[x2][y1-1] + U[x1][y1-1]
def calc_l(x1, y1, x2, y2):
  return L[x2][y2] - L[x1-1][y2] - L[x2][y1] + L[x1-1][y1]

for _ in range(q):
  x1, y1, x2, y2 = map(int, input().split())
  res = calc_b(x1, y1, x2, y2) - (calc_u(x1, y1, x2, y2) + calc_l(x1, y1, x2, y2))
  print(res)
### BUGGY CODE ###

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

sub = set(i for i in range(1, N + 1))
for _ in range(M):
    L, R = map(int, input().split())
    sub &= set(i for i in range(L, R + 1))
print(len(sub))

### FIXED CODE ###

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

st = 1
en = N
for _ in range(M):
    L, R = map(int, input().split())
    st = max(st, L)
    en = min(en, R)

ans = en - st
if ans < 0:
    print(0)
else:
    print(ans + 1)
### BUGGY CODE ###

import itertools
import functools
import math
from collections import Counter
from itertools import combinations


S=list(input())
Q=int(input())
for i in range(Q):
    Que = input()
    if Que == '1':
        S= list(reversed(S))
    else:
        T,F,C=map(str,Que.split())
        if F == '1':
            S=list(C)+S
        else:
            S.append(C)

print("".join(S))

### FIXED CODE ###

import itertools
import functools
import math
from collections import Counter
from itertools import combinations

def CHK():
    S=list(input())
    Q=int(input())
    H=""
    B=""
    rflg = 0
    for i in range(Q):
        Que = input()
        if Que == '1':
            if rflg == 0:
                rflg = 1
            else:
                rflg = 0
            #S= list(reversed(S))
        else:
            T,F,C=map(str,Que.split())
            if F == '1' and rflg == 0 or (F != '1' and rflg == 1):
                #S=list(C)+S
                H = C + H
            else:
                #S.append(C)
                B = B + C

    S = list(H) + S + list(B)
    if rflg == 1:
        S = list(reversed(S))
    print("".join(S))

CHK()
### BUGGY CODE ###

n, p = map(int, input().split())
if n == 1:
    print(p)
else:
    num = round(p ** (1 / n))
    for i in range(num + 1, 0, -1):
        if p % (i ** n) == 0:
            print(i)
            break

### FIXED CODE ###

n,p = map(int,input().split())
dum = round(p**(1/n))
for i in range(dum,-1,-1):
    if p%(i**n) == 0:
        print(i)
        break
### BUGGY CODE ###

a,b = map(int, input().split())
l = [(int(i)+1)/2 for i in input().split()]

ll = []

for i in range(a-b+1):
  ll += [sum(l[i:i+b])]

ll.sort()
print(ll[-1])

### FIXED CODE ###

a,b = map(int, input().split())
l = [(int(i)+1)/2 for i in input().split()]

temp = sum(l[:b])
max = temp
for i in range(b,a):
  temp = temp + l[i] - l[i-b]
  if max < temp:
    max = temp
    
print(max)
### BUGGY CODE ###

import itertools


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

print(sum([len(set(itertools.permutations(l, 3))) for l in itertools.combinations_with_replacement(list(range(K+1)), 3) if sum(l) == S]))


### FIXED CODE ###

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

R = 0

for X in range(max(0, S-2*K), K+1):
    for Y in range(max(0, S-X-K), K+1):
        if X + Y <= S:
            R += 1

print(R)
### BUGGY CODE ###

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]

dp = [[0] * (w + 1) for i in range(n + 1)]

for i in range(n):
    for sum_w in range(w + 1):
        if sum_w - wv[i][0] >= 0:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - wv[i][0]] + wv[i][1])
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
print(dp[n][w])

### FIXED CODE ###

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]

dp = [[0] * (w + 1) for i in range(n + 1)]

for i in range(n):
    for sum_w in range(w + 1):
        if sum_w - wv[i][0] >= 0:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - wv[i][0]] + wv[i][1])
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
print(max(dp[n]))