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

R, C, K = map(int, input().split())

V = [[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    V[r][c] = v

dp0 = [[0]*(C+1) for _ in range(R+1)]
dp1 = [[0]*(C+1) for _ in range(R+1)]
dp2 = [[0]*(C+1) for _ in range(R+1)]
dp3 = [[0]*(C+1) for _ in range(R+1)]
for i in range(R+1):
    for j in range(C+1):
        v = V[i][j]

        a = dp0[i][j]
        b = dp0[i][j]
        c = dp0[i][j]
        d = dp0[i][j]

        pa = pb = pc = pd = 0
        if i > 0:
            pa = dp0[i-1][j]
            pb = dp1[i-1][j]
            pc = dp2[i-1][j]
            pd = dp3[i-1][j]

        la = lb = lc = ld = 0
        if j > 0:
            la = dp0[i][j-1]
            lb = dp1[i][j-1]
            lc = dp2[i][j-1]
            ld = dp3[i][j-1]

        a = max(a, pa)
        b = max(b, pa+v)
        a = max(a, la)

        a = max(a, pb)
        b = max(b, pb+v)
        b = max(b, lb, la+v)

        a = max(a, pc)
        b = max(b, pc+v)
        c = max(c, lc, lb+v)

        a = max(a, pd)
        b = max(b, pd+v)
        d = max(d, ld, lc+v)

        dp0[i][j] = a
        dp1[i][j] = b
        dp2[i][j] = c
        dp3[i][j] = d

print(max(dp0[R][C], dp1[R][C], dp2[R][C], dp3[R][C]))


### FIXED CODE ###

R, C, K = map(int, input().split())

V = [[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    V[r][c] = v

pre = [[0]*(3+1) for _ in range(C+1)]
for i in range(R+1):
    now = [[0]*(3+1) for _ in range(C+1)]
    for j in range(C+1):
        for k in range(3+1):
            if i-1 >= 0:
                now[j][0] = max(now[j][0], pre[j][k])
                now[j][1] = max(now[j][1], pre[j][k] + V[i][j])

            if j-1 >= 0:
                now[j][k] = max(now[j][k], now[j-1][k])
                if k-1 >= 0:
                    now[j][k] = max(now[j][k], now[j-1][k-1] + V[i][j])
    pre = now

print(max(now[C]))
### BUGGY CODE ###

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

dic = {}

def count_word(add_word):
	exist = False
	# 辞書dicにすでに書いてあるかチェック
	for key, value in dic.items():
		if add_word==key:
			value += 1
			dic[key] = value
			exist = True
			break
	
	# 辞書dicにない場合、追加
	if exist==False: dic[add_word] = 1

	return dic

for word in s:
	count_word(word)

# 書かれた回数の最大値
value_max = max(dic.values())
# print(value_max)


ans = [k for k, v in dic.items() if v==value_max]
ans = sorted(ans)

for a in ans:
	print(a)
			

### FIXED CODE ###

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

dic = {}

for word in s:
	if word not in dic:
		dic[word] = 1
	else:
		dic[word] += 1

# 書かれた回数の最大値
value_max = max(dic.values())
# print(value_max)


ans = [k for k, v in dic.items() if v==value_max]
ans = sorted(ans)

for a in ans:
	print(a)
### BUGGY CODE ###

s = input()
K = int(input())
A =[]
b = len(s)
for i in range(b+1):
  for j in range(b+1):
    if j > i:
      A.append(s[i:j])
for i in range(b):
  A.append(s[i])
B = set(A)
B = list(B)
if K == 1:
  ans = min(B)
if K == 2:
  B.remove(min(B))
  ans = (min(B))
if K == 3:
  B.remove(min(B))
  B.remove(min(B))
  ans = (min(B))
if K == 4:
  B.remove(min(B))
  B.remove(min(B))
  B.remove(min(B))
  ans = (min(B))
if K == 5:
  B.remove(min(B))
  B.remove(min(B))
  B.remove(min(B))
  B.remove(min(B))
  ans = (min(B))
print(ans)

### FIXED CODE ###

s = input()
K = int(input())
A =[]
b = len(s)
for i in range(b+1):
      if i+1 < b+1:
        A.append(s[i:i+1])
      if i+2 < b+1:
        A.append(s[i:i+2])
      if i+3 < b+1:
        A.append(s[i:i+3])
      if i+4 < b+1:
        A.append(s[i:i+4])
      if i+5 < b+1:
        A.append(s[i:i+5])
B = set(A)
B = list(B)
B = sorted(B)
print(B[K-1])
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

h,w=map(int,input().split())
d=[]
for i in range(h):
    s=input()
    d.append(s)
x=h*w
p=[[x+1]*x for i in range(x)]
for i in range(x):
    for j in range(x):
        ih,iw=i//w,i%w
        jh,jw=j//w,j%w
        if "."==d[ih][iw]==d[jh][jw] and ih==jh and abs(iw-jw)==1:
            p[i][j]=1
            p[j][i]=1
        if "."==d[ih][iw]==d[jh][jw] and iw==jw and abs(ih-jh)==1:
            p[i][j]=1
            p[j][i]=1
        if i==j:
            p[i][j]=0
for i in range(x):
    for j in range(x):
        for k in range(x):
            ih,iw=i//w,i%w
            jh,jw=j//w,j%w
            kh,kw=k//w,k%w
            if d[ih][iw]==d[jh][jw]==d[kh][kw]==".":
                p[j][k]=min(p[j][k],p[j][i]+p[i][k])
ans=0
for i in p:
    for j in i:
        if j<x+1:
            ans=max(ans,j)
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
def sol():
    h,w=map(int,input().split())
    d=[]
    for i in range(h):
        s=input()
        d.append(s)
    x=h*w
    p=[[x+1]*x for i in range(x)]
    for i in range(x):
        for j in range(i+1):
            if i==j:
                p[i][j]=0
                p[j][i]=0
            ih,iw,jh,jw=i//w,i%w,j//w,j%w
            if d[ih][iw]==d[jh][jw]=="." and ih==jh and abs(iw-jw)==1:
                p[i][j]=1
                p[j][i]=1
            if d[ih][iw]==d[jh][jw]=="." and iw==jw and abs(ih-jh)==1:
                p[i][j]=1
                p[j][i]=1


    for i in range(x):
        ih,iw=i//w,i%w
        if d[ih][iw]!=".": continue
        for j in range(x):
            ih,iw=i//w,i%w
            jh,jw=j//w,j%w
            if d[jh][jw]!=".": continue
            for k in range(j+1):
                ih,iw=i//w,i%w
                jh,jw=j//w,j%w
                kh,kw=k//w,k%w
                if d[kh][kw]==".":
                    p[j][k]=min(p[j][k],p[j][i]+p[i][k])
                    p[k][j]=min(p[k][j],p[j][i]+p[i][k])
    ans=0
    for i in p:
        for j in i:
            if j<x+1:
                ans=max(ans,j)
    print(ans)

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

n = int(input())
a = [input().split() for i in range(n)]

l_c = []
count = 0

for i in a:
    ii = a.count(i)
    l_c.append(ii)
    
for i in l_c:
    if i%2 == 1:
        count += 1

print(count)

### FIXED CODE ###

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

count = 0
dic = {}

for i in a:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1

for i in dic.values():
    if i%2 == 1:
        count += 1

print(count)
### BUGGY CODE ###

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

result = 0
for i in range(1,n+1):
  if i // 100 == 0:
    result = i*(100**d)
  else:
    j = 0
    while not(((i+j) //100 == 0)):
      j += 1

    result = (i+j)*(100**d)

print(result)


### FIXED CODE ###

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

result = 0
for i in range(1,n+1):
  if i // 100 == 0:
    result = i*(100**d)
  else:  
    j = 1
    result = (i+j)*(100**d)

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

n=int(input())
a = list(input().split())
a = [int(i) for i in a]
q=int(input())
#bc=[list(map(int,input().split())) for i in range(q)]

for _ in range(q):
  bi,ci=map(int,input().split())
  a=[ci if bi==a[i] else a[i] for i in range(n)]
  #print(a)
  print(sum(a))
  

### FIXED CODE ###

import numpy as np
from collections import Counter as C

n=int(input())
a = list(input().split())
a = [int(i) for i in a]
q=int(input())
bc=[list(map(int,input().split())) for i in range(q)]
bc=np.array(bc).T
b=bc[0]
c=bc[1]

d=C(a)
d2={}
for k,v in d.items():
  d2[k]=k*v

#print(d)
ans=sum(a)
for i in range(q):
  d[c[i]]+=d[b[i]]
  ans+=(c[i]-b[i])*d[b[i]]
  d[b[i]]=0
  print(ans)
### BUGGY CODE ###

from collections import defaultdict
def solve():
	Base = 2000
	MAX = Base*2
	p = 10**9+7
	F = [1]; Finv = [0]*(MAX*2+1)
	for i in xrange(MAX*2): F.append(F[i]*(i+1)%p)
	Finv[MAX*2] = pow(F[MAX*2],p-2,p)
	for i in xrange(MAX*2,0,-1): Finv[i-1] = Finv[i]*i%p
	N = int(raw_input())
	dup = A_MAX = B_MAX = 0
	dp = [[0]*(MAX+2) for i in xrange(MAX+2)]
	goals = defaultdict(int)
	for i in xrange(N):
		A,B = map(int,raw_input().split())
		dup = (dup + F[A*2+B*2]*Finv[A*2]*Finv[B*2]%p)%p
		if A > A_MAX: A_MAX = A
		if B > B_MAX: B_MAX = B
		goals[(Base+A,Base+B)] += 1
		dp[Base-B][Base-A] += 1
	for j in xrange(Base-B_MAX,Base+B_MAX+1):
		for i in xrange(Base-A_MAX,Base+A_MAX+1):
			dp[j+1][i] = (dp[j+1][i] + dp[j][i]) % p
			dp[j][i+1] = (dp[j][i+1] + dp[j][i]) % p
	ans = 0
	for (i,j),v in goals.iteritems():
		ans = (ans + dp[j][i]*v) % p
	print ((ans - dup)*pow(2,p-2,p) + p) % p
solve()

### FIXED CODE ###

from collections import defaultdict
def solve():
	Base = 2000
	MAX = Base*2
	p = 10**9+7
	F = [1]; Finv = [0]*(MAX*2+1)
	for i in xrange(MAX*2): F.append(F[i]*(i+1)%p)
	Finv[MAX] = pow(F[MAX],p-2,p)
	for i in xrange(MAX,0,-1): Finv[i-1] = Finv[i]*i%p
	N = int(raw_input())
	dup = A_MAX = B_MAX = 0
	dp = [[0]*(MAX+2) for i in xrange(MAX+2)]
	goals = defaultdict(int)
	for i in xrange(N):
		A,B = map(int,raw_input().split())
		dup = (dup + F[A*2+B*2]*Finv[A*2]*Finv[B*2])%p
		if A > A_MAX: A_MAX = A
		if B > B_MAX: B_MAX = B
		goals[(Base+A,Base+B)] += 1
		dp[Base-B][Base-A] += 1
	for j in xrange(Base-B_MAX,Base+B_MAX+1):
		for i in xrange(Base-A_MAX,Base+A_MAX+1):
			dp[j+1][i] = (dp[j+1][i] + dp[j][i]) % p
			dp[j][i+1] = (dp[j][i+1] + dp[j][i]) % p
	ans = 0
	for (i,j),v in goals.iteritems():
		ans = (ans + dp[j][i]*v) % p
	print ((ans - dup)*pow(2,p-2,p)+p) % p
solve()
### BUGGY CODE ###

n = int(input())
A = [list(int(x) - 1 for x in input().split()) for _ in range(n)]
B = [0] * n

ans = 1
while True:
    day_set = set()
    for i in range(n):
        if i in day_set or B[i] == n - 1:
            continue
        j = A[i][B[i]]
        if j in day_set or B[j] == n - 1:
            continue
        if A[j][B[j]] == i:
            B[i] += 1
            B[j] += 1
            day_set.add(i)
            day_set.add(j)
            if all(b == n - 1 for b in B):
                print(ans)
                exit()
    if not day_set:
        print(-1)
        exit()
    else:
        ans += 1


### FIXED CODE ###

n = int(input())
A = [list(int(x) - 1 for x in input().split()) for _ in range(n)]
B = [0] * n

ans = 1
stack = [i for i in range(n)]
while True:
    day_set = set()
    next_stack = []
    while stack:
        i = stack.pop()
        if i in day_set or B[i] >= n - 1:
            continue
        j = A[i][B[i]]
        if j in day_set or B[j] >= n - 1:
            continue
        if A[j][B[j]] == i:
            B[i] += 1
            B[j] += 1
            day_set.add(i)
            day_set.add(j)
            next_stack += [i, j]
            if all(b >= n - 1 for b in B):
                print(ans)
                exit()

    if not day_set:
        print(-1)
        exit()
    ans += 1
    stack = next_stack
### BUGGY CODE ###

def main():
    N=int(input())
    L=list(map(int,input().split()))
    L_i,L_j=[],[]
    d, s = [0]*N, 0
    cnt=0
    
    for i, j in enumerate(L):
        L_i.append(i+j)
        L_j.append(i-j)

    for i in L_j:
        cnt += L_i.count(i)
        
    print(cnt)
main()

### FIXED CODE ###

def main():
    N=int(input())
    L=list(map(int,input().split()))
    L_i,L_j=[],[]
    L_memo = [0]*N
    cnt=0
    for i, j in enumerate(L):
        if i+j<N:
            L_memo[i+j]+=1
        if i-j>0:
            cnt+=L_memo[i-j]        
    print(cnt)
main()
### BUGGY CODE ###

n,k = list(map(int,input().split()))
m = 10**9+7
def inv(x):
  m = 10**9+7
  t = x
  y = 1
  while True:
    if t == 1:
      break
    y *= m // t
    t = m % t
    y *= -1
    y %= m
  return y
def c(x,y):
  t = 1
  for j in range(y):
    t *= x-j
    t *= inv(j+1)
  return t
for i in range(1,k+1):
  print( (c(k-1,i-1) * c(n-k+1,i)) % m )

### FIXED CODE ###

n,k = list(map(int,input().split()))
m = 10**9+7
a = 1
b = n-k+1
print(a*b%m)
for i in range(2,k+1):
  a *= k+1-i
  a //= i-1
  at = a%m
  b *= n-k+2-i
  b //= i
  bt = b%m
  print(at*bt%m)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()

A = A[::-1]
B = B[::-1]
C = C[::-1]

anslist = []

for i in range(len(A)):
    if i > k:
        break
    for j in range(len(B)):
        if i * j > k:
            break
        for l in range(len(C)):
            if i * j * l > k:
                break
            anslist.append(A[i] + B[j] + C[l])

anslist.sort()

anslist = anslist[::-1]

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


### FIXED CODE ###

x, y, z, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()

A = A[::-1]
B = B[::-1]
C = C[::-1]

anslist = []

for i in range(len(A)):
    if i > k:
        break
    for j in range(len(B)):
        if i * j > k:
            break
        for l in range(len(C)):
            if (i + 1) * (j + 1) * (l + 1) > k:
                break
            anslist.append(A[i] + B[j] + C[l])

anslist.sort()

anslist = anslist[::-1]

for i in range(k):
    print(anslist[i])
### BUGGY CODE ###

##
s = input()
q = int(input())
for i in range(q):
    x = input().split()
    if x[0] == "1":
        s = s[::-1]
    else:
        if x[1] == "1":
            s = x[2] + s
        else:
            s = s + x[2]

print(s)

### FIXED CODE ###

from collections import deque
 
S = input()
L = deque([])
for c in S:
    L.append(c)
Q = int(input())
flag = 1
for _ in range(Q):
    q = list(input().split())
    if q[0] == "1":
        flag *= -1
    else:
        F = q[1]
        if F == "1":
            if flag == 1:
                L.appendleft(q[2])
            else:
                L.append(q[2])
        else:
            if flag == 1:
                L.append(q[2])
            else:
                L.appendleft(q[2])
if flag == 1:
    print("".join(map(str, L)))
else:
    L.reverse()
    print("".join(map(str, L)))
### BUGGY CODE ###

import math
import collections
def main():

    N = int(input())
    d = collections.defaultdict(int)

    ans = 0
    for i in range(1, int(math.sqrt(N))+1):
        p = i
        while p <= N:
            d[p] += 1
            if p // i > int(math.sqrt(N)):
                d[p] += 1
            p += i

    for i in range(1, N+1):
        ans += i * d[i]

    return ans

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


### FIXED CODE ###

import math
import collections
def main():

    N = int(input())
    d = dict()
    for i in range(1, N+1):
        d[i] = 0

    ans = 0
    for i in range(1, N+1):
        p = N//i
        ans += p * (p+1)//2 * i
    return ans

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

def resolve():
    n, m = map(int, input().split())
    li_broken = [int(input()) for _ in range(m)]
    dp = [0] * (n + 2)

    for i in reversed(range(n + 1)):

        if i == n:
            dp[i] = 1
            continue

        if i in li_broken:
            dp[i] = 0
            continue

        dp[i] = (dp[i+1] + dp[i+2]) % 1000000007

    print(dp[0])
    
resolve()

### FIXED CODE ###

def step(n):
  if n == 0:
      return 1
  steps = [0 for i in range(n + 2)]
  steps[1] = 1
  steps[2] = 2
  for i in range(3, n + 1):
    steps[i] = steps[i - 1] + steps[i - 2]
  return steps[n]

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

a.append(n)

sum = 1

for i in range(m + 1):

  if i == 0:
    sum *= step(a[i] - 1)
    continue
  
  elif i == m:
    sum *= step(a[m] - a[m-1] -1)
    
  elif a[i] - a[i-1] == 1:
    sum = 0
    break

  else:
    sum *= step(a[i] - a[i-1] -2)
    
if m == 0:
  sum = step(n)

print(sum % 1000000007)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)

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


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.per = list(range(n))
        self.point = n*(n-1) // 2
        self.counts = [1]*n

    def root(self, x):
        if self.per[x] == x:
            return x
        return self.root(self.per[x])

    def union(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return False
        self.per[rx] = ry
        self.point -= self.counts[ry] * self.counts[rx]
        self.counts[ry] += self.counts[rx]
        self.counts[rx] = 0

    def is_same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry


u = UnionFind(N)
results = []
for a, b in AB[::-1]:
    results.append(u.point)
    x, y = a-1, b-1
    u.union(x, y)

# print(*results[::-1])
for r in results[::-1]:
    print(r)


### FIXED CODE ###

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


class UnionFind:
    def __init__(self, n):
        self.par = [-1]*n
        self.size = [1]*n
        self.point = n*(n-1) // 2

    def root(self, x):
        if self.par[x] < 0:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return False
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        self.point -= self.size[rx]*self.size[ry]
        self.size[rx] += self.size[ry]
        self.par[ry] = rx
        return True

    def is_same(self, x, y):
        rx, ry = self.root(x), self.root(y)
        return rx == ry

    def get_size(self, x):
        return self.size[self.root(x)]


uf = UnionFind(N)
results = []
for a, b in AB[::-1]:
    results.append(uf.point)
    x, y = a-1, b-1
    uf.unite(x, y)

print(*results[::-1], sep="\n")
### BUGGY CODE ###

import re
N,Q=[int(e) for e in input().split(' ')]
S=input()

qs=[]
for i in range(Q):
    qs.append([int(e) for e in input().split(' ')])

for q in qs:
    substr=S[q[0]-1:q[1]]
    print(len(re.findall('AC',substr)))

### FIXED CODE ###

import re
N,Q=[int(e) for e in input().split(' ')]
S=input()
qs=[]
for i in range(Q):
    qs.append([int(e) for e in input().split(' ')])

sts=[0]*N
for i in range(N):
    if i>0:
        if S[i-1:i+1]=='AC':
            sts[i]=sts[i-1]+1
        else:
            sts[i]=sts[i-1]
for q in qs:
    print(sts[q[1]-1]-sts[q[0]-1])
### BUGGY CODE ###

import copy

def com(n,r,m):
    #a = math.factorial(n)%m
    a = 1
    for i in range(1,n+1):
        a *= i
        a %= m
    A = pow(a,m-2,m)
    
    
    b= copy.copy(A)   
    for i in range(n,r,-1):
        b = (b*i)%m
    
    c = copy.copy(A)
    for i in range(n,n-r,-1):
        c = (c*i)%m
       
    return (a*b*c)%m

def main():
    k = int(input())
    s = input()
    mod = 10**9+7
    z = [1]
    for i in range(1,k+1):
        y = z[-1]*26
        z.append(y%mod)
    #print(z)
    l = len(s)

    ans = 0
    p = 1   #pow(25,i-len(s),mod)
    q = z[k]
    bai = 1
    for i in range(l,l+k+1):
        base = p*q   #pow(26,len(s)+k-i,mod)
        #base = pow(25,i-len(s),mod) * pow(26,len(s)+k-i,mod)
        #bai = r
        #bai = com(i-1,len(s)-1,mod)
        #print(i,len(s),base,bai)
        ans += base*bai
        ans %= mod
        p *= 25
        q = z[l+k-i-1]
        bai = bai*i*pow(i-l+1,mod-2,mod)
    print(ans)
    
if __name__=="__main__":
    main()

### FIXED CODE ###

import copy

def com(n,r,m):
    #a = math.factorial(n)%m
    a = 1
    for i in range(1,n+1):
        a *= i
        a %= m
    A = pow(a,m-2,m)
    
    
    b= copy.copy(A)   
    for i in range(n,r,-1):
        b = (b*i)%m
    
    c = copy.copy(A)
    for i in range(n,n-r,-1):
        c = (c*i)%m
       
    return (a*b*c)%m

def main():
    k = int(input())
    s = input()
    mod = 10**9+7
    z = [1]
    for i in range(1,k+1):
        y = z[-1]*26
        z.append(y%mod)
    l = len(s)

    N = k+2
    inv_t = [0]+[1]
    for i in range(2,N):
        inv_t.append(inv_t[mod % i] * (mod - int(mod / i)) % mod)
    #print(inv_t)
    
    ans = 0
    p = 1   #pow(25,i-len(s),mod)
    #q = z[k]
    bai = 1
    for i in range(l,l+k+1):
        #base = p*q   #pow(26,len(s)+k-i,mod)
        #base = pow(25,i-len(s),mod) * pow(26,len(s)+k-i,mod)
        #bai = r
        #bai = com(i-1,len(s)-1,mod)
        #print(i,len(s),base,bai)
        ans += p*z[l+k-i]*bai
        ans %= mod
        p *= 25
        p %= mod
        #q = z[l+k-i-1]
        bai = bai*i*inv_t[i+1-l]
        bai %= mod
    print(ans)
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

s = input()
q = int(input())
for i in range(q):
    query = [i for i in input().split()]
    if query[0] == "1":
        s = "".join(list(reversed(s)))
    else:
        if query[1] == "1":
            s = query[2] + s
        else:
            s = s + query[2]

print(s)

### FIXED CODE ###

s = input()
q = int(input())
status = 1
top = []
bottom = []
for i in range(q):
    query = [i for i in input().split()]
    if query[0] == "1":
        status *= -1
    else:
        if (query[1] == "1" and status == 1) or (query[1] == "2" and status == -1):
            top.append(query[2])
        else:
            bottom.append(query[2])

tmp = "".join(top[::-1]) + s + "".join(bottom)
print(tmp if status == 1 else tmp[::-1])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

import networkx as nx

YES = "Yes"  # type: str
NO = "No"


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    G = nx.Graph()
    G.add_nodes_from([1+n for n in range(N)])

    G.add_edges_from([(a,b) for a,b in zip(A,B)])

    paths = nx.predecessor(G, 1)

    print(YES)

    ans_list = []
    for key, val in sorted(paths.items()):
        if key != 1:
            print(val[0])
            # ans_list.append((key,val[0]))

    # ans_list.sort(key=lambda x: x[0])
    # for key, val in ans_list:
    #     print(val)
    return


# Generated by 1.1.7.1 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
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

YES = "Yes"  # type: str


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    dq = deque([])
    traversed = [False for _ in range(N+1)]
    ans = [None for _ in range(N+1)]

    G = {n : set([]) for n in range(1, N+1)}
    for a, b in zip(A,B):
        G[a].add(b)
        G[b].add(a)

    dq.append(1)
    traversed[1] = True

    while dq:
        s = dq.popleft()

        for node in G[s]:
            if not traversed[node]:
                dq.append(node)
                traversed[node] = True
                

                ans[node] = s

    print(YES)
    for s in ans:
        if s != None:
            print(s)
    return


# Generated by 1.1.7.1 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
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

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

S = input()
a = len(S)
mod = 0
L = [0]*2019 #余りの列
L[0] = 1
for i in range(a-1,-1,-1):
    mod = (int(S[i])*(10**(a-1-i))+mod) %2019
    L[mod] += 1  
ans = 0
for i in L:
  ans += i*(i-1)//2
print(ans)

### FIXED CODE ###

S = input()
a = len(S)
mod = 0
ten = 1
L = [0]*2019 #余りの列
L[0] = 1
for i in range(a-1,-1,-1):
    mod = (int(S[i])*(ten)+mod) %2019
    L[mod] += 1
    ten = (ten*10)%2019
ans = 0
for i in L:
  ans += i*(i-1)//2
print(ans)