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

N = int(input())
a = list(map(int, input().split()))
suma = [0, a[0]]
for i in range(1, N):
    suma.append(suma[-1] + a[i])
inf = float("inf")
dp = [[-1 for i in range(N+1)] for j in range(N+1)]
# dp[i][j]は区間[i, j)での最小のコスト

# メモ化再帰
def rec(l, r):
    if r - l == 0:
        dp[l][r] = 0
        return 0
    elif r - l == 1:
        dp[l][r] = a[l]
        return a[l]

    # r - l >= 2である
    # iを媒介にdpを貪欲に探索する。
    res = inf
    for pos in range(l+1, r):
        tmp = 0
        if pos - l > 1:
            tmp += rec(l, pos) + suma[pos] - suma[l]
        else:
            tmp += rec(l, pos)
        if r - pos > 1:
            tmp += rec(pos, r) + suma[r] - suma[pos]
        else:
            tmp += rec(pos, r)
        res = min(res, tmp)
    dp[l][r] = res
    return res

print(rec(0, N))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)
N = int(input())
a = list(map(int, input().split()))
suma = [0, a[0]]
for i in range(1, N):
    suma.append(suma[-1] + a[i])
inf = float("inf")
dp = [[-1 for i in range(N+1)] for j in range(N+1)]
# dp[i][j]は区間[i, j)での最小のコスト

# メモ化再帰
def rec(l, r):
    if r - l == 0:
        dp[l][r] = 0
        return 0
    elif r - l == 1:
        dp[l][r] = a[l]
        return a[l]

    if dp[l][r] != -1:
        return dp[l][r]

    # r - l >= 2である
    # iを媒介にdpを貪欲に探索する。
    res = inf
    for pos in range(l+1, r):
        tmp = 0
        if pos - l > 1:
            tmp += rec(l, pos) + suma[pos] - suma[l]
        else:
            tmp += rec(l, pos)
        if r - pos > 1:
            tmp += rec(pos, r) + suma[r] - suma[pos]
        else:
            tmp += rec(pos, r)
        res = min(res, tmp)
    dp[l][r] = res
    return res

print(rec(0, N))
### BUGGY CODE ###

def lcs(str1, str2):
    '''文字列str1, str2の最長共通部分列(Lowest Common Subsequence, LCS)を求める
    計算量O(len(str1)*len(str2))  
    '''
    dp = [[0]*(len(str2) + 1) for _ in range(len(str1) + 1)]
    for i in range(len(str1)):
        for j in range(len(str2)):
            if str1[i] == str2[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
    return dp[len(str1)][len(str2)]

n = int(input())
s = input()
ans = 0
for i in range(1000):
    t = ("000"+str(i))[::-1][0:3][::-1]
    num = lcs(t, s)
    if num == 3:
        ans += 1
print(ans)


### FIXED CODE ###

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

next_ = [[-1]*(n+1) for i in range(10)]
for num in range(10):
    pos = -1
    for i in range(n)[::-1]:
        next_[num][i] = pos
        if num == int(s[i]):
            pos = i

start = [-1] * 10
for num in range(10):
    for i in range(n)[::-1]:
        if num == int(s[i]):
            start[num] = i
ans = 0
for i in range(1000):
    t = ("000"+str(i))[::-1][0:3][::-1]
    pos = start[int(t[0])]
    for i in t[1:]:
        pos = next_[int(i)][pos]
    if pos != -1:
        ans += 1
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
l=[]
for _ in range(m):
    l.append(int(input()))
#print(l)
dp=[0]*(n+1)
dp[0]=1
if 1 not in l:
    dp[1]=1

for i in range(2,n+1):
    if i in l:
        dp[i]=0
    else:
        dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%1000000007)

### FIXED CODE ###

n,m=map(int,input().split())
a=[-1]
for i in range(m):
    s=int(input())
    a.append(s)  
a.append(n+1)
if 1 in a:
    a=a[1:]
if n-1 in a:
    a=a[:-1]
b=[]
for i in range(len(a)-1):
    b.append(a[i+1]-a[i]-2)
l=[1,1,2]
for i in range(3,n+1):
    l.append(l[i-2]+l[i-1])
ans=1
#print(a,b,l)
for i in range(len(b)):
    if b[i]<0:
        print(0)
        break
    else:
        ans*=l[b[i]]%1000000007
else:
    print(ans%1000000007)
### BUGGY CODE ###

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

### FIXED CODE ###

s = input()
q = int(input())
qs = [input().split() for i in range(q)]
n = False
left= right = ""
for operation in qs:
    if operation[0] == '1':
        n = not n
    if operation[0] == '2':
        t , f, c = operation
        f = int(f)
        if n:
            f = 1 if f != 1 else 2
        if f == 1:
            left=c+left
        elif f == 2:
            right+=c
s = left+s+right
print(s[::-1] if n else s)
### BUGGY CODE ###

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


b = []
i = 0
while k != n+1:
    total = 1
    for j in range(i, k):
        total *= a[j]
    b.append(total)
    i += 1
    k += 1
l = len(b)
#print(b)
for i in range(l-1):
    if b[i] < b[i+1]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

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

for i in range(n-k):
    if a[i] < a[i+k] :
        print('Yes')
    else :
        print('No')
### BUGGY CODE ###

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

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

l.sort()
cnt = 0
lst=[]

for n,i in enumerate(l):
    for m,j in enumerate(l[n+1:],n+1):

        lst = list([c for c in set(l[m+1:]) if c<=i+j-1])
        cnt += len(lst)
        
print(cnt)


### FIXED CODE ###

import sys
from bisect import bisect_left
from itertools import combinations 

input = sys.stdin.readline
 
N = int(input())
l= list(map(int, input().split()))
 
l.sort()
cnt = 0
 
for n,i in enumerate(l[:N-2]):
    for m,j in enumerate(l[n+1:N-1],n+1):
        cnt += max(0,bisect_left(l,i+j)-(m+1)) 
        
print(cnt)
### BUGGY CODE ###

n=int(input())
s=input()
min=99999999
for i in range(n):
    left=s[:i:].count("W")
    right=s[i+1:].count("E")
    if min>left+right:
        min=left+right
print(min)


### FIXED CODE ###

n=int(input())
s=input()
w=[0]*n
e=[0]*n
for i in range(n):
    if s[i]=="W":
        if i==0:
           w[i]+=1
        else:
            w[i]+=w[i-1]+1
            e[i]+=e[i-1]
    else:
        if i==0:
            e[i]+=1
        else:
            e[i]+=e[i-1]+1
            w[i]+=w[i-1]
min=9999999
for i in range(n):
    if i==0:
        num=e[n-1]-e[i]

    else:
        num=w[i-1]+e[n-1]-e[i]
    if min>num:
        min=num
print(min)
### BUGGY CODE ###

N, Q = map(int,input().split())
G = [[] for i in range(N+ 1)]
ANS = [0] * (N + 1)
for _ in range(N - 1):
    a , b = map(int,input().split())
    G[a].append(b)
for _ in range(Q):
    p, x =map(int,input().split())
    ANS[p] += x
que=[1]
while que:
    node = que.pop(0)
    ans = ANS[node]
    for child in G[node]:
        ANS[child] += ans
        que.append(child)
for i in range(1, N + 1):
    print(ANS[i])

### FIXED CODE ###

N, Q = map(int,input().split())
G = [[] for i in range(N+ 1)]
ANS = [0] * (N + 1)
for _ in range(N - 1):
    a , b = map(int,input().split())
    G[a].append(b)
for _ in range(Q):
    p, x =map(int,input().split())
    ANS[p] += x
from collections import deque
que=deque([])
que.append(1)
while que:
    node = que.pop()
    ans = ANS[node]
    for child in G[node]:
        ANS[child] += ans
        que.append(child)
for i in range(1, N + 1):
    print(ANS[i])
### BUGGY CODE ###

from collections import defaultdict
# from sys import stdin
# input = stdin.readline


def main():
  # S = input()[-1:0:-1]
  S = input()[::-1]
  MOD = 2019

  dp = [0]*(len(S)+1)
  dp[0] = 0

  ten = 1
  for i, s in enumerate(S):
    dp[i] = (dp[i-1] + ten*int(s)) % MOD
    ten *= 10

  dic = defaultdict(int)
  sum_ = 0
  for sup in dp:
    if sup in dic:
      sum_ += dic[sup]
    dic[sup] += 1

  print(sum_)


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


### FIXED CODE ###

def main():
  # S = input()[-1:0:-1]
  S = input()[::-1]
  MOD = 2019

  # dp = [0]*(len(S)+1)
  # dp[0] = 0
  dic = [0]*2019
  dic[0] = 1

  ten = 1
  pre = 0
  for i, s in enumerate(S):
    # dp[i] = (dp[i-1] + ten*int(s)) % MOD
    pre = (pre + ten*int(s)) % MOD
    dic[pre] += 1
    ten *= 10
    ten %= MOD

  sum_ = 0
  # for sup in dp:
  #   dic[sup] += 1

  for v in dic:
    sum_ += v*(v-1)//2

  print(sum_)


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

N, M, Q = map(int, input().split())
S=[[0 for i in range(4)] for j in range(Q)]
for i in range(Q):
    inputS=list(map(int,input().split()))
    S[i][0]=inputS[0]
    S[i][1]=inputS[1]
    S[i][2]=inputS[2]
    S[i][3]=inputS[3]
S2=[]
maxNum=0
for a in range(11):
    for b in range(a,11):
        for c in range(b,11):
            for d in range(c,11):
                for e in range(d,11):
                    for f in range(e,11):
                        for g in range(f,11):
                            for h in range(g,11):
                                for i in range(h,11):
                                    for j in range(i,11):
                                        S2.append([a,b,c,d,e,f,g,h,i,j])
                                        
                                        count=0
                                        for k in range(Q):
                                            if S2[len(S2)-1][S[k][1]-1]-S2[len(S2)-1][S[k][0]-1]==S[k][2]:
                                                count+=S[k][3]
                                        maxNum=max(maxNum,count)

print(maxNum)


### FIXED CODE ###

N, M, Q = map(int, input().split())
S=[[0 for i in range(4)] for j in range(Q)]
for i in range(Q):
    inputS=list(map(int,input().split()))
    S[i][0]=inputS[0]
    S[i][1]=inputS[1]
    S[i][2]=inputS[2]
    S[i][3]=inputS[3]
S2=[]
maxNum=0
for a in range(1,M+1):
    for b in range(a,M+1):
        for c in range(b,M+1):
            for d in range(c,M+1):
                for e in range(d,M+1):
                    for f in range(e,M+1):
                        for g in range(f,M+1):
                            for h in range(g,M+1):
                                for i in range(h,M+1):
                                    for j in range(i,M+1):
                                        S2=[a,b,c,d,e,f,g,h,i,j]
                                        count=0
                                        for k in range(Q):
                                            if S2[S[k][1]-1]-S2[S[k][0]-1]==S[k][2]:
                                                count+=S[k][3]
                                        maxNum=max(maxNum,count)
                                       
    
print(maxNum)
### BUGGY CODE ###

import math
A,B,N = map(int,input().split())
maxi = -100000
for i in range(0,N+1):
    maxi = max(math.floor(A*i/B)-A*math.floor(i/B),maxi)
print(maxi)


### FIXED CODE ###

import math
from math import floor
A,B,N = map(int,input().split())
def f(x):
  return floor(A*x/B) - A*floor(x/B)
print(f(min(B-1,N)))
### BUGGY CODE ###

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

import sys

sys.setrecursionlimit(10 ** 7)

n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
px = [list(map(int, input().split())) for _ in range(q)]

graph = [[] for _ in range(n + 1)]
for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (n + 1)
for p, x in px:
    value[p] += x


def dfs(v, p, add):
    value[v] += add
    for x in graph[v]:
        if x == p:
            continue
        dfs(x, v, value[v])


dfs(1, 0, 0)

ans = value[1:]
print(*ans)


### FIXED CODE ###

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

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
px = [list(map(int, input().split())) for _ in range(q)]

graph = [[] for _ in range(n + 1)]
for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (n + 1)
for p, x in px:
    value[p] += x


def dfs(v, p, add):
    value[v] += add
    for x in graph[v]:
        if x == p:
            continue
        dfs(x, v, value[v])


dfs(1, 0, 0)

ans = value[1:]
print(*ans)
### BUGGY CODE ###

import fractions

N = int(input())
ints = list(map(int, input().split()))
ints.sort()

gcd = 0
result = 1
holed_ints = []
for i in range(N):
    holed_ints = ints[:i] + ints[i+1:]
    gcd = 0
    for j in range(N-1):
        gcd = fractions.gcd(gcd, holed_ints[j])
        if gcd == 1:
            break
    if gcd > result:
        result = gcd

print(result)

### FIXED CODE ###

import fractions

integral_count = int(input())
blackboard_integers = list(map(int, input().split()))

gcd_integers = list(set(blackboard_integers))

gcd = 0
result = 1
for i in range(len(gcd_integers)):
    gcd = 0
    if blackboard_integers.count(gcd_integers[i]) >= 2:
        for n in gcd_integers:
            gcd = fractions.gcd(gcd, n)
    else:
        for n in gcd_integers[:i]:
            gcd = fractions.gcd(gcd, n)
        for n in gcd_integers[i+1:]:
            gcd = fractions.gcd(gcd, n)
    if gcd > result:
        result = gcd

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

# -*- coding: utf-8 -*-
n, m = map(int, input().split())
a = list(map(int, input().split()))

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

a.sort(reverse=True)
print(sum(a[:n]))

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import defaultdict
n, m = map(int, input().split())
a = list(map(int, input().split()))

cards = defaultdict(int)
for num in a:
    cards[num] += 1

for _ in range(m):
    b, c = map(int, input().split())
    cards[c] += b

count = n
ans = 0
for key, val in sorted(cards.items(), key=lambda x: -x[0]):
    if count - val < 0:
        ans += key * count
        break
    else:
        ans += key * val
        count -= val
print(ans)
### BUGGY CODE ###

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

import bisect
#a=[0,2,3,4,67,8]
#a.sort()
#bisect.bisect_left(a, 4) #被ったら左側のindexを返す
#bisect.bisect_right(a, 4)#被ったら右側のindexを返す

color=[-1]

for aa in a:
    i=bisect.bisect_left(color, aa)
    if i==0:
        color.insert(0,aa)
        #print("insert")
    else:
        color[i-1]=aa
        #print("update")
    #print(color,aa) 
print(len(color))


### FIXED CODE ###

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

import bisect
#a=[0,2,3,4,67,8]
#a.sort()
#bisect.bisect_left(a, 4) #被ったら左側のindexを返す
#bisect.bisect_right(a, 4)#被ったら右側のindexを返す

color=[1]
lencolor=1
for aa in a:
    aa=-1*aa
    i=bisect.bisect_right(color, aa)
    if i==lencolor:
        color.append(aa)
        lencolor+=1
        #print("insert")
    else:
        color[i]=aa
        #print("update")
    #print(color,aa) 
print(lencolor)
### BUGGY CODE ###

MOD = 998244353
def part_sum(a,A):
  
  #初期化
  N=len(a)
  dp=[[[0 for i in range(N+1)] for i in range(A+1)] for j in range(N+1)]
  dp[0][0][0]=1

  #DP
  for i in range(N):
    for j in range(A+1):
      for k in range(N):
        if a[i]<=j: #i+1番目の数字a[i]を足せるかも
            dp[i+1][j][k+1]=dp[i][j-a[i]][k]+ dp[i][j][k+1]% MOD
        else: #入る可能性はない
            dp[i+1][j][k]=dp[i][j][k]%MOD
  return dp[N][A]



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

ans = 0
sm = part_sum(A,S)
for n in range(N+1):
    p = pow(2,N-n,MOD)
    ans += p*sm[n]
    ans %= MOD
print (ans)

### FIXED CODE ###


def solve(N,S,A):
    dp = [[0]*(S+1) for _ in range(N+1)]
    dp[0][0] = 1
    mod = 998244353
    for i, a in enumerate(A, 1):
        for s in range(S+1):
            if s-a >= 0:
                dp[i][s] = (dp[i-1][s] * 2 + dp[i-1][s-a]) % mod
            else:
                dp[i][s] = dp[i-1][s] * 2 % mod
    print(dp[N][S])

N, S = map(int, input().split())
A = list(map(int, input().split()))
solve(N,S,A)
### BUGGY CODE ###

H, N = map(int, input().split())
ATK = []

for i in range(N):	
  ATK.append(list(map(int, input().split())))
mp_min = [0]
for hp in range(1, H+1):
  mp_min.append(min([mp_min[max(0, hp-ATK[i][0])] + ATK[i][1] for i in range(N)]))

 # print(mp_min)

print(mp_min[-1])


### FIXED CODE ###

H, N = map(int, input().split())
ATK = []

for i in range(N):	
  ATK.append(list(map(int, input().split())))
mp_min = [0]
for hp in range(1, H+1):
  mp_min.append(min([mp_min[max(0, hp-ATK[i][0])] + ATK[i][1] for i in range(N)]))

 # print(mp_min)

print(mp_min[-1])
### BUGGY CODE ###

import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a.sort()
if sum(a)<=k:
    print(0)
    exit()
f.sort(reverse=True)
l=0
r=10**12
x=(r+l)//2
a=np.array(a)
f=np.array(f)
def check(x):
    p=np.sum(np.maximum(np.array([0]*n),a-x//f))
    if p>k:
        return False
    else:
        return True
while l<r:
    if check(x):
        r=x
        x=(r+l)//2
    else:
        l=x
        x=(r+l)//2
print(r)


### FIXED CODE ###

import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)

a = []
f = []
n = 0

def rec(l, r, k):
    if l+1 < r:
        mid = (l + r) // 2
        s = 0
        for i in range(n):
            s += max(a[i] - mid // f[i], 0)
        if s <= k:
            return rec(l, mid, k)
        else:
            return rec(mid, r, k)
    else:
        return r

def main():
    global a, f, n
    n, k = map(int, input().strip().split())
    a = list(map(int, input().strip().split()))
    f = list(map(int, input().strip().split()))
    a = sorted(a)
    f = sorted(f, reverse=True)
    print(rec(-1, 10**12, k))

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

R,G,B,N = map(int, input().split())

ans = 0
for i in range(N//R+1):
    if i*R > N:
        break
    for j in range(N//G+1):
        if i*R + j*G > N:
            break
        for k in range(N//B+1):
            if i*R + j*G + k*B > N:
                break
            elif i*R + j*G + k*B == N:
                ans += 1

print(ans)

### FIXED CODE ###

R,G,B,N = map(int, input().split())

ans = 0
L = sorted([R,G,B], reverse=True)
for i in range(N//L[0]+1):
    for j in range((N-i*L[0])//L[1]+1):
        if (N-i*L[0]-j*L[1])%L[2] == 0:
                ans += 1

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

def main():

    L = input()
    mod = pow(10, 9) + 7
    n = len(L)
    count = dict()
    prefix = 0
    for c in L:
        temp = dict()
        for v in count:
            temp[v+1] = temp.get(v+1, 0) + count[v]
            temp[v] = temp.get(v, 0) + count[v]
        if c == "1":
            temp[prefix] = temp.get(prefix, 0) + 1
            prefix += 1
        count = temp
    count[prefix] = count.get(prefix, 0) + 1

    pows = [1]
    for l in range(1, len(L)+1):
        pows.append(pows[-1]*2)
    ans = 0
    for v in count:
        ans += pows[v] * count[v]
        ans %= mod
    return ans

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

### FIXED CODE ###

def main():

    L = input()
    mod = pow(10, 9) + 7
    n = len(L)
    dp1 = [0 for _ in range(n+1)]
    dp2 = [0 for _ in range(n+1)]
    dp2[0] = 1
    for i in range(n):
        if L[i] == "0":
            dp1[i+1] = dp1[i] * 3
            dp2[i+1] = dp2[i]
        else:
            dp1[i+1] = dp1[i] * 3 + dp2[i]
            dp2[i+1] = dp2[i] * 2
        dp1[i+1] %= mod
        dp2[i+1] %= mod
    # print(dp1)
    # print(dp2)
    return (dp1[n] + dp2[n]) % mod

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

def main():
  n=int(input())
  s=list(input())
  q_=int(input())
  q=[input().split() for _ in range(q_)]
  class BIT:
    def __init__(self, n):
      self.n = n
      self.data = [0]*(n+1)
      self.el = [0]*(n+1)
    def sum(self, i):
      s = 0
      while i > 0:
        s += self.data[i]
        i -= i & -i
      return s
    def add(self, i, x):
      # assert i > 0
      self.el[i] += x
      while i <= self.n:
        self.data[i] += x
        i += i & -i
    def get(self, i, j=None):
      if j is None:
        return self.el[i]
      return self.sum(j) - self.sum(i)

  a2n = lambda c: ord(c) - ord('a')
  d=[BIT(n) for _ in range(26)]
  di=[0]*26
  for i in range(1,n+1):
    d[a2n(s[i-1])].add(i,1)
  for qi in q:
    if qi[0]=='1':
      i=int(qi[1])
      c=a2n(qi[2])
      si=a2n(s[i-1])
      d[c].add(i,1)
      d[si].add(i,-1)
      s[i-1]=qi[2]
    else:
      ans=0
      l,r=int(qi[1]),int(qi[2])
      for i in range(26):
        ls=d[i].sum(l-1)
        rs=d[i].sum(r)
        ans+=1 if rs-ls>0 else 0
      print(ans)
if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())


### FIXED CODE ###

def main():
  n=int(input())
  s=list(input())
  q_=int(input())
  q=[input().split() for _ in range(q_)]
  class BIT:
    def __init__(self, n):
      self.n = n
      self.data = [0]*(n+1)
      self.el = [0]*(n+1)
    def sum(self, i):
      s = 0
      while i > 0:
        s += self.data[i]
        i -= i & -i
      return s
    def add(self, i, x):
      # assert i > 0
      self.el[i] += x
      while i <= self.n:
        self.data[i] += x
        i += i & -i
    def get(self, i, j=None):
      if j is None:
        return self.el[i]
      return self.sum(j) - self.sum(i)

  a2n = lambda c: ord(c) - ord('a')
  d=[BIT(n) for _ in range(26)]
  di=[0]*26
  for i in range(1,n+1):
    d[a2n(s[i-1])].add(i,1)
  for qi in q:
    if qi[0]=='1':
      i=int(qi[1])
      c=a2n(qi[2])
      si=a2n(s[i-1])
      d[c].add(i,1)
      d[si].add(i,-1)
      s[i-1]=qi[2]
    else:
      ans=0
      l,r=int(qi[1]),int(qi[2])
      for i in range(26):
        ls=d[i].sum(l-1)
        rs=d[i].sum(r)
        ans+=1 if rs-ls>0 else 0
      print(ans)
if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())
### BUGGY CODE ###

K = int(input())
def gcd(a, b):
    c = 1
    for i in range(1, min([a+1, b+1]))[::-1]:
        if a%i==0 and b%i==0:
            c = i
            break
        else:
            continue
    return c

count = 0
temp = list()
for n in range(1, K+1):
    for m in range(1, K+1):
        temp.append(gcd(n, m))
for l in range(1, K+1):
    for j in range(len(temp)):
        p = gcd(l, temp[j])
        count += p
print(count)

### FIXED CODE ###

K = int(input())
def gcd(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        r = a%b
        a = b
        b = r
    return a
count = 0
temp = list()
for n in range(1, K+1):
    for m in range(1, n):
        temp.append(gcd(n, m))
for l in range(1, K+1):
    for j in range(len(temp)):
        p = gcd(l, temp[j])
        count += 2 * p
    for k in range(1, K+1):
        q = gcd(l, k)
        count += q
print(count)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

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

dp = [[[0] * 4 for _ in range(C)] for _ in range(R)]
dp[0][0][1] = goods[0][0]
for i in range(R):
    for j in range(C):
        if i < R - 1:
            dp[i+1][j][0] = max(dp[i+1][j][0], max(dp[i][j]))
            dp[i+1][j][1] = max(dp[i+1][j][1], max(dp[i][j]) + goods[i+1][j])
        
        if j < C - 1:
            for k in range(4):
                dp[i][j+1][k] = max(dp[i][j+1][k], dp[i][j][k])
            for k in range(3):
                dp[i][j+1][k+1] = max(dp[i][j+1][k+1], dp[i][j][k] + goods[i][j+1])

print(max(dp[R-1][C-1]))

### FIXED CODE ###

R, C, K = map(int,input().split())
MAP = [[0 for i in range(C)] for j in range(R)]
DP = [[[0 for i in range(C+1)] for j in range(4)] for k in range(R+1)]
 
for _ in range(K):
    r, c, v = map(int,input().split())
    MAP[r-1][c-1] = v
 
for i in range(R):
    for j in range(4):
        for k in range(C):
            DP[i+1][j][k+1] = max(DP[i][3][k+1], DP[i+1][j][k])
            if j == 0:
                continue
            v = MAP[i][k]
            if v == 0:
                continue
            DP[i+1][j][k+1] = max(DP[i+1][j][k+1], max(DP[i][3][k+1], DP[i+1][j-1][k]) + v)

print(DP[R][3][C])