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

import sys
input = sys.stdin.readline

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

arr = sorted([i for i in range(a, b+1)])
arr_slice = set(arr[:k]) | set(arr[-k:])
[print(i) for i in sorted(arr_slice)]

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

pre_arr = [i for i in range(a, min(a+k, b+1))]
back_arr = [i for i in range(max(b-k+1, a), b+1)]
arr_slice = set(pre_arr) | set(back_arr)
[print(i) for i in sorted(arr_slice)]
### BUGGY CODE ###

#import sys
#input = sys.stdin.buffer.readline

def main():
    S = list(str(input()))
    a = len(S)
    dp = [[0 for _ in range(13)] for _ in range(a+1)]
    dp[0][0] = 1
    INF = 10**9+7
    
    for i in range(a):
        if S[i] == "?":
            for j in range(10):
                for k in range(13):
                    dp[i+1][(10*k+j)%13] += dp[i][k]%INF
        else:
            num = int(S[i])
            for k in range(13):
                dp[i+1][(10*k+num)%13] += dp[i][k]%INF
    
    print(dp[-1][5]%INF)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
#input = sys.stdin.buffer.readline

def main():
    s = str(input())
    l = len(s)
    ans = [0 for _ in range(13)]
    MOD = 10**9+7
    ans[0] = 1
    
    for st in s:
        dp = [0 for _ in range(13)]
        for i in range(13):
            dp[(10*i)%13] = ans[i]%MOD
        dp += dp
        if st != "?":
            for i in range(13):
                num = int(st)
                ans[i] = dp[i+13-num]
        else:
            for i in range(13):
                ans[i] = sum(dp[i+4:i+14])
    
    print(ans[5]%MOD)

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

from bisect import bisect_left

N=int(input())
*A,=map(int,input().split())
G=[[] for _ in range(N)]
ab = [tuple(map(int,input().split())) for _ in range(N-1)]
for a,b in ab:
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
def bfs():
    from collections import deque
    dp = [[] for _ in range(N)]
    dp[0] = [A[0]]
    seen = [0]*N
    todo = deque()
    seen[0]=1
    todo.append(0)
    while todo:
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          idx = bisect_left(dp[a],A[b])
          if idx == len(dp[a]): dp[b] = dp[a]+[A[b]]
          else: dp[b] = [dp[a][i] if i != idx else A[b] for i in range(len(dp[a]))]
          seen[b] = 1
          todo.append(b)
    return dp
  
dp = bfs()
  
print(*[len(dp[i]) for i in range(N)],sep="\n")

### FIXED CODE ###

from bisect import bisect_left

N=int(input())
*A,=map(int,input().split())
INF=10**20
G=[[] for _ in range(N)]
ab = [tuple(map(int,input().split())) for _ in range(N-1)]
for a,b in ab:
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
def dfs(a0):
    seen =[0]*len(G)
    todo = [~a0, a0]
    while todo:
        a = todo.pop()
        if a >= 0:
            seen[a] = 1
            idx = bisect_left(lis,A[a])
            his[a] = (idx,lis[idx])
            lis[idx] = A[a]
            dp[a] = bisect_left(lis,INF)
            for b in G[a]:
                if seen[b]: continue
                todo.append(~b)
                todo.append(b)
        else:
          idx,val = his[~a]
          lis[idx] = val
    return
  
lis = [INF]*N
dp = [0]*N
his = {}
dfs(0)
print(*dp,sep="\n")
### BUGGY CODE ###

import sys
from collections import Counter

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG: {} -> {}'.format(name, val), file=sys.stderr)
            return None

N, M = map(int, input().split())
L = {}
R = {}

for i in range(N):
    left, right = map(int, input().split())
    if left in L:
        L[left].add(i)
    else:
        L[left] = {i}

    if (right + 1) in R:
        R[right + 1].add(i)
    else:
        R[right + 1] = {i}

# debug(L, locals())
# debug(R, locals())

eki_kaeru = [set()] * (M + 1)
tmp = set()

for eki in range(M + 1):
    if eki in L:
        eki_kaeru[eki] = tmp.union(L[eki])
    else:
        eki_kaeru[eki] = tmp.copy()
    if eki in R:
        eki_kaeru[eki] -= R[eki]

    tmp = eki_kaeru[eki]
    # debug(tmp, locals())

# debug(eki_kaeru, locals())

ans = []

for d in range(1, M + 1):
    buy = set()

    for i in range(0, M + 1, d):
        buy = buy.union(eki_kaeru[i])

    ans.append(len(buy))

print(*ans, sep='\n')


### FIXED CODE ###

import sys
from operator import itemgetter

mod = 10**9 + 7
inf = 1<<30

def solve():
    N, M = map(int, sys.stdin.readline().split())
    sects = []

    for i in range(N):
        li, ri = map(int, sys.stdin.readline().split())

        sects.append((li - 1, ri, ri - li + 1))

    sects.sort(key=itemgetter(2))

    # print(sects)

    print(N)

    left = 0

    ft = FenwickTree([0]*(M + 1))

    for d in range(2, M + 1):
        for j in range(left, N):
            if sects[j][2] >= d:
                left = j
                break
            else:
                ft.add(sects[j][0], 1)
                ft.add(sects[j][1], -1)
        else:
            left = N

        # print('left', left)
        # print(ft.data)

        ans = N - left + sum(ft.get_sum(j) for j in range(d, M + 1, d))
        
        print(ans)

class FenwickTree:
    def __init__(self, a):
        self.n = len(a)
        self.data = [0] + a[:]

        for i in range(1, self.n + 1):
            if i + (i & (-i)) <= self.n:
                self.data[i + (i & (-i))] += self.data[i]

    def add(self, i, x):
        ''' a[i] += x '''
        i += 1 # 0-oringn -> 1-origin

        while i <= self.n:
            self.data[i] += x
            i += i & (-i)

    def get_sum(self, r):
        ''' sum[a_0 .. a_r) '''
        res = 0

        while r > 0:
            res += self.data[r]
            r -= r & (-r)

        return res


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

from collections import deque


h, w = map(int, input().split())
a = []
d = deque([])
hs, ws = set(range(h)), set(range(w))
memo = [[None] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
for i in hs:
    a.append(list(input()))
for i in hs:
    for j in ws:
        if a[i][j] == '#':
            d.append([i, j])
            memo[i][j] = 0


def d_list_update(d, hmax, wmax):
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < hmax) and (0 <= dw + j < wmax) and not(memo[dh + i][dw + j]):
            memo[dh + i][dw + j] = memo[dh][dw] + 1
            d.append([dh + i, dw + j])
    return d


while(d):
    d = d_list_update(d, h, w)
ans = max([max(e) for e in memo])
print(ans)

### FIXED CODE ###

from collections import deque
 
 
h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
d = deque()
memo = [[-1] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
a = tuple(input() for _ in hs)
b = [[i, j] for i in hs for j in ws if a[i][j] == '#']
for i, j in b:
    d.append((i, j))
    memo[i][j] = 0
while d:
    dh, dw = d.popleft()
    for i, j in move:
        dhn, dwn = dh + i, dw + j
        if (0 <= dhn < h) and (0 <= dwn < w) and (memo[dhn][dwn] < 0):
            d.append((dhn, dwn))
            memo[dhn][dwn] = memo[dh][dw] + 1
ans = max([max(e) for e in memo])
print(ans)
### BUGGY CODE ###

import math
import sys
from decimal import *

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

getcontext().prec = 28


aa = [Decimal(f'{b}').log10() for b in a if a != 0]

ans = Decimal('0')

for c in aa:
    ans += c

if ans > 18.0:
    print(-1)
else:
    ans = 1

    for c in a:
        ans *= c

    print(ans)


### FIXED CODE ###

n = int(input())

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

ans = 1

for b in a:
    if b == 0:
        ans = 0
        break
    else:
        ans *= b
        if ans > pow(10, 18):
            ans = -1
            break

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

from itertools import permutations
n,m,r=map(int, input().split())
r_l=[int(i)-1 for i in input().split()]
town = [[0]*n for _ in range(n)]
for i in range(m):
    a,b,c=map(int, input().split())
    town[a-1][b-1]=c
    town[b-1][a-1]=c

for k in range(n):
    for i in range(n):
        for j in range(n):
            town[i][j] = min(town[i][j],town[i][k]+town[k][j])
res = float("INF")
for root in list(permutations(r_l)):
    tmp = 0
    for i in range(1,r):
        tmp += town[root[i]][root[i-1]]
    res = min(tmp,res)

print(res)


### FIXED CODE ###

from itertools import permutations
n,m,r=map(int, input().split())
r_l=[int(i)-1 for i in input().split()]
town = [[float("INF")]*n for _ in range(n)]
for i in range(m):
    a,b,c=map(int, input().split())
    town[a-1][b-1]=c
    town[b-1][a-1]=c

for k in range(n):
    for i in range(n):
        for j in range(n):
            town[i][j] = min(town[i][j],town[i][k]+town[k][j])
res = float("INF")
for root in list(permutations(r_l)):
    tmp = 0
    for i in range(1,r):
        tmp += town[root[i]][root[i-1]]
    res = min(tmp,res)

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

def f(s):
    if s == 0:
        return (0, 0)
    a = s
    b = 1
    k = 2
    while k**2 < 1e9:
        if a <= 1e9 and b <= 1e9:
           break
        if a % k == 0:
            a //= k
            b *= k
        else:
            k += 1
    return (a, b)

s = int(input())
for i in range(100000):
    a, d = f(s - i)
    b, c = f(i)
    if max(a, b, c, b + d) <= 1e9:
        print("%d 0 %d %d 0 %d" % (a, c, b + d, b))
        break

### FIXED CODE ###

ps = [2]
for i in range(3, int(1e9**0.5)):
    n = i
    for p in ps:
        if n % p == 0:
            n //= p
            break
    if n == i:
        ps.append(n)



def f(s):
    if s == 0:
        return (0, 0)
    a = s
    b = 1
    i = 0
    while i < len(ps):
        if a <= 1e9 and b <= 1e9:
            break
        p = ps[i]
        if a % p == 0 and 1e9 < b * p:
            break
        if a % p == 0:
            a //= p
            b *= p
        else:
            i += 1
    return (a, b)

s = int(input())

l = 0
r = s
while l + 1 < r:
    m = (l + r) // 2
    if m ** 2 < s:
        l = m
    else:
        r = m
ds = r**2 - s

a, b = f(ds)
print("0 0 %d %d %d %d" % (r, a, b, r))
### BUGGY CODE ###

import heapq as hq

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

arr = [-i for i in list(map(int,input().split()))]
hq.heapify(arr)

for i in range(m):
    arr[0] = -1*(-1*arr[0]//2)
    hq.heapify(arr)

    
print(-1*sum(arr))
        

### FIXED CODE ###

import heapq as hq

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

arr = [-i for i in list(map(int,input().split()))]
hq.heapify(arr)

for i in range(m):
    hq.heappush(arr, -1*(-1*hq.heappop(arr)//2))

    
print(-1*sum(arr))
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    al = []
    al.append(deque([]))
    for _ in range(n):
        row = list(map(int, input().split()))
        al.append(deque(row))

    # print(al)

    day = 0
    cnt = 0
    max_cnt = n*(n-1)//2
    while True:
        day += 1
        # print('-----',day)
        # print(al)
        already_fights = [False]*(n+1)
        update_flag = False
        for i in range(1,n+1):
            al_i = al[i]
            if not al_i or already_fights[i]: continue
            i_next_rival = al_i[0]

            al_rival_i = al[i_next_rival]
            if not al_rival_i or already_fights[i_next_rival]: continue
            i_next_rival_rival = al_rival_i[0]

            if i_next_rival_rival == i:
                al[i].popleft()
                al[i_next_rival].popleft()
                already_fights[i] = True
                already_fights[i_next_rival] = True
                cnt += 1
                update_flag = True
            else:
                continue
        # print(al)

        if not update_flag:
            print(-1)
            exit()

        if cnt == max_cnt:
            break

    print(day)


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    al = []
    al.append(deque([]))
    for _ in range(n):
        row = list(map(int, input().split()))
        al.append(deque(row))

    # print(al)

    day = 0
    cnt = 0
    max_cnt = n*(n-1)//2
    check_il = [i for i in range(1,n+1)]
    while True:
        next_check_il = check_il[:]
        check_il = []
        day += 1
        already_fights = set()
        update_flag = False
        for i in next_check_il:
            al_i = al[i]
            if not al_i or i in already_fights: continue
            i_next_rival = al_i[0]

            al_rival_i = al[i_next_rival]
            if not al_rival_i or i_next_rival in already_fights: continue
            i_next_rival_rival = al_rival_i[0]

            if i_next_rival_rival == i:
                al[i].popleft()
                al[i_next_rival].popleft()
                already_fights.add(i)
                already_fights.add(i_next_rival)
                check_il.append(i)
                check_il.append(i_next_rival)
                cnt += 1
                update_flag = True
            else:
                continue

        if not update_flag:
            print(-1)
            exit()

        if cnt == max_cnt:
            break

    print(day)


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

N = int(input())

ans = 0
for i in range(1,N+1):
    s = set(str(i))
    if s == {'7','5','3'}:
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())

def dfs(s):
    if int(s) > N:
        return 0
    cnt = 1 if all(s.count(c) for c in '753') else 0
    
    for ss in '753':
        cnt += dfs(s+ss)
    #print(s,cnt)
    
    return cnt
    
print(dfs('0'))
### BUGGY CODE ###

import numpy as np
N,M = list(map(int,input().split()))
A = input().split()
 
count = 0
A = np.array(A,dtype='int64')
B = np.cumsum(A)
C = np.append([0],B)
 
L = (1 for i in range(len(A)+1) for t in range(len(A)+1) if i<t and (C[t] - C[i])%M==0)
print(len(list(L)))

### FIXED CODE ###

import collections
import numpy as np

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

A = np.array(A,dtype='int64')
C = np.append([0],np.cumsum(A))
L = [i%M for i in C]
L_c = collections.Counter(L)

ans = 0
for i in L_c.values():
    S = i * (i-1) / 2
    ans+=S
    
print(int(ans))
### BUGGY CODE ###

N = int(input())
life = list(map(int, input().split()))
while len(life) >1:
    life.sort()
    life_array=[]
    for i in life:
        if i%life[0] != 0 and i not in life_array: life_array.append(i%life[0])
    life = [life[0]] + life_array

print(life[0])

### FIXED CODE ###

N = int(input())
life = list(map(int, input().split()))
while len(life) >1:
    life.sort()
    life_array = [life[0]] + [i%life[0] for i in life if i%life[0] !=0]
    life = life_array
    #for i in life_array:
        #if i not in life:
            #life.append(i)
 
print(life[0])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    ans = 0
    cnt = [[0]*60 for _ in range(60)]
    for _ in range(n):
        a = list(map(str, input().rstrip().split(".")))
        x = 0
        if len(a) == 1:
            x = int(a[0]) * 10**9
        else:
            x = int(a[0]) * 10**9 + int(a[1]) * pow(10, 9-len(a[1]))
        cnt_2, cnt_5 = 0, 0
        while x % 2 == 0:
            cnt_2 += 1
            x //= 2
        while x % 5 == 0:
            cnt_5 += 1
            x //= 5
        for i in range(60):
            for j in range(60):
                if cnt_2 + i >= 18 and cnt_5 + j >= 18:
                    ans += cnt[i][j]
        cnt[cnt_2][cnt_5] += 1
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
ans = 0
cnt = [[0]*20 for _ in range(45)]
for _ in range(n):
    a = list(map(str, input().rstrip().split(".")))
    x = 0
    if len(a) == 1:
        x = int(a[0]) * 10**9
    else:
        x = int(a[0]) * 10**9 + int(a[1]) * pow(10, 9-len(a[1]))
    cnt_2, cnt_5 = 0, 0
    while x % 2 == 0:
        cnt_2 += 1
        x //= 2
    while x % 5 == 0:
        cnt_5 += 1
        x //= 5
    for i in range(45):
        for j in range(20):
            if cnt_2 + i >= 18 and cnt_5 + j >= 18:
                ans += cnt[i][j]
    cnt[cnt_2][cnt_5] += 1
print(ans)
### BUGGY CODE ###

from pprint import pprint
from fractions import gcd
import sys
def input() -> str:
    return sys.stdin.readline()
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n//i)
    return divisors
a, b = map(int, input().split())
cd = sorted(list(make_divisors(a) & make_divisors(b)))
n = len(cd)
divs = [[False for _ in range(n)] for _ in range(n)]
choice = []
answer = 0
for i in cd:
    n = len(choice)
    for j in range(n):
        for k in choice[j]:
            if gcd(i, k) != 1:
                break
        else:
            addition = choice[j] + [i]
            if len(addition) > answer:
                answer = len(addition)
            choice.append(addition)
    choice.append([i])
print(answer if answer != 0 else 1)

### FIXED CODE ###

from fractions import gcd
from math import sqrt
import sys
def input() -> str:
    return sys.stdin.readline()
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n//i)
    return list(divisors)
def is_prime(n):
    if n == 1:
        return False
    for k in range(2, int(sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True
a, b = map(int, input().split())
print(len([div for div in make_divisors(gcd(a, b)) if is_prime(div)]) + 1)
### BUGGY CODE ###

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

for i in range(N):
    B = []
    for j in range(N):
        if i != j:
            B.append(X[j])
    B.sort()
    print(B[int((len(B)-1)/2)])


### FIXED CODE ###

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

Y = sorted(X)

l = Y[N//2-1]
r = Y[N//2]

for x in X:
    if l >= x:
        print(r)
    else:
        print(l)
### BUGGY CODE ###

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

c = collections.Counter(a)

comon = c.most_common()
ans = 0
for i in comon:
  if i[1] != 1:
  	ans += (i[1]*(i[1]-1)//2)
  
for i in a:
  if (ans-int(a.count(i))) < 0:
    print(0)
  else:
    for j in comon:
      if i == j[0]:
        co = j[1]
    print(ans-(co*(co-1)//2)+((co-1)*(co-2)//2))

      

### FIXED CODE ###

import collections
n = int(input())
a = list(map(str,input().split()))
ls = [i for i in range(2*10**5)]
c = collections.Counter(a)
comon = c.most_common()
ans = 0

for i in comon:
    if i != 1:
      ls[int(i[0])] = i[1]
      ans += (i[1]*(i[1]-1)//2)

for i in a:
    co = ls[int(i)]
    print(ans-(co*(co-1)//2)+((co-1)*(co-2)//2))
### BUGGY CODE ###

import itertools

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数


for i in range(N):
    NEXT=[0]*(K+1)
    NOWSUM=list(itertools.accumulate(NOW))
        
    for j in range(K+1):
        if j-A[i]-1>=0:
            NEXT[j]=(NEXT[j]+NOWSUM[j]-NOWSUM[j-A[i]-1])%mod
        else:
            NEXT[j]=(NEXT[j]+NOWSUM[j])%mod
            

    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K])

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数


for i in range(N):
    NEXT=[0]*(K+1)
    NOWSUM=[0]
    for n in NOW:
        NOWSUM.append(NOWSUM[-1]+n)
        
    for j in range(K+1):
        NEXT[j]=(NEXT[j]+NOWSUM[j+1]-NOWSUM[max(0,j-A[i])])%mod

    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K])
### BUGGY CODE ###

from itertools import permutations
n=int(input())
N=list(map(int,input().split()))
ans=[]
for i in list(permutations(N)):
    flag=0
    i=list(i)
    i.insert(0,i[-1])
    i.append(i[1])
    for j in range(1,n):
        if i[j]!=i[j-1]^i[j+1]:break
        else:flag=1
    if flag==1:break
    
if flag:print("Yes")
else:print("No")

### FIXED CODE ###

N=int(input())
A = list(map(int,input().split()))
temp = 0
for i in A:
    temp = temp ^ i
if(temp == 0):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

n = int(input())
tris = list(map(int,input().split()))
tris.sort()
cnt = 0
for i in range(n-2):
    a = tris[i]
    for j in range(i+1,n-1):
        b = tris[j]

        low = j
        high = n
        while high - low > 1:
            mid = low + (high - low) // 2
            c = tris[mid]
            if c < a + b:
                low = mid
            else:
                high = mid
        cnt += low - j
print(cnt)


### FIXED CODE ###

import bisect
n = int(input())
tris = list(map(int,input().split()))
tris.sort()
cnt = 0
for i in range(n-2):
    a = tris[i]
    for j in range(i+1,n-1):
        b = tris[j]
        r = bisect.bisect_left(tris, a+b)
        cnt += r - j - 1
print(cnt)
### BUGGY CODE ###

import sys
import math
import queue
import copy
import bisect#2分探索
from collections import deque #popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s): return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

S = int(input())
#N, K = map(int, input().split())
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=lambda x:x[1],reverse=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)

#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入

ss=str(S)
# #print(ss)
ls=len(ss)
# l=[0]*(ls+1)

    #print(l[i])
#print(l)

import heapq #優先度付きqueue

kl=[0]*2019
kl[0]=1
a = [0]
heapq.heapify(a)  # aを優先度付きキューに

for i in range(0,ls):
    kl[(S%10**(i+1))%2019]+=1
#print(a)


ans=0

for k in kl:
    ans+=k*(k-1)//2

print(ans)
# cur=-1
# ans=0
# for i, li in enumerate(l):
#     if cur==-1:
#         cur=li
#         count=1
#     elif li==cur:
#         count+=1
#     else:
#         ans+=count*(count-1)//2
#         cur=li
#         count=1

# print(ans)

### FIXED CODE ###

import sys
import math
import queue
import copy
import bisect#2分探索
from collections import deque #popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s): return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

ss = input()
#N, K = map(int, input().split())
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=lambda x:x[1],reverse=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)

#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入

#ss=str(S)
# #print(ss)
ls=len(ss)
# l=[0]*(ls+1)

    #print(l[i])
#print(l)

# #優先度付きqueue

kl=[0]*2019
kl[0]=1
# a = [0]
# heapq.heapify(a)  # aを優先度付きキューに

tmp=0
t2=1
for s in reversed(ss):
    tmp=(tmp+int(s)*t2)%2019
    kl[tmp]+=1
    t2=t2*10%2019
    #print(tmp)

#print(a)




ans=0
for k in kl:
    ans+=k*(k-1)//2
print(ans)

# cur=-1
# ans=0
# for i, li in enumerate(l):
#     if cur==-1:
#         cur=li
#         count=1
#     elif li==cur:
#         count+=1
#     else:
#         ans+=count*(count-1)//2
#         cur=li
#         count=1

# print(ans)