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

from heapq import heappush, heappop

n, m = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(m)]
edge.sort(key=lambda x: (x[0], x[1]))

q = [(1, 0)]
for l, r, c in edge:
    # print((l, r, c), q)

    cand = float("inf")
    while q:
        y, z = heappop(q)
        if y >= l:
            heappush(q, (y, z))
            break

    for y, z in q:
        if y < r:
            cand = min(cand, z)
        else:
            heappush(q, (y, z))
            break

    if cand != float("inf"):
        heappush(q, (r, cand + c))

# print(q)

ans = -1
for y, z in q:
    if y == n:
        if ans == -1:
            ans = z
        else:
            ans = min(ans, z)

print(ans)


### FIXED CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline


def dijkstra(graph: list, node: int, start: int) -> list:
    # graph[node] = [(cost, to)]
    INF = float('inf')
    dist = [INF] * node

    dist[start] = 0
    heap = [(0, start)]
    while heap:
        cost, thisNode = heappop(heap)
        for NextCost, NextNode in graph[thisNode]:
            dist_cand = dist[thisNode] + NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap, (dist[NextNode], NextNode))
    return dist
    # dist = [costs to nodes]


n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    l, r, c = map(int, input().split())
    l -= 1
    r -= 1
    edge[l].append((c, r))
for i in range(1, n):
    edge[i].append((0, i - 1))

dist = dijkstra(edge, n, 0)
ans = dist[-1] if dist[-1] != float("inf") else -1

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

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

"""
参考：http://tutuz.hateblo.jp/entry/2018/08/06/074104
・別解
・予め必要なA,C,?の個数は集めておく。
・Bの位置を決めて、4つの選び方パターンを全部数え上げる。
"""

MOD = 10 ** 9 + 7
S = input()

# あるBの位置よりも左にあるAと?の個数
A, LQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1):
    a = lq = 0
    if S[i] == 'A':
        a += 1
    if S[i] == '?':
        lq += 1
    A[i+1] = A[i] + a
    LQ[i+1] = LQ[i] + lq
# あるBの位置よりも右にあるCと?の個数
C, RQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1, 0, -1):
    c = rq = 0
    if S[i] == 'C':
        c += 1
    if S[i] == '?':
        rq += 1
    C[i-1] = C[i] + c
    RQ[i-1] = RQ[i] + rq

ans = 0
for i in range(len(S)):
    if S[i] == '?' or S[i] == 'B':
        # (A,B,C) と選ぶ場合(後ろの3べきは使わなかった?の分)
        case1 = (A[i] * C[i] * pow(3, LQ[i]) * pow(3, RQ[i])) % MOD
        # (A,B,?) と選ぶ場合
        case2 = (A[i] * RQ[i] * pow(3, LQ[i]) * pow(3, max(RQ[i]-1, 0))) % MOD
        # (?,B,C) と選ぶ場合
        case3 = (LQ[i] * C[i] * pow(3, max(LQ[i]-1, 0)) * pow(3, RQ[i])) % MOD
        # (?,B,?) と選ぶ場合
        case4 = (LQ[i] * RQ[i] * pow(3, max(LQ[i]-1, 0)) * pow(3, max(RQ[i]-1, 0))) % MOD
        # 全部足し合わせてMOD
        ans = (ans + case1 + case2 + case3 + case4) % MOD

print(int(ans))


### FIXED CODE ###

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

"""
参考：http://drken1215.hatenablog.com/entry/2018/08/05/224100_1
・文字列DP
・こういう、ちょっと状況込み入ったDPがまだ自分でうまく書けない。
・もっと数こなして経験積まなきゃなー。
"""

MOD = 10 ** 9 + 7
S = input()

# 文字列Sのi文字目まで考えたときにABCのj文字目まで照合させた個数
dp = [[0] * 4 for i in range(len(S)+1)]
dp[0][0] = 1

for i in range(len(S)):
    # i文字目でABCカウントを進めない場合(真下に送る分)
    for j in range(4):
        if S[i] == '?':
            dp[i+1][j] = (dp[i+1][j] + dp[i][j] * 3) % MOD
        else:
            dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD
    # i文字目でABCカウントを進める場合(右下に送る分)
    if S[i] == '?' or S[i] == 'A':
        dp[i+1][1] = (dp[i+1][1] + dp[i][0]) % MOD
    if S[i] == '?' or S[i] == 'B':
        dp[i+1][2] = (dp[i+1][2] + dp[i][1]) % MOD
    if S[i] == '?' or S[i] == 'C':
        dp[i+1][3] = (dp[i+1][3] + dp[i][2]) % MOD

print(dp[len(S)][3])
### BUGGY CODE ###

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

task.sort()

wa = []
ans = 0
j = 0
for i in range(M):
    while j < N and task[j][0] == i + 1:
        wa.append(task[j][1])
        j += 1
    if wa:
        ls = max(wa)
        ans += ls
        wa.remove(ls)

print(ans)


### FIXED CODE ###

import bisect
import heapq

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

task.sort()

wa = []
ans = 0
j = 0
for i in range(M):
    while j < N and task[j][0] == i + 1:
        heapq.heappush(wa,-task[j][1])
        j += 1
    if wa:
        ans -= heapq.heappop(wa)

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

S = input()
N = len(S)
# N 文字の文字列 S から、長さ N+1 の ---累積和--- s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

counter = [0] * 2019
indices = []

for i in range(N + 1):
    if i == 0:
        sub = 0
    elif i == 1:
        sub = int(S[N - 1])
    else:
        # sub = int(S[N - i] + str(sub))
        sub += int(S[N - i]) * 10 ** (i-1)
    rest = sub % 2019
    counter[rest] += 1

ans = 0
for r in counter:
    ans += r * (r - 1) // 2
print(ans)

### FIXED CODE ###

S = list(input())
N = len(S)
# N 文字の文字列 S から、長さ N+1 の ---累積和--- s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

counter = [0] * 2019
k = 10
for i in range(N + 1):
    if i == 0:
        sub = 0
    elif i == 1:
        sub = int(S[N - 1])
    else:
        sub += int(S[N - i]) * k
        k *= 10
        k %= 2019
    rest = sub % 2019
    counter[rest] += 1

ans = 0
for r in counter:
    ans += r * (r - 1) // 2
print(ans)
### BUGGY CODE ###

N = int(input())
emplist = [int(x) for x in input().split()]

for i in range(1,N+1):
    print(emplist.count(i))

### FIXED CODE ###

from collections import Counter
N = int(input())
emplist = [int(x) for x in input().split()]

ans = Counter(emplist)

for i in range(1,N+1):
    print(ans[i])
### BUGGY CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()

import numpy as np


def ret_binary(a: int):  # 逆順で返すことに注意
    ret_r = [0] * n
    for i in range(n):
        bit = a % 2
        a = a // 2
        ret_r[i] = bit
    return np.array(ret_r, dtype='int')


def calc_sum(a_binary, n_1_ls, n_1_max):
    '''
    a_binaryはxorしてから和を取りたい数
    n_1_lsは各桁の1の数
    n_1_maxは最大1は何個あり得るか
    '''
    ret = 0
    for i, (aa, n_1) in enumerate(zip(a_binary, n_1_ls)):
        if aa == 0:
            ret += (((2**i) % MOD) * (n_1 % MOD)) % MOD
        else:
            ret += (((2**i) % MOD) * ((n_1_max - n_1) % MOD)) % MOD
    return ret


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = np.zeros(n, dtype='int')
ans = 0
a_pre = A[N - 1]
a_pre_binary = ret_binary(a_pre)
for a in A[-2::-1]:
    a_binary = ret_binary(a)
    n_1_ls = n_1_ls + a_pre_binary
    n_1_max += 1
    tmp = calc_sum(a_binary, n_1_ls, n_1_max)
    ans += tmp
    ans %= MOD
    a_pre_binary = a_binary

print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()


def ret_binary(a: int):  # 逆順で返すことに注意
    ret_r = [0] * n
    for i in range(n):
        bit = a % 2
        a = a // 2
        ret_r[i] = bit
    return ret_r


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
for a in A:
    tmp = ret_binary(a)
    for i in range(n):
        n_1_ls[i] += tmp[i]


for i, n_1 in enumerate(n_1_ls):
    num_sonoketa = n_1 * (N - n_1)
    ans += (((2**i) % MOD) * num_sonoketa)
    ans %= MOD
print(ans)
### BUGGY CODE ###

from heapq import heappop, heappush

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1

C = [input() for i in range(H)]
dist = {}
d = [[0, x1, y1, K, -1]]
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  cost, x, y, remain, v = heappop(d)
  if (x, y, v) in dist:
    continue
  dist[(x, y, v)] = cost
  for i, (dx, dy) in enumerate(dxy):
    xx = x + dx; yy = y + dy
    if 0<=xx<H and 0<=yy<W and C[xx][yy] != '@':
      if (xx, yy, i) in dist:
        continue
      if i == v and remain:
        heappush(d, [cost, xx, yy, remain-1, v])
      else:
        heappush(d, [cost+1, xx, yy, K-1, i])

cands = [dist[(x2, y2, i)] for i in range(4) if (x2, y2, i) in dist]
if cands:
  print(min(cands))
else:
  print(-1)

### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque
 
H, W, K = map(int,readline().split())
x1, y1, x2, y2 = map(int,readline().split())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
C = read().split()

dist = [[-1]*W for i in range(H)]
dist[x1][y1] = 0
d = deque([[x1, y1]])
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  x, y = d.popleft()
  if (x, y) == (x2, y2):
    print(dist[x][y])
    quit()
  for dx, dy in dxy:
    xx = x; yy = y
    for i in range(K):
      xx += dx; yy += dy
      if 0<=xx<H and 0<=yy<W and C[xx][yy]!='@':
        if 0 <= dist[xx][yy] <= dist[x][y]:
          break
        if dist[xx][yy] == -1:
           d.append([xx, yy])
        dist[xx][yy] = dist[x][y] + 1
      else:
        break

print(-1)
### BUGGY CODE ###

N = int(input())
s = []; count = 0
for i in range(N):
    spell = ''.join(sorted(input()))
    for j in range(len(s)):
        if spell == s[j]:
            count += 1
    s.append(spell)

print(count)

### FIXED CODE ###

N = int(input())
dic = {}
for i in range(N):
    spell = ''.join(sorted(input()))
    if spell in dic.keys():
        dic[spell] += 1
    else:
        dic[spell] = 1

count = 0
for num in dic.values():
    count += sum([i for i in range(num)])

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

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

l=[]
for _ in range(m):
  a,b=map(int,input().split())
  l1=list(range(a,b+1))
  l.append(l1)
  
con=0
for x in range(1,n+1):
  ans=[x in i for i in l]
  con+=all(ans)
  
print(con)

### FIXED CODE ###

n,m=map(int,input().split())
lm=0
rm=10**9
 
for i in range(m):
    l,r=map(int,input().split())
    lm=max(lm,l)
    rm=min(rm,r)
 
print(max(0,rm-lm+1))
### BUGGY CODE ###

N,x=map(int,input().split())
a=list(map(int,input().split()))
c=[[None]*N for i in range(N)]
for j in range(N):
    for i in range(N):
        if j==0:
            c[j][i]=a[i]
        else:
            c[j][i]=min(c[j-1][i-1],a[i])
ans=2*10**12
for i in range(N):
    ans=min(ans,sum(c[i])+x*i)
print(ans)

### FIXED CODE ###

N,x=map(int,input().split())
a=list(map(int,input().split()))
c=[[None]*N for i in range(N)]
for j in range(N):
    for i in range(N):
        if j==0:
            c[j][i]=a[i]
        else:
            c[j][i]=min(c[j-1][i-1],a[i])
ans=2*10**12
for i in range(N):
    ans=min(ans,sum(c[i])+x*i)
print(ans)
### BUGGY CODE ###

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

count1 = 0
count2 = 0
count3 = 0
for x in range(K+1):
    for y in range(x, K+1):
        for z in range(y, K+1):
            if x + y + z == S:
                count1 += 1
                if x == y or y == z or z == x:
                    count2 += 1
                    if x == y and y == z:
                        count3 += 1
                
print(count1*6 - count2*3 - count3*2)

### FIXED CODE ###

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

count = 0
for x in range(K+1):
    for y in range(K+1):
        if 0 <= S - x - y <= K:
            count += 1
                
print(count)
### BUGGY CODE ###

from collections import deque
 
H,W=map(int, input().split())

A=[]
for i in range(H):
  A.append(list(input()))
q=deque(maxlen=H*W)
for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      q.append((i, j, 0))

x=-1
while q:
  (i, j, n)=q.popleft()
  x=max(x, n)
  if i > 0 and A[i-1][j] == '.':
    A[i-1][j] = '#'
    q.append((i-1, j, n+1))
  if i < H-1 and A[i+1][j] == '.':
    A[i+1][j] = '#'
    q.append((i+1, j, n+1))
  if j > 0 and A[i][j-1] == '.':
    A[i][j-1] = '#'
    q.append((i, j-1, n+1))
  if j < W-1 and A[i][j+1] == '.':
    A[i][j+1] = '#'
    q.append((i, j+1, n+1))
    
print(x)

### FIXED CODE ###

def f(h, w):
    dt = [[-1, 0], [0, -1], [0, 1], [1, 0]]
    t = [[True] * (w + 2)]
    for _ in range(h):
        t += [[True] + [(c == "#") for c in input()] + [True]]
    t += [[True] * (w + 2)]
    kuro = []
    for i, ti in enumerate(t[1:-1]):
        for j, tij in enumerate(ti[1:-1]):
            if tij:
                kuro+=[(i + 1, j + 1)]
    cnt = -1
    while kuro:
        cnt += 1
        nxt = []
        for i, j in kuro:
            ti=t[i]
            if not ti[j+1]:
                ti[j + 1]=True
                nxt += [(i, j+1)]
            if not ti[j-1]:
                ti[j - 1]=True
                nxt += [(i, j-1)]
            if not t[i - 1][j]:
                t[i - 1][j]=True
                nxt += [(i - 1, j)]
            if not t[i + 1][j]:
                t[i + 1][j]=True
                nxt += [(i + 1, j)]
        kuro = nxt
    print(cnt)
 
 
h, w = map(int, input().split())
f(h, w)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,K = map(int,input().split())
a = list(map(int,input().split()))
b = set(a)
c = [a.count(i) for i in b]
d = len(b)
c.sort()
ans = 0
for i in c:
    if K >= d:
        break
    ans += i
    d -= 1
print(ans)


### FIXED CODE ###

import sys
import collections
input = sys.stdin.readline

N,K = map(int,input().split())
a = list(map(int,input().split()))
c = collections.Counter(a)
d = len(c)
ans = 0
c_sorted = sorted(c.items(),key = lambda x:x[1])
for i in c_sorted:
    if K >= d:
        break
    ans += i[1]
    d -= 1
print(ans)
### BUGGY CODE ###

input()
s=list(map(int,input().split()))
input()
t=list(map(int,input().split()))
c=0
for x in t:
    if x in s:c+=1
print(c)

### FIXED CODE ###

input()
s=set(list(map(int,input().split())))
input()
t=set(list(map(int,input().split())))
print(len(s&t))
### BUGGY CODE ###

#200419C
N = int(input())
A = list(map(int,input().split()))
A = sorted(A)

for i in range(N-1):
    print(A.count(i+1))

print("0")
        

### FIXED CODE ###

#200419C
N = int(input())
A = list(map(int,input().split()))
A = sorted(A)

count = 0
for i in range(N-1):
    L = len(A)
    #print(A)
    Ans = 0
    count += Ans
    for j in range(L-count):
        if A[count + j]==i+1:
            Ans += 1
        else:            
            break
    print(Ans)
    count += Ans

        
print("0")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
    N = int(input())
    h = list(map(int,input().split()))
    def fr(i):
        if i == 1:
            return abs(h[1]-h[0])
        elif i == 0:
            return 0
        else:
            return min(fr(i-1)+abs(h[i]-h[i-1]),\
                    fr(i-2)+abs(h[i]-h[i-2]))

    print(fr(N-1))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    h = list(map(int,input().split()))
    dp = [0 for _ in range(N)]
    dp[0] = 0
    dp[1] = abs(h[1]-h[0])
    cost = h
    for i in range(1,N-1):
        dp[i+1] = min(dp[i]+abs(cost[i+1]-cost[i]),\
            dp[i-1]+abs(cost[i+1]-cost[i-1]))
    print(dp[-1])

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

#!/usr/bin/env python3
import sys
import numpy as np
import math


def solve(A: int, B: int, N: int):
    ans = 0
    for x in range(N+1):
        ans = max(ans, A*x//B-A*(x//B))

    print(ans)
    
    return


# Generated by 1.1.6 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()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    solve(A, B, N)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import numpy as np
import math

def solve(A: int, B: int, N: int):
    x = min(B-1, N)
    print(math.floor(A*x/B)-A*math.floor(x/B))
    return


# Generated by 1.1.6 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()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    solve(A, B, N)

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

from collections import defaultdict

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

friend_list = defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split(' '))
    a, b = a - 1, b - 1
    friend_list[a].append(b)
    friend_list[b].append(a)

block_list = defaultdict(list)
for _ in range(K):
    c, d = map(int, input().split(' '))
    c, d = c - 1, d - 1
    block_list[c].append(d)
    block_list[d].append(c)


def dfs(s, adj_list):
    cand_list = [s]
    vis_list = []

    while len(cand_list) > 0:
        vis = cand_list.pop(-1)
        vis_list.append(vis)
        pre_cand_list = adj_list[vis]
        for cand in pre_cand_list:
            if cand in vis_list:
                continue
            if cand in cand_list:
                continue
            cand_list.append(cand)

    return vis_list


num_friend_candidate_array = [0, ] * N
visited_user_list = []

for i in range(N):
    if i in visited_user_list:
        continue

    connected_components = dfs(i, friend_list)
    visited_user_list += connected_components

    for j in connected_components:
        exclude_block_user = set(connected_components) - set(block_list[j])
        friend_candidates = len(exclude_block_user) - len(friend_list[j]) - 1
        num_friend_candidate_array[j] = max(friend_candidates, 0)

print(*num_friend_candidate_array)


### FIXED CODE ###

from collections import defaultdict


class UnionFind:
    def __init__(self, n=0):
        self.d = {i: -1 for i in range(n)}

    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.d[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if (x == y):
            return False
        if (self.d[x] > self.d[y]):
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.d[self.find(x)]


N, M, K = map(int, input().split(' '))
deg = defaultdict(int)
to = defaultdict(list)
uf = UnionFind(N)

for _ in range(M):
    a, b = map(int, input().split(' '))
    a -= 1
    b -= 1
    deg[a] += 1
    deg[b] += 1
    uf.unite(a, b)

for _ in range(K):
    c, d = map(int, input().split(' '))
    c -= 1
    d -= 1
    to[c].append(d)
    to[d].append(c)

for i in range(N):
    ans = uf.size(i) - 1 - deg[i]
    for u in to[i]:
        if uf.same(i, u):
            ans -= 1
    print(ans, end=' ' if i != (N - 1) else '\n')
### BUGGY CODE ###

import math

def readInt():
	return int(input())

def readInts():
	return list(map(int, input().split()))

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

s = input()[::-1]

ai = [0]*len(s)
si = [0]*len(s)

p = 2019

for i in range(len(s)):
	ai[i] = (int(s[i])*pow(10,i,p))%p
	si[i] = sum(ai[:i+1])%p
countarr = [0]*2019
for i in si:
	countarr[i]+=1

res = countarr[0]
for i in range(p):
	c = countarr[i]
	res += c*(c-1)//2

print(res)

### FIXED CODE ###

import math

def readInt():
	return int(input())

def readInts():
	return list(map(int, input().split()))

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

s = reversed(input())

ai = 0
si = 0

p = 2019
countarr = [0]*2019

for i, j in enumerate(s):
	ai = (int(j)*pow(10,i,p))%p
	si = (si+ai)%p
	countarr[si]+=1

res = countarr[0]
for i in range(p):
	c = countarr[i]
	res += c*(c-1)//2

print(res)
### BUGGY CODE ###

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


for j in range(M):
    max=0
    max_idx=0
    for i in range(len(L)):
        if(max<L[i]):
            max = L[i]
            max_idx = i

    L[max_idx] = L[max_idx]//2
    
print(sum(L))

### FIXED CODE ###

import heapq

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

q=[]
for l in L:
    heapq.heappush(q, -l)

for _ in range(M):
    p = -heapq.heappop(q)//2
    heapq.heappush(q, -p)

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

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

c = 0
for i in range(n):
    for j in range(i):
        if p[i] > p[j]:
            break
    else:
        c += 1
print(c)

### FIXED CODE ###

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

c = 0
m = p[0]
for i in range(n):
    m = min(m, p[i])
    if m >= p[i]:
        c += 1
print(c)
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
D = defaultdict(int)
for a in A:
  D[a] += 1
Q = int(input())
B = []
C = []
for _ in range(Q):
  l = list(map(int, input().split()))
  B.append(l[0])
  C.append(l[1])

for i in range(Q):
  k = D[B[i]]
  D.pop(B[i])
  D[C[i]] += k
  ans = 0
  for k, v in D.items():
    ans += k * v
  print(ans)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
D = defaultdict(int)
for a in A:
  D[a] += 1
Q = int(input())
B = []
C = []
for _ in range(Q):
  l = list(map(int, input().split()))
  B.append(l[0])
  C.append(l[1])

ans = sum(A)
for i in range(Q):
  k = D[B[i]]
  D[B[i]] = 0
  D[C[i]] += k
  ans = ans - (B[i]*k) + (C[i]*k)
  print(ans)
### BUGGY CODE ###

def my_index_multi(l, x):
    return [k for k, _x in enumerate(l) if _x == x]

h,w,m = map(int,input().split())
l_h = [0]*(h+1)
l_w = [0]*(w+1)
a = min(h*w,3*10**5)
l_hw = [[0 for _ in range(a)] for __ in range(h+1)]

for x in range(m):
    h,w = map(int,input().split())
    l_h[h] += 1
    l_w[w] += 1
    l_hw[h][x] += w

m_h = max(l_h)
m_w = max(l_w)

ans = m_h + m_w

l_h_2 = my_index_multi(l_h,m_h)
l_w_2 = my_index_multi(l_w,m_w)

for i in l_h_2:
    flag = False
    for j in l_w_2:
        if j not in l_hw[i]:
            flag = True
            break
    if flag:
        break
else:
    ans -= 1

print(ans)

### FIXED CODE ###

import sys
import itertools

input = sys.stdin.readline

def my_index_multi(l, x):
    return [k for k, _x in enumerate(l) if _x == x]

h,w,m = map(int,input().split())
l_h = [0]*(h+1)
l_w = [0]*(w+1)
l_b = set()

for _ in range(m):
    h,w = map(int,input().split())
    l_h[h] += 1
    l_w[w] += 1
    l_b.add((h,w))

m_h = max(l_h)
m_w = max(l_w)

l_h_2 = []
for i, x in enumerate(l_h):
    if x == m_h:
        l_h_2.append(i)

l_w_2 = []
for i, x in enumerate(l_w):
    if x == m_w:
        l_w_2.append(i)

ans = m_h + m_w

for i,j in itertools.product(l_h_2,l_w_2):
    if (i,j) not in l_b:
        break
else:
    ans -= 1

print(ans)