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

import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

r,c,k = map(int,readline().split())
items = [[0]*c for _ in range(r)]
for i in range(k):
    a,b,v = map(int,readline().split())
    a,b = a-1,b-1
    items[a][b] = v

dp = [[[0]*4 for i in range(c+1)] for j in range(r+1)]

#process1
#移動は→↓の２通りのみなので、その方向に探索していけば良い。
for i in range(1,r+1):
    for j in range(1,c+1):
        if items[i-1][j-1]:
            dp[i][j][0] = max(max(dp[i-1][j]),dp[i][j-1][0])
            dp[i][j][1] = max(max(dp[i-1][j])+items[i-1][j-1],dp[i][j-1][1],dp[i][j-1][0]+items[i-1][j-1])
            dp[i][j][2] = max(dp[i][j-1][2],dp[i][j-1][1]+items[i-1][j-1])
            dp[i][j][3] = max(dp[i][j-1][3],dp[i][j-1][2]+items[i-1][j-1])
        else:
            dp[i][j][0] = max(max(dp[i-1][j]),dp[i][j-1][0])
            dp[i][j][1] = dp[i][j-1][1]
            dp[i][j][2] = dp[i][j-1][2]
            dp[i][j][3] = dp[i][j-1][3]

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

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
r,c,k = map(int,readline().split())
items = [[0]*c for _ in range(r)]
for i in range(k):
    a,b,v = map(int,readline().split())
    a,b = a-1,b-1
    items[a][b] = v

dp0 = [[0]*(c+1) for j in range(r+1)]
dp1 = [[0]*(c+1) for j in range(r+1)]
dp2 = [[0]*(c+1) for j in range(r+1)]
dp3 = [[0]*(c+1) for j in range(r+1)]

for i in range(1,r+1):
    for j in range(1,c+1):
        #dp[i][j][0] = max(maximam[i-1][j],dp[i][j-1][0])
        #dp[i][j][1] = max(maximam[i-1][j]+items[i-1][j-1],dp[i][j-1][1],dp[i][j-1][0]+items[i-1][j-1])
        dp1[i][j] = max(dp0[i][j]+items[i-1][j-1],dp1[i][j-1],dp0[i][j-1]+items[i-1][j-1])
        dp2[i][j] = max(dp2[i][j-1],dp1[i][j-1]+items[i-1][j-1])
        dp3[i][j] = max(dp3[i][j-1],dp2[i][j-1]+items[i-1][j-1])
        if i < r:
            dp0[i+1][j] = max(dp0[i][j],dp1[i][j],dp2[i][j],dp3[i][j])
        #maximam[i][j] = max(dp[i][j])

print(max(dp0[-1][-1],dp1[-1][-1],dp2[-1][-1],dp3[-1][-1]))
### BUGGY CODE ###

n = int(input())
arr = list(map(int,input().split()))
arr.insert(0,0)
arr.append(0)
ans = 0
tmp = 0
for i in range(1,n + 1):
    for j in range(1,len(arr)):
        if i == j:
            pass
        else:
            ans += abs(arr[j] - tmp)
            tmp = arr[j]
    print(ans)
    ans = 0

### FIXED CODE ###

n = int(input())
arr = [0] + list(map(int,input().split())) + [0]
tmp= [ abs(arr[i] - arr[i + 1]) for i in range(len(arr) - 1)]
_sum = sum(tmp)
for i in range(n):
    ans = _sum - tmp[i] - tmp[i + 1] + abs(arr[i + 2] - arr[i])
    print(ans)
### BUGGY CODE ###

n,q = map(int, input().split())
stx = [tuple(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

#これはセグ木 * bisect
import bisect
inf = 10**9 + 100

def init(n,init_num=0):
    num = len(str(bin(n-1))) + 1
    seg = [init_num] * (2**num)
    seg[0] = 2**(num-1)
    return(seg)

def update(head, tail, x):
    # print('{} {} {}'.format(head, tail, x))
    head += seg[0]
    tail += seg[0]
    points = []
    while(head <= tail):
        if(head == tail):
            points.append(head)
            break

        if(head % 2 ==1):
            points.append(head)
            head += 1
        head = head//2

        if(tail % 2 == 0):
            points.append(tail)
            tail -= 1
        tail = (tail-1)//2

    for point in points:
        seg[point] = min(seg[point], x)

def execute(p):
    p += seg[0]
    tmp = seg[p]
    while(p > 0):
        p = p//2
        tmp = min(tmp, sep[p])
    return(tmp)

def execute_all():
    for i in range(2,len(seg)):
        seg[i] = min(seg[i], seg[i//2])


seg = init(q, init_num = inf)

for i in range(n):
    left = bisect.bisect_left(d, stx[i][0] -stx[i][2])
    right = bisect.bisect_right(d, stx[i][1] - stx[i][2] -1) -1
    update(left, right, stx[i][2])
    # print('{} {} {}'.format(left, right, stx[i][2]))

execute_all()

for i in seg[seg[0]: seg[0] + q]:
    if(i == inf):
        print(-1)
    else:
        print(i)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n,q = map(int, input().split())
# stx = [tuple(map(int, input().split())) for _ in range(n)]
stx = [0]*n
for i in range(n):
    stx[i] = tuple(map(int, input().split()))
# d = [int(input()) for _ in range(q)]
d = [0]*q
for i in range(q):
    d[i] = int(input())

#これはセグ木 * bisect
import bisect
inf = 10**9 + 100

# 定数倍高速化
b_left = bisect.bisect_left
b_right = bisect.bisect_right

def init(n,init_num=0):
    num = len(str(bin(n-1))) + 1
    seg = [init_num] * (2**num)
    # seg[0] = 2**(num-1)
    seg0 = 2**(num-1)
    return(seg,seg0)

def update(head, tail, x):
    # print('{} {} {}'.format(head, tail, x))
    head += seg0
    tail += seg0
    points = []
    while(head <= tail):
        if(head == tail):
            points.append(head)
            break

        if(head % 2 ==1):
            points.append(head)
            head += 1
        head = head//2

        if(tail % 2 == 0):
            points.append(tail)
            tail -= 1
        tail = (tail-1)//2

    for point in points:
        seg[point] = min(seg[point], x)

def execute_all():
    for i in range(2,len(seg)):
        seg[i] = min(seg[i], seg[i//2])


seg,seg0 = init(q, init_num = inf)

for i in range(n):
    left = b_left(d, stx[i][0] -stx[i][2])
    right = b_right(d, stx[i][1] - stx[i][2] -1) -1
    update(left, right, stx[i][2])
    # print('{} {} {}'.format(left, right, stx[i][2]))

execute_all()

for i in seg[seg0: seg0 + q]:
    if(i == inf):
        print(-1)
    else:
        print(i)
### BUGGY CODE ###

def f_knapsack_for_all_segments(MOD=998244353):
    N, S = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]

    dp = [[[0] * 3 for s in range(S + 1)] for i in range(N + 1)]
    dp[0][0][0] = 1
    for i in range(N):
        for s in range(S + 1):
            # i 番の要素を採用しない場合
            dp[i + 1][s][0] += dp[i][s][0]
            dp[i + 1][s][1] += dp[i][s][0] + dp[i][s][1]
            dp[i + 1][s][2] += dp[i][s][0] + dp[i][s][1] + dp[i][s][2]
            for t in range(3):
                dp[i + 1][s][t] %= MOD

            # i 番の要素を採用できる場合
            if s + A[i] <= S:
                dp[i + 1][s + A[i]][1] += dp[i][s][0] + dp[i][s][1]
                dp[i + 1][s + A[i]][2] += dp[i][s][0] + dp[i][s][1]
                for t in range(1, 3):
                    dp[i + 1][s + A[i]][t] %= MOD
    return dp[N][S][2]

print(f_knapsack_for_all_segments())


### FIXED CODE ###

def f_knapsack_for_all_segments(MOD=998244353):
    # 参考: https://maspypy.com/atcoder-参加感想-2019-03-22abc-159
    import numpy as np
    N, S = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]

    ans = 0
    f = np.zeros(S + 1, np.int64)  # f[k]: 多項式の x**k の項の係数
    for a in A:
        # f で表される多項式に対して (f + 1)(1 + x**a) を新しい f とする
        f[0] += 1  # f + 1
        f[a:] += f[:-a].copy()  # 1 + x**a を掛ける
        f %= MOD
        # x**S の項の係数を解に加える
        ans += f[S]
        ans %= MOD
    return ans

print(f_knapsack_for_all_segments())
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

H, W = map(int, input().split())
A = []
for _ in range(H):
    A.append(input())
import queue
todo = queue.Queue()
for y in range(H):
    for x in range(W):
        if A[y][x] == '#':
            exist = True
            todo.put((x, y))

seen = [[False] * W for _ in range(H)]
route= [[0] * W for _ in range(H)]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
def bfs(el):
    x, y = el
    #print(x, y)
    seen[y][x] = True
    for i in range(4):
        if 0 <= x + dx[i] < W and 0 <= y + dy[i] < H:
            if seen[y + dy[i]][x + dx[i]] == False and A[y + dy[i]][x + dx[i]] == '.':
                route[y + dy[i]][x + dx[i]] = route[y][x] + 1
                seen[y + dy[i]][x + dx[i]] = True
                todo.put((x + dx[i], y + dy[i]))
    if not todo.empty():
        bfs(todo.get())
    else:
        return None
bfs(todo.get())
#print(seen)
#print(route)

M = 0
for y in range(W):
    for x in range(H):
        M = max(M, route[y][x])
print(M)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
matrix = [["a" for _ in range(w+2)]] + [list("a" + input() + "a") for _ in range(h)] + [["a" for _ in range(w+2)]]

matrix_list1 = deque()
cnt = 0

#黒いタイルの位置情報を確認
for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "#":
            matrix_list1.append([i,j])

#白いタイルが無くなるまで、黒いタイルを増やす
while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            matrix_list1.append([x+1,y])
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            matrix_list1.append([x-1,y])
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            matrix_list1.append([x,y+1])
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            matrix_list1.append([x,y-1])
    else:
        if len(matrix_list1) > 0:
            cnt += 1
    
print(cnt)
### 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]
        ans %= 1000000007

print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A2 = list(map(lambda x: x ** 2, A))

sumA = sum(A)
sumA2 = sum(A2)

ans = (((sumA ** 2) - sumA2) // 2) % 1000000007

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

N = int(input())
A = list(map(int, input().split()))
tmp_x = -1
tmp_x_diff = -1
for i in range(N - 1):
    sum1 = sum(A[:i + 1])
    sum2 = sum(A[i + 1:])
    diff = abs(sum1 - sum2)
    if tmp_x_diff == -1 or diff < tmp_x_diff:
        tmp_x = i
        tmp_x_diff = diff
print(tmp_x_diff)


### FIXED CODE ###

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

cumsum = [0]
for i in range(N):
    cumsum.append(cumsum[-1] + A[i])

tmp_x = -1
tmp_x_diff = -1
for i in range(N - 1):
    sum1 = cumsum[i + 1]
    sum2 = cumsum[-1] - cumsum[i + 1]
    diff = abs(sum2 - sum1)
    if tmp_x_diff == -1 or diff < tmp_x_diff:
        tmp_x = i
        tmp_x_diff = diff
print(tmp_x_diff)
### BUGGY CODE ###

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

for i in range(M):
    max_value = max(A)
    max_index = A.index(max_value)
    A[max_index] = int(A[max_index] / 2)

print(sum(A))


### FIXED CODE ###

import heapq

N, M = list(map(int, input().split()))
A = list(map(lambda x: -int(x), input().split()))

heapq.heapify(A)

for i in range(M):
    _ = -heapq.heappop(A)
    _ = int(_ / 2)
    heapq.heappush(A, -_)

print(-sum(A))
### BUGGY CODE ###

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M = nl()
S = nl()
T = nl()

dp = [0] * (M+1)
for i, s in enumerate(S):
    dp2 = dp[:]
    cum = 0
    for j, t in enumerate(T):
        k = dp2[j] - dp[j]
        if s == t:
            k += dp[j] + 1
        dp2[j+1] += k
    dp = dp2

print((dp[M]+1) % 1000000007)


### FIXED CODE ###

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M = nl()
S = nl()
T = nl()

dp = [0] * (M+1)
for i, s in enumerate(S):
    dp2 = dp[:]
    for j, t in enumerate(T):
        dp2[j+1] += dp2[j] - dp[j]
        if s == t:
            dp2[j+1] += dp[j] + 1
    dp = dp2

print((dp[M]+1) % 1000000007)
### BUGGY CODE ###

# encoding: "utf-8"

from collections import defaultdict
from functools import reduce
from itertools import groupby

class Stdin:
    @staticmethod
    def read_line(converter=str):
        return [converter(x) for x in input().split()]
    
    @staticmethod
    def read_lines(n, converter=str):
        result = list()
        for _ in range(n):
            result.append(Stdin.read_line(converter))
        return result
    
    @staticmethod
    def convert(data, converter):
        assert(len(data) == len(converter))
        return tuple(map(lambda x, f: f(x), data, converter))

    @staticmethod
    def convert_lines(datas, n, converter):
        return [converter(data, n, converter) for data in datas]


def main():
    _ = input()
    xs = Stdin.read_line(converter=int)
    # print(xs)
    ys = concat_map(xs, lambda x: [x, x+1, x-1])
    ys.sort()
    print(max(map(lambda x: count(x[1]), groupby(ys))))

def concat_map(xs, f):
    return reduce(lambda accum, x: accum + x, map(f, xs))

def count(iterator):
    cnt = 0
    for _ in iterator:
        cnt += 1
    return cnt

if __name__ == "__main__":
    main()

### FIXED CODE ###

input()
a_list = [int(s) for s in input().split()]

count = [0]*100002

for a in a_list:
    count[a] += 1
    count[a+1] += 1
    count[a+2] += 1
    
print(max(count))
### BUGGY CODE ###



from collections import defaultdict

N, M = map(int, input().split())
es = defaultdict(list)
for i in range(M):
    a,b = map(int, input().split())
    es[a].append(b)


for i in range(2,N):

    if i in es[1] and N in es[i]:
        print("POSSIBLE")
        exit()


print("IMPOSSIBLE")

### FIXED CODE ###

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

ship = {}

for i in range(m):
  a,b = (map(int, input().split()))
  if a == 1 or b == n:
    if a in ship: #keyにaがあるばあい
      ship[a].append(b)
    else:
      ship[a] = [b]

if 1 in ship:
  for i in ship[1]:
    if i in ship and n in ship[i]:
      print("POSSIBLE")
      exit()
      


  
  
print("IMPOSSIBLE")
### BUGGY CODE ###

def xor_plus(l1,l2):#引数はリストであることに注意
    l = [0] * max(len(l1),len(l2))
    for i in range(1,len(l)+1):
        if i > len(l1):
            l[-i] = l2[-i]
        elif i > len(l2):
            l[-i] = l1[-i]
        elif l1[-i] == l2[-i]:
            l[-i] = 0
        else:
            l[-i] = 1
    return l#返り値はリストであることに注意


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

a_bin = [0] * n

for i in range(0,n):
    a_bin[i] = list(map(int,list(bin(a[i]))[2:]))
    
#print("a_bin")
#print(a_bin)

k_bin = list(map(int, list(bin(k+1))[2:]))
#print("k_bin")
#print(k_bin)


#print("x_bin")

m = [0] * len(k_bin)

for i in range(0,len(k_bin)):
    x_bin = [0] * (len(k_bin))
    if k_bin[i] == 0:
        continue
    for j in range(0,i):
        x_bin[j] = k_bin[j]
    
    #print(x_bin)
    
    
    for j in range(1,len(k_bin)-i):
        count = 0
        for l in range(0,n):
            if j <= len(a_bin[l]):
                count += a_bin[l][-j]
        #print([-j,count])
        if count <= n - count:
            x_bin[-j] = 1
    
    val = 0
    #print(x_bin)
    
    for j in range(0,n):
        lis = list(map(str, xor_plus(x_bin,a_bin[j])))
        #print(lis)
        val = val + int(''.join(lis),2)
        #print(val)
    m[i] = val

print(max(m))

### FIXED CODE ###

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

def f(x):
    ret = 0
    for i in range(N):
        ret += A[i] ^ x
    return ret

###2**(num-1)<=K<2**numなるnumを求める
P = bin(K)
num = len(list(map(int,P[2:])))

best = 0

for i in range(num):
    count = 0###2**iの位が1になるAの個数
    for j in range(N):
        if A[j] > A[j]^(2**i):
            count += 1
    
    if count <= N - count:
        best += 2**i

#print(best)
can = [0]*40

for i in range(40):
    if K & 2**i == 0:
        continue
    for j in range(0,i):
        can[i] += best & 2**j
    for j in range(i+1,40):
        can[i] += K & 2**j

can.append(K)

print(max(list(map(f,can))))
### BUGGY CODE ###

m = 10**9 + 7
n = int(input())
seq = [bin(int(x))[2:].zfill(61) for x in input().split()]
cnt = [[0,0] for i in range(61)]
for s in seq:
    for i in range(61):
        if s[i] == '0':
            cnt[i][0] += 1
        else:
            cnt[i][1] += 1
ans = 0
for i in range(61):
  ans += cnt[-i-1][0]*cnt[-i-1][1]*(2**i)
  ans = ans % m
print(ans)

### FIXED CODE ###

m = 10**9 + 7
n = int(input())
seq = [bin(int(x))[2:].zfill(61) for x in input().split()]
cnt = [[0,0] for i in range(61)]
for s in seq:
    for i in range(len(s)):
        if s[i] == '0':
            cnt[i][0] += 1
        else:
            cnt[i][1] += 1
ans = 0
for i in range(61):
  ans += cnt[-i-1][0]*cnt[-i-1][1]*(2**i)
  ans = ans % m
print(ans)
### BUGGY CODE ###

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

ac_list  = [0]*N
for i in range(N-1):
    if S[i:i+2] == "AC":
        ac_list[i] = 1
        
for lr in lr_list:
    print(ac_list[lr[0] - 1:lr[1] - 1].count(1))

### FIXED CODE ###

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

ac_list  = [0]*N
cnt = 0
for i in range(N-1):
    if i < len(S) and S[i:i+2] == "AC":
        cnt += 1
    ac_list[i+1] = cnt
        
for lr in lr_list:
    print(ac_list[lr[1]-1] - ac_list[lr[0]-1])
### BUGGY CODE ###

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

d = dict(list((_, a.count(_))) for _ in set(a))
a_cnt = sorted(d.values())

cnt = 0##書き換えた数
for i in range(len(set(a)) - k):##書き換え必要な種類の数
    cnt += a_cnt[i]
print(cnt)    

### FIXED CODE ###

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

d = dict()
for i in a:
    d[i] = d.get(i, 0) + 1
d_sorted = sorted(d.values())
knd = len(set(a))##種類数
print(sum(d_sorted[:knd - k]))
### BUGGY CODE ###

n = int(input())
d = []

for i in range(n):
    order = input().split()
    if order[0] == 'insert':
        d.append(order[1])
    else:
        if order[1] in d:
            print("yes")
        else:
            print("no")

### FIXED CODE ###

n = int(input())
d = {}

for i in range(n):
    order = input().split()
    if order[0] == 'insert':
        d[order[1]] = i
    else:
        if order[1] in d:
            print("yes")
        else:
            print("no")
### BUGGY CODE ###

n, k = map(int, input().split())
lr = []
for _ in range(k):
    l, r = map(int, input().split())
    lr.append((l, r))
mod = 998244353
dp = [0]*(2*n+1)
dp[0] = 1
dp[1] = -1
now = 1
for i in range(n):
    for l, r in lr:
        dp[i+l] += now
        dp[i+r+1] -= now
    now += dp[i+1]
print(sum(dp[:n])%mod)

### FIXED CODE ###

n, k = map(int, input().split())
lr = []
for _ in range(k):
    l, r = map(int, input().split())
    lr.append((l, r))
mod = 998244353
dp = [0]*(2*n+1)
dp[0] = 1
dp[1] = -1
now = 1
for i in range(n):
    for l, r in lr:
        dp[i+l] += now
        dp[i+r+1] -= now
    now += dp[i+1]
    now %= mod
ans = 0
for i in range(n):
    ans += dp[i]
    ans %= mod
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
 
def readstr():
    return input().strip()
 
 
def readint():
    return int(input())
 
 
def readnums():
    return map(int, input().split())
 
 
def readstrs():
    return input().split()
 
 
def main():
    N = readint()
    X = list(readnums())
    xs = sorted(X)
    for i in X:
        d = xs.index(i)
        if d >= N // 2:
            print(xs[N // 2 - 1])
        else:
            print(xs[N // 2])
 
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import bisect
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    N = readint()
    X = list(readnums())
    xs = sorted(X)
    for i in X:
        d = bisect.bisect_left(xs, i)
        if d >= N // 2:
            print(xs[N // 2 - 1])
        else:
            print(xs[N // 2])


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

from itertools import accumulate
n, k = map(int, input().split())
p = list(map(int, input().split()))
ps =[0] + list(accumulate(p))
a = 0
b = []
for i in range(n+1- k):
    if a < ps[i+k] - ps[i]:
        a = ps[i+k] - ps[i]
        b = p[ i : i + k ]
        
x = 0
for i in b:
    for j in range(i+1):
        x += j/i
print(x)
    

### FIXED CODE ###

from itertools import accumulate
n, k = map(int, input().split())
P= list(map(int, input().split()))
e = [(1+p) / 2 for p in P]
ps =[0] + list(accumulate(e))
a = 0
for i in range(n+1- k):
    if a < ps[i+k] - ps[i]:
        a = ps[i+k] - ps[i]

print(a)
### BUGGY CODE ###

from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N, M = reads()
edges = [[] for _ in range(N)]
for _ in range(M):
  p, q, c = reads()
  p, q = p-1, q-1
  edges[p].append((q, c))
  edges[q].append((p, c))

INF = 1 << 30
def dijkstra(edges, s):
  result = defaultdict(lambda: INF)
  result[s, -1] = 0
  que = deque([(0, s, -1)])
  while len(que) > 0:
    (d, u, c) = que.popleft()
    if result[u, c] < d:
      continue
    if c < 0:
      for (t, c2) in edges[u]:
        if d + 1 < result[t, c2]:
          result[t, c2] = d + 1
          que.append((d + 1, t, c2))
    else:
      for (t, c2) in edges[u]:
        if c == c2 and d < result[t, c2]:
          result[t, c2] = d
          que.appendleft((d, t, c2))
      if d < result[u, -1]:
        result[u, -1] = d
        que.appendleft((d, u, -1))
  return result

dist = dijkstra(edges, 0)
try:
  print(min(d for (u, _), d in dist.items() if u == N-1))
except ValueError:
  print(-1)

### FIXED CODE ###

from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N, M = reads()
edges = [[] for _ in range(N)]
edgesc = defaultdict(lambda: [])
for _ in range(M):
  p, q, c = reads()
  p, q = p-1, q-1
  edges[p].append((q, c))
  edges[q].append((p, c))
  edgesc[p, c].append(q)
  edgesc[q, c].append(p)

INF = 1 << 30
def dijkstra(edges, s):
  result = defaultdict(lambda: INF)
  result[s, -1] = 0
  que = deque([(0, s, -1)])
  while len(que) > 0:
    (d, u, c) = que.popleft()
    if result[u, c] < d:
      continue
    if c < 0:
      for (t, c2) in edges[u]:
        if d + 1 < result[t, c2]:
          result[t, c2] = d + 1
          que.append((d + 1, t, c2))
    else:
      for t in edgesc[u, c]:
        if d < result[t, c]:
          result[t, c] = d
          que.appendleft((d, t, c))
      if d < result[u, -1]:
        result[u, -1] = d
        que.appendleft((d, u, -1))
  return result

dist = dijkstra(edges, 0)
try:
  print(min(d for (u, _), d in dist.items() if u == N-1))
except ValueError:
  print(-1)
### BUGGY CODE ###

# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    S = input().rstrip()

    N = len(S)

    M = [0 for i in range(2019)]

    for i in range(N):
        T = S[i:]
        T = int(T)
        M[T%2019] += 1

    M[0] += 1

    res = 0

    for m in M:
        res += m * (m-1) // 2


    print(res)



main()


### FIXED CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit, i8


# @njit(i8[:](i8,i8,i8[:]))
@njit
def loof(a,N):
    M = np.zeros(2019,dtype=np.int16)
    M[0] += 1
    T = 0
    r = 1
    T += a[-1] * r
    T %= 2019
    M[T] += 1
    for i in range(N-2,-1,-1):
        r *= 10
        r %= 2019
        T += a[i] * r
        T %= 2019
        M[T] += 1
    return M


# @njit
# def pow_mod(a,n,mod):
#     memo = np.array([1])
#     if n >= 1:
#         for i in range(n-1):
#             memo = np.append(memo,memo[-1]*a%mod)
#         return memo
#     else:
#         return memo[0]


def main():
    S = input().rstrip()
    S = list(map(int,list(S)))
    a = np.array(S)

    N = len(a)

    # memo = pow_mod(10,N,2019)
    M = loof(a,N)

    res = 0

    for m in M:
        res += m * (m-1) // 2

    print(res)


main()
### BUGGY CODE ###

N = int(input())
N_List =list(map(int,input().split()))
Sort_List = []
for i in range(N):
    Sort_List.append(N_List.index(i+1)+1)

print(" ".join(list(map(str,Sort_List))))

### FIXED CODE ###

N = int(input())
N_List =list(map(int,input().split()))
ans = [0] * N
for i in range(N):
    s = N_List[i]   
    ans[s-1] = i+1  
print(*ans)