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

import sys
input = sys.stdin.readline

INF = float('inf')
N, M = map(int, input().split())

class Edge():
    def __init__(self, start, end, cost):
        self.start = start
        self.end = end
        self.cost = cost
    def __str__(self):
        return 'Edge: {} -> {}, cost {}'.format(self.start, self.end, self.cost)

def bellman_ford(n, es, s):
    dist = [INF] * n
    dist[s] = 0
    # 更新が止まるまで繰り返す O(V*E)
    # i度目の更新までにsを始点として0~i個の辺からなる経路が探索され、その時点の最短経路が計算される
    # 最短経路は最大でもV-1個の頂点しか通らないため、最悪でもv-1回で収束する
    cnt = 0
    while True:
        update = False
        # 辺をすべて見る
        for e in es:
            # aに到達可能かつa経由の方が近ければ更新する
            if dist[e.start] != INF and dist[e.end] > dist[e.start] + e.cost:
                dist[e.end] = dist[e.start] + e.cost
                update = True
                if cnt == n-1 and e.end == n-1:
                  print('inf')
                  sys.exit()
        cnt += 1
        # 一度も更新されなければ終了
        if not update:
            break
    return dist

es = []

for i in range(M):
  a, b, cost = map(int, input().split())
  es.append(Edge(a-1, b-1, -cost))
  # es.append(Edge(b-1, a-1, -cost))


print(-bellman_ford(N, es,0)[N-1])


### FIXED CODE ###

import sys
input = sys.stdin.readline

INF = float('inf')
N, M = map(int, input().split())

class Edge():
    def __init__(self, start, end, cost):
        self.start = start
        self.end = end
        self.cost = cost
    def __str__(self):
        return 'Edge: {} -> {}, cost {}'.format(self.start, self.end, self.cost)

def bellman_ford(n, es, s):
    dist = [INF] * n
    dist[s] = 0
    # 更新が止まるまで繰り返す O(V*E)
    # i度目の更新までにsを始点として0~i個の辺からなる経路が探索され、その時点の最短経路が計算される
    # 最短経路は最大でもV-1個の頂点しか通らないため、最悪でもv-1回で収束する
    cnt = 0
    while True:
        update = False
        # 辺をすべて見る
        for e in es:
            # aに到達可能かつa経由の方が近ければ更新する
            if dist[e.start] != INF and dist[e.end] > dist[e.start] + e.cost:
                dist[e.end] = dist[e.start] + e.cost
                update = True
                if cnt == n-1 and e.end == n-1:
                  print('inf')
                  sys.exit()
        cnt += 1
        # 一度も更新されなければ終了
        if not update or cnt == n:
            break
    return dist

es = []

for i in range(M):
  a, b, cost = map(int, input().split())
  es.append(Edge(a-1, b-1, -cost))
  # es.append(Edge(b-1, a-1, -cost))


print(-bellman_ford(N, es,0)[N-1])
### BUGGY CODE ###


N, W = map(int, input().split())
goods = []
for _ in range(N):
    goods.append(list(map(int, input().split())))

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, W + 1):
        if j - goods[i - 1][0] >= 0:
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j - goods[i - 1][0]] + goods[i - 1][1])
        else:
            dp[i][j] = dp[i-1][j]
# print(dp)
print(dp[-1][-1])

### FIXED CODE ###

import numpy as np

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

# dp = [0] * (weights + 1)
dp = np.zeros(weights + 1, dtype=np.int64)

while N:
    w, v = map(int, input().split())
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
    # for i in range(weights, -1, -1):
    #     if i - w >= 0:
    #         dp[i] = max(dp[i], dp[i - w] + v)
    # print(dp)
    N -= 1
print(dp[-1])
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

a = []
i = 1
cnt = 0
while i != 2 and i not in a:
  a.append(i)
  i = A[i-1]
  cnt += 1

if i == 2:
  print(cnt)
else:
  print(-1)

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

i = 1
cnt = 0
while i != 2 and cnt <= N:
  cnt += 1
  i = A[i-1]
  if i == 2:
    break

if i == 2:
  print(cnt)
else:
  print(-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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


def main():
    N, M =two_int()

    key_list=[]
    treasures=[]

    for i in range(M):
        mon,_ =two_int()
        key_list.append(mon)
        temp = map(lambda x: 1<<(x-1), many_int())
        sums = sum(temp)
        treasures.append(sums)

    max_index=2**N
    INF=10**15

    dp=[INF for i in range(max_index)]
    dp_i=[set([j for j in range(M)]) for i in range(max_index)]
    dp[0]=0

    for i in range(max_index-1):
        
        lists = list( dp_i[i])
        min_key=0
        for j in lists:
            new_i = int(bin(treasures[j] | i),2)
            cost = dp[i] + key_list[j]
            if dp[new_i] > cost:
                dp[new_i] = cost 
                min_key = j
                
        dp_i[i] = dp_i[i] - set([min_key])
        
    goal_index=max_index-1
    if dp[goal_index]!=INF:
        print(dp[goal_index])
    else:
        print(-1)

main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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


def main():
    N, M =two_int()

    key_list=[]
    treasures=[]
    check={}

    for i in range(M):
        mon,_ =two_int()
        temp = map(lambda x: 1<<(x-1), many_int())
        sums = sum(temp)
        
        if sums in check:
            if check[sums] > mon:
                check[sums]=mon
        else:
            check[sums]=mon
            
    for k,v in check.items():
        key_list.append(v)
        treasures.append(k)

    max_index=2**N
    INF=10**15

    dp=[INF for i in range(max_index)]
    dp[0]=0
    M=len(key_list)

    for i in range(max_index-1):
        for j in range(M):
            new_i = int(bin(treasures[j] | i),2)
            cost = dp[i] + key_list[j]
            dp[new_i] = min(dp[new_i], cost) 
        
    goal_index=max_index-1
    if dp[goal_index]!=INF:
        print(dp[goal_index])
    else:
        print(-1)

main()
### BUGGY CODE ###

def main():
    # input
    import sys
    input = sys.stdin.readline
    MAX = 10**9+7

    n = int(input())
    a = tuple(map(int, input().split()))
    ans = 0
    for first, i in enumerate(a[:n-1]):
        for j in a[first:n]:
            ans += i^j
    print(ans%MAX)



    # calc


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    MAX = 10**9+7

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

    li = [0]*61
    for i in a:
        for j in range(61):
            li[j] += i&1
            i >>= 1
    ans = 0
    bit = 1
    for i in li:
        ans += bit * i * (n-i)
        bit <<= 1
    print(ans%MAX)

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

n,q =map(int,input().split())
S = input()
LR = [list(map(int,input().split())) for _ in range(q)]
flag = True
Ans = [0]*q
count = -1

for l,r in LR:
    count += 1
    temp = ""
    for s in S[l-1:r]:
        if temp =="A" and s =="C":
            Ans[count] += 1
        temp = s
print(*Ans,sep = "\n")

### FIXED CODE ###

n,q =map(int,input().split())
S = input()
LR = [list(map(int,input().split())) for _ in range(q)]
temp = ""
S2 = []

for s,i in zip(S,range(n)):
    if temp == "A" and s == "C":
        S2.append(i)
    temp = s

import bisect as bi

for l,r in LR:
    ans = - bi.bisect_right(S2,l-1) + bi.bisect_right(S2,r-1)
    print(ans)
### BUGGY CODE ###

import numpy as np

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

matrix = [[0 for i in range(N)] for j in range(N)]

for i in range(N - 1):
    matrix[i][i] = 1
    matrix[i][i+1] = 1

matrix[N-1][N-1] = 1
matrix[N-1][0] = 1

matrix = np.array(matrix)
A = np.array(A)
A = A.T

inv_mat = np.linalg.inv(matrix)

ans = np.dot(inv_mat, A)
ans = np.dot(2, ans)

ans = list(map(int, ans))

print(*ans)

### FIXED CODE ###

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

x0 = 0

for i in range(N):
    x0 += A[i] * (-1)**i / 2

x = [x0]

for i in range(N - 1):
    x.append(A[i] - x[i])

ans = []

for i in range(N):
    ans.append(int(x[i] * 2))

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

N = int(input())
D = [int(x) for x in input().split()]
D = sorted(D)
if D[0] > 0:
    print(0)
else:
    new_l = list()
    for n in range(1,N+1):
        count = 0
        for d in D:
            if d == n:
                count += 1
        new_l.append(count)
    res = 1
    for n in range(len(new_l)-1):
        res *= new_l[n]**new_l[n+1]
        res = res%998244353
    print(res)


### FIXED CODE ###

N = int(input())
D = [int(x) for x in input().split()]
new_l = [0 for n in range(max(D)+1)]
for n in range(N):
    new_l[D[n]] += 1
if new_l[0] == 1 and D[0] == 0:
    res = 1
    for n in range(max(D)):
        res *= pow(new_l[n],new_l[n+1],998244353)
    print(res%998244353)
else:
    print(0)
### BUGGY CODE ###

n, m = map(int, input().split())
p = []
s = []
for i in range(m):
    input_p, input_s = input().split()
    p.append(int(input_p))
    s.append(input_s)

ac_list = []
wa_list = [0] * n
wa_count = 0
for i in range(m):
    if p[i] not in ac_list:
        if s[i] == 'AC':
            ac_list.append(p[i])
            wa_count += wa_list[p[i]-1]
        else:
            wa_list[p[i]-1] += 1
        
print(len(ac_list), wa_count)

### FIXED CODE ###

n, m = map(int, input().split())
ps = [[0, 0] for i in range(n)]  
wa_count = 0
ac_count = 0
for i in range(m):
    input_p, input_s = input().split()
    if ps[int(input_p)-1][0] <= 0:
        if input_s == 'AC':
            ps[int(input_p)-1][0] += 1
        else:
            ps[int(input_p)-1][1] += 1
for i in ps:
    if i[0] == 1:
        ac_count += 1
        wa_count += i[1]

print(ac_count, wa_count)
### BUGGY CODE ###

N = int(input())
A = [list(map(lambda x: int(x) - 1, input().split(" "))) for i in range(N)]

class Cycle(Exception):
    pass

paths = {}
st = set()

def dfs(a, b):

    node = (min(a, b), max(a, b))

    if node in paths:
        return paths[node]

    if node in st:
        raise Cycle()

    st.add(node)

    ns = [1]
    i = A[a].index(b)
    for j in range(i):
        ns.append(1 + dfs(a, A[a][j]))

    i = A[b].index(a)
    for j in range(i):
        ns.append(1 + dfs(b, A[b][j]))

    st.remove(node)
    paths[node] = max(ns)
    return paths[node]

ans = -1
try:
    for i in range(N):
        for j in range(N - 1):
            ans = max(ans, dfs(i, A[i][j]))
    print(ans)
except Cycle:
    print(-1)


### FIXED CODE ###

import sys

N = int(input())
A = [list(map(lambda x: int(x) - 1, input().split(" "))) for i in range(N)]

canUse = set(range(N))

ans = 0
done = 0
while done < N:
    ans += 1
    canUseNew = set()
    # print("LC", len(canUse))
    for n in canUse:
        if not A[n]:
            continue

        first = A[n][-1]
        if first in canUseNew or n in canUseNew:
            continue

        if A[first][-1] == n:
            # print("Do", n + 1, first + 1)
            A[n].pop()
            if len(A[n]) == 0:
                done += 1
            A[first].pop()
            if len(A[first]) == 0:
                done += 1
            canUseNew.add(n)
            canUseNew.add(first)

    if len(canUseNew) == 0:
        print(-1)
        sys.exit(0)
    canUse = canUseNew

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

N,M=map(int,input().split())
list1=[int(input()) for i in range(M)]
list2=[1]
if 1 in list1:
    list2.append(0)
else:
    list2.append(1)
for i in range(N-1):
    if i+2 in list1:
        list2.append(0)
    else:
        list2.append(list2[i]+list2[i+1])
print(list2[N]%1000000007)

### FIXED CODE ###

N,M=map(int,input().split())
list1=set([int(input()) for i in range(M)])
list2=[1]+[0]*N
if not 1 in list1:
    list2[1]=1
for i in range(N-1):
    if not i+2 in list1:
        list2[i+2]=(list2[i]+list2[i+1])%1000000007
print(list2[N])
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]
BC.sort(key=lambda x: x[1], reverse=True)
D = []
for B, C in BC:
    D += [C] * B
A+=D
A.sort(reverse = True)
print(sum(A[:N]))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]
BC.sort(key=lambda x: x[1], reverse=True)
D = []
sum_B=0
for B, C in BC:
    D += [C] * B
    sum_B += B
    if sum_B>N:
        break

A+=D
A.sort(reverse = True)
print(sum(A[:N]))
### BUGGY CODE ###

# Author: cr4zjh0bp
# Created: Sun Mar 22 23:25:40 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n = ni()
a = nin(n)

ans = 0
flag = True
i = 0
p = 0
while i != 1:
    if p == a[i] - 1:
        flag = False
        break
    p = i
    i = a[i] - 1
    ans += 1

print(ans if flag else -1)

### FIXED CODE ###

# Author: cr4zjh0bp
# Created: Sun Mar 22 23:25:40 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n = ni()
a = nin(n)

i = 0
ans = 0
flag = True
while i != 1:
    if ans > n:
        flag = False
        break
    i = a[i] - 1
    ans += 1

print(ans if flag else -1)
### BUGGY CODE ###

n = int(input())
ls = []
for i in range(n):
    ls.append(int(input()))
maxnum = max(ls)
for i in range(n):
    if maxnum > ls[i]:
        print(maxnum)
    else:
        lstmp = ls[0:i] + ls[i+1:]
        print(max(lstmp))


### FIXED CODE ###

n = int(input())
ls = []
for i in range(n):
    ls.append(int(input()))
maxnum = max(ls)
ind = ls.index(maxnum)
ls.remove(maxnum)
secondnum = max(ls)
ls = ls[0:ind] + [maxnum] + ls[ind:]
#print(ls)
if maxnum == secondnum:
    for i in range(n):
        print(maxnum)
    quit()
for i in range(n):
    if ls[i] == maxnum:
        print(secondnum)
    else:
        print(maxnum)
### BUGGY CODE ###

# Fast IO (only use in integer input)

import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N,K = map(int,input().split())
a = list(map(int,input().split()))
ans = ""
for i in range(N):
    if i < K:
        continue
    if a[i] <= a[i - K]:
        ans += "No"
    else:
        ans += "Yes"
    if i != N-1:
        ans += "\n"
print(ans)




### FIXED CODE ###

# Fast IO (only use in integer input)

import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N,K = map(int,input().split())
a = list(map(int,input().split()))
ans = ""
for i in range(N):
    if i < K:
        continue
    if a[i] <= a[i - K]:
        ans += "No"
    else:
        ans += "Yes"
    if i != N-1:
        ans += "\n"
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

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

#ans = [0]*n
#
#for i in range(k-1, n):
#    tmp = 1
#    for a in A[i-k+1:i+1]:
#        tmp *= a
#    ans[i] = tmp
#
#ans = ans[k-1:]
#
#for i in range(len(ans)-1):
#    if ans[i] < ans[i+1]:
#        print('Yes')
#    else:
#        print('No')

val = 1
for a in A[:k]:
    val *= a
ans = [val]
pos = k
while pos < n:
    tmp = ans[-1]*A[pos]//A[pos-k]
    ans.append(tmp)
    pos += 1
for i in range(len(ans)-1):
    if ans[i] < ans[i+1]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

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

#val = 1
#for a in A[:k]:
#    val *= a
#ans = [val]
#pos = k
#while pos < n:
#    tmp = ans[-1]*A[pos]//A[pos-k]
#    ans.append(tmp)
#    pos += 1
#
#for i in range(len(ans)-1):
#    if ans[i] < ans[i+1]:
#        print('Yes')
#    else:
#        print('No')
        
for i in range(n-k):
    pos = k+i
    if A[pos] > A[pos-k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import Counter
def main():
    S = list(map(int, input().rstrip("\r\n")))
    N = len(S)
    P = 2019
    S.reverse()
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if S[i] % P == 0:ans += N-i
    else:
        D = [0] * (N+1)
        tenpow = 1
        for i in range(N):
            S[i] = S[i] * tenpow % P
            tenpow *= 10 % P
            D[i+1] = (S[i] + D[i]) % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import Counter
def main():
    S = list(map(int, input().rstrip("\r\n")))
    N = len(S)
    P = 2019
    S.reverse()
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if S[i] % P == 0:ans += N-i
    else:
        D = [0] * (N+1)
        tenpow = 1
        for i in range(N):
            S[i] = S[i] * tenpow % P
            tenpow *= 10
            tenpow %= P
            D[i+1] = (S[i] + D[i]) % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

X = input()
def erase(string,word):
    for i in range(10**5):
        note = string
        string = string.replace(word,"")
        if note == string:
            break
    return string
for e in ["SSSSTTTT","SSSTTT","SSTT","ST"]:
    X = erase(X,e)
print(len(X))

### FIXED CODE ###

X = input()
stack = []
for e in X:
    if e == "S":
        stack.append(e)
    elif stack == []:
        stack.append(e)
    elif stack[-1] == "T":
        stack.append(e)
    elif stack[-1] == "S":
        stack.pop(-1)
print(len(stack))
### BUGGY CODE ###

def main():
  def binary_search(left,right,x):
    while left+1!=right:
      mid = (right+left)//2
      if XH[mid][0]<=x+2*D:
        left = mid
      else:
        right = mid
    return left
  
  def cal(h,i,a,ans):
    b = math.ceil(h/A)
    ans += b
    H[i:a+1:]-=b*A
    return ans
  
  N,D,A = map(int,input().split())
  import numpy as np
  import math
  XH = [list(map(int,input().split())) for _ in range(N)]
  XH = sorted(XH)
  ans = 0
  l=[0]*N
  x = XH[0][0]
  l[0]=binary_search(0,N,x)
  for i in range(1,N):
    x = XH[i][0]
    l[i]=binary_search(l[i-1],N,x)
  H = np.array([xh[1] for xh in XH])
  for i,a in enumerate(l):
    h = H[i]
    if h<=0:
      continue
    else:
      ans = cal(h,i,a,ans)
  print(ans)
  
main()

### FIXED CODE ###

def main():
  N,D,A = map(int,input().split())
  XH = [list(map(int,input().split())) for _ in range(N)]
  XH = sorted(XH)
  ans = 0
  S = [0]*(N+1)
  x = XH[0][0]
  h = XH[0][1]
  j = 0
  b = (h+A-1)//A
  ans += b
  y = b*A
  while True:
    if j+1>=N:
      break
    if XH[j+1][0]<=x+2*D:
      j+=1
    else:
      break
  S[0]+=y
  S[j+1]-=y
  S[1]+=S[0]
  for i in range(1,N):
    xh = XH[i]
    h = xh[1]
    s = S[i]
    rec = h-s
    if rec<=0:
      S[i+1]+=s
      continue
    else:
      x = xh[0]
      j = max(j,i)
      while True:
        if j+1>=N:
          break
        if XH[j+1][0]<=x+2*D:
          j+=1
        else:
          break
      b = (rec+A-1)//A
      ans += b
      y = b*A
      S[i]+=y
      S[j+1]-=y
      S[i+1]+=s+y
  print(ans)
main()
### BUGGY CODE ###

K = int(input())
ans = 0
for A in range(1, K+1):
  for B in range(1, K+1):
    a = A
    b = B
    gcd_AB = 0
    while gcd_AB == 0:
      if a > b:
        a = a + b
        b = a - b
        a = a - b # 必ず c <= d になる
      if b%a == 0:
        gcd_AB = a
      else:
        b = b%a
    for C in range(1, K+1):
      c = C
      gcd_ab = gcd_AB
      gcd_ABC = 0
      while gcd_ABC == 0:
        if gcd_ab > c:
          gcd_ab = gcd_ab + c
          c = gcd_ab - c
          gcd_ab = gcd_ab - c # 必ず c <= d になる
        if c%gcd_ab == 0:
          gcd_ABC = gcd_ab
        else:
          c = c%gcd_ab
      ans += gcd_ABC
print(ans)

### FIXED CODE ###

import math

K = int(input())
ans = 0
for A in range(1, K+1):
  for B in range(1, K+1):
    AB = math.gcd(A, B)
    for C in range(1, K+1):
      ans += math.gcd(AB, C)
print(ans)
### BUGGY CODE ###

import numpy as np
from collections import Counter

def resolve():
    s = input()

    mod_table = np.zeros(shape=len(s), dtype=int)
    for i in reversed(range(len(s) - 1)):
        mod_table[i] = int(s[i:]) % 2019

    count = Counter(mod_table)

    ans = 0
    for num_dup in count.values():
        if num_dup >= 2:
            ans += (num_dup * (num_dup - 1)) / 2

    print(int(ans))
    
resolve()

### FIXED CODE ###

def resolve():
    s = [int(i) for i in input()]
    p_cnt = 0

    p = 2019

    s = s[::-1]
    div_dic = dict(zip(range(p), [0] * p))
    tmp = 0

    for i in range(len(s)):
        tmp += s[i] * pow(10, i, p)
        tmp %= p
        div_dic[tmp] += 1

    for v in div_dic.values():
        p_cnt += v * (v - 1)
    p_cnt //= 2
    p_cnt += div_dic.get(0)


    print(p_cnt)
    
resolve()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
m = 1
if 0 in a:
    m = 0
else:
    for i in a:
        m *= i
        if m > 10**18:
            m = -1
print(m)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
m = 1
if 0 in a:
    m = 0
else:
    for i in a:
        m *= i
        if m > 10**18:
            m = -1
            break
print(m)
### BUGGY CODE ###

N = int(input())
s = input().split()
a = [int(i) for i in s]

b = []

for i in range(N) : 
    if i % 2 == 0 : b.append(a[i])
    if i % 2 == 1 : b.insert(0 , a[i])

if i % 2 == 0 : b.reverse()        

print(" ".join(map(str, b)))

### FIXED CODE ###

from collections import deque
N = int(input())
s = input().split()
a = [int(i) for i in s]

b = deque()

for i in range(N) : 
    if i % 2 == 0 : b.append(a[i])
    if i % 2 == 1 : b.appendleft(a[i])

if i % 2 == 0 : b.reverse()        

print(" ".join(map(str, b)))
### BUGGY CODE ###

import fractions

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

l = a[0]
for i in range(1, n):
    l = l * a[i] // fractions.gcd(l, a[i])

count = 0

for i in a:
  count += l//i
  count %= (10**9+7)

print(count)

### FIXED CODE ###

import fractions

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

l = a[0]
for i in range(1, n):
    l = l * a[i] // fractions.gcd(l, a[i])

count = 0


for i in a:
  count += l//i
count %= (10**9+7)

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

s = input()
q = int(input())
state = 0
for i in range(q):
    query = list(input().split())
    if query[0] == "2":
        if state%2 == 0:
            if query[1] == "1":
                s = query[2] + s
            else:
                s = s + query[2]
        else:
            if query[1] == "1":
                s = s +  query[2]
            else:
                s = query[2] + s
    else:
        state += 1
ans = ""
if len(s)>1:
    if state%2==1 and state != 1:
        for i in range(len(s)):
            ans += s[-1-i]
        print(ans)
    else:
        print(s)
else:
    print(s)

### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())
state = 0
for i in range(q):
    query = input().split()
    if query[0] =="1":
        state +=1
    else:
        if (int(query[1])+state)%2 == 1:
            s.appendleft(query[2])
        else:
            s.append(query[2])
if state%2 == 1:
    s.reverse()
print("".join(s))