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

N, M = map(int,input().split())
li = [0]*N
for i in range(M):
    L, R = map(int,input().split())
    for j in range(L-1,R,1):
        li[j] += 1
print(li.count(M))

### FIXED CODE ###

N, M = map(int,input().split())
li1 = []
li2 = []
for i in range(M):
    L, R = map(int,input().split())
    li1.append([L,R])
    li2.append([R,L])
li1.sort()
li2.sort(reverse=True)
if (li2[M-1][0])<(li1[M-1][0]):
    print("0")
    exit()
print((li2[M-1][0])-(li1[M-1][0])+1)
### BUGGY CODE ###

s = list(input())
q = int(input())

revs = 0

for i in range(q):
    ins = input().split()
    if(ins[0] == "1"):
        revs += 1
    else:
        if (ins[1] == "1" and revs%2 == 0 or ins[1] =="2" and revs%2 == 1):
            s.insert(0, ins[2])
        else:
            s.append(ins[2])

if(revs %2 == 0):
    for j in s:
        print(j, end="")
else:
    for j in reversed(s):
        print(j, end="")
print()


### FIXED CODE ###

s = list(input())
q = int(input())

revs = 0
front = []
rear = []

for i in range(q):
    ins = input().split()
    if(ins[0] == "1"):
        revs += 1
    else:
        if (ins[1] == "1" and revs%2 == 0 or ins[1] =="2" and revs%2 == 1):
            front.extend(ins[2])
        else:
            rear.extend(ins[2])

if (revs % 2 == 0):
    for j in reversed(front):
        print(j, end="")
    for j in s:
        print(j, end="")
    for j in rear:
        print(j, end="")
else:
    for j in reversed(rear):
        print(j, end="")
    for j in reversed(s):
        print(j, end="")
    for j in front:
        print(j, end="")
print()
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    N, Ma, Mb = map(int, input().split())
    a = [None] * N
    b = [None] * N
    c = [None] * N
    for i in range(N):
        a[i], b[i], c[i] = map(int, input().split())

    INF = 10**12
    dp = [[INF] * 401 for _ in range(401)]
    dp[0][0] = 0

    for i in range(N):
        for j in range(400,-1,-1):# 後ろから更新すること
            for k in range(400,-1,-1):
                if j - a[i] >= 0 and k - b[i] >= 0:
                    dp[j][k] = min(dp[j][k], dp[j-a[i]][k-b[i]]+c[i])
    
    ans = INF
    for j in range(400):
        for k in range(400):
            if j*Mb == k*Ma != 0:
                ans = min(ans,dp[j][k])
    print(ans) if ans < INF else print(-1)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    N, Ma, Mb = map(int, input().split())
    a = [None] * N
    b = [None] * N
    c = [None] * N
    for i in range(N):
        a[i], b[i], c[i] = map(int, input().split())

    INF = 10**12
    dp = [[[INF] * 401 for _ in range(401)] for _ in range(N+1)]
    dp[0][0][0] = 0

    for i in range(N):
        for j in range(400,-1,-1):# 後ろから更新すること
            for k in range(400,-1,-1):
                dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
                if j - a[i] >= 0 and k - b[i] >= 0:
                    dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j-a[i]][k-b[i]]+c[i])
    
    ans = INF
    for j in range(400):
        for k in range(400):
            if j*Mb == k*Ma != 0:
                ans = min(ans,dp[N][j][k])
    print(ans) if ans < INF else print(-1)

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

import sys
import copy
from collections import deque

n = int(input())
a = [deque(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]

day = 0
setn = set(range(n))
while True:
    popped = 0
    plist = set()
    zeros = 0
    tmpns = copy.copy(setn)
    for i in setn:
        if len(a[i]) == 0:
            tmpns.remove(i)
            continue
        if i in plist:
            continue
        num = a[i][0] - 1
        if num < i:
            continue
        if num in plist:
            continue
        if a[num][0] - 1 == i:
            plist.add(num)
            a[i].popleft()
            a[num].popleft()
            popped += 1
    if popped == 0:
        if len(tmpns) == 0:
            break
        else:
            day = -1
            break
    setn = tmpns
    day += 1

print(day)


### FIXED CODE ###

import sys
from collections import deque

n = int(input())
a = [deque(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]

current = []

for i in range(n):
    target = a[i][0] -1
    if a[target][0] -1 == i and i < target:
        current.append([i, target])

day = 0
zc = 0
while True:
    popped = 0
    plist = set()
    zeros = 0
    tc = []
    for i in current:
        a[i[0]].popleft()
        a[i[1]].popleft()
        if len(a[i[0]]) > 0:
            plist.add(i[0])
        else:
            zc += 1
        if len(a[i[1]]) > 0:
            plist.add(i[1])
        else:
            zc += 1
    for i in plist:
        target = a[i][0] -1
        if a[target][0] -1 == i:
            if not target in plist or i < target:
                tc.append([i, target])
    day += 1
    if len(tc) == 0:
        break
    current = tc

if zc != n:
    day = -1

print(day)
### BUGGY CODE ###

import math

K = int(input())

ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for l in range(1,K+1):
           ab = math.gcd(i,j)
           abc = math.gcd(ab,l)
           ans += abc


print(ans)


### FIXED CODE ###

import math

K = int(input())

ans = 0
'''
for i in range(1,K+1):
    for j in range(1,K+1):
        for l in range(1,K+1):
           ab = math.gcd(i,j)
           abc = math.gcd(ab,l)
           print(i,j,l)
           ans += abc
'''
           
for i in range(1,K+1):
    for j in range(i,K+1):
        for l in range(j,K+1):
           ab = math.gcd(i,j)
           abc = math.gcd(ab,l)
           #print(i,j,l)
           if i == j and j == l:#３つすべて同じ数字のとき
               abc = abc
               #print('abc',abc)
           elif i == j or j == l or i == l:#２つの数字が同じ時
               abc = 3*abc
               #print('abc',abc)
           elif i != j and i != l and j != l:#３つの数字がすべて違うとき
               abc = 6*abc
               #print('abc',abc)
           
           ans += abc
           #print(ans,abc)


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

import sys
sys.setrecursionlimit(10**6)

#a = int(input())
n, m = map(int, input().split())
a = list(map(int, input().split()))
#s = input()
#s,t = input().split()
#a = [int(input()) for _ in range(n)]
#
readline = sys.stdin.readline
#n,m = [int(i) for i in readline().split()]
bc = [[int(i) for i in readline().split()] for _ in range(m)]

import heapq

heapq.heapify(a)

for i in range(m):
    b = bc[i][0]; c = bc[i][1]
    for _ in range(b):
        if a[0] < c:
            _ = heapq.heappop(a)
            heapq.heappush(a, c)
        else:
            break
    
ans = sum(a)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
readline = sys.stdin.readline
A = [int(i) for i in readline().split()]

A.sort()

CB = []
for _ in range(m):
    b, c = [int(i) for i in readline().split()]
    CB.append([c, b])
    
CB.sort(reverse=True)

idx = 0
c = 0
for i in range(n):
    if A[i] < CB[idx][0]:
        A[i] = CB[idx][0]
        c += 1
    if CB[idx][1] <= c:
        idx += 1
        c = 0
    if idx >= m:
        break

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

import sys
import heapq
input = sys.stdin.readline

n, m = map(int, input().split())
sum = 0
# Aiが最小のものから順に選ぶ
# 重複するときは最大金額を選び残りはAiを+1する

# Ai>Mのものは最初から除外
# 受け取りにA日かかるということはM-A+1日目までに受けなければならない
# index = M-A(day)
# element = B(reword)

schedule = [[] for _ in range(m+1)]
for _ in range(n):
    day, reword = map(int, input().split())
    if day > m:
        continue
    schedule[m-day+1].append(reword)

for i in range(m, 0, -1):
    if not schedule[i]:
        del schedule[i]
        continue
    max_reword = heapq.nlargest(1, schedule[i])
    sum += max_reword[0]
    schedule[i].remove(max_reword[0])
    if schedule[i]:
        schedule[i-1].extend(schedule[i])
    del schedule[i]

print(sum)


### FIXED CODE ###

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

n, m = map(int, input().split())
# Ai>Mのものは最初から除外
# Aiが最小のものから順に選ぶ

# index = A(day-1), element = B(reword)
schedule = [[] for _ in range(m)]
for _ in range(n):
    day, reword = map(int, input().split())
    if day > m:
        continue
    schedule[day-1].append(reword)

hq = []
sum = 0

for i in range(m):
    while schedule[i]:
        heappush(hq, -schedule[i][-1])
        del schedule[i][-1]

    if hq:
        sum -= heappop(hq)

print(sum)
### BUGGY CODE ###

N = int(input())
y = pow(10,18)
x = 1

for i in map(int,input().split()):
    x *= i
if x > y:
    print("-1")
else:
    print(x)

### FIXED CODE ###

N = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 1
rec = True
for i in range(N):
    ans = ans * l[i]
    if ans > 10**18:
        rec = False
        break

if rec:
    print(ans)
else:
    print('-1')
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*n
for i in range(1,n):
  dp[i]=min(dp[j]+abs(h[i]-h[j]) for j in range(max(i-k,0),i))
print(dp[n-1])

### FIXED CODE ###

def main():
	N, K = map(int, input().split())
	h = list(map(int, input().split()))
	dp=[0]*N
	for i in range(1,N):
		dp[i] = min(dp[g] + abs(h[i] - h[g]) for g in range(max(i-K,0), i))
	print(dp[N-1])
main()
### BUGGY CODE ###

from bisect import bisect

n = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for i in range(n):
	for j in range(i+1, n):
		for k in range(j+1, bisect(L, L[i]+L[j]-1)):
			ans+=1
print(ans)

### FIXED CODE ###

from bisect import bisect

n = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for i in range(n):
	for j in range(i+1, n):
		ans+=bisect(L, L[i]+L[j]-1)-j-1
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
mod=10**9+7
b,w=map(int,input().split())
n=b+w

factorial=[1]
for i in range(1,n+1):
    factorial.append(factorial[i-1]*i%mod)
inverse=[0]*(n+1)
inverse[-1]=pow(factorial[-1],mod-2,mod)
for i in range(n-1,-1,-1):
    inverse[i]=inverse[i+1]*(i+1)%mod
def comb(n,r):
    if n<r:
        return 0
    return factorial[n]*inverse[r]*inverse[n-r]%mod
def power(x,n,mod):
    if n==0:
        return 1
    elif n%2:
        return power(x,n//2,mod)**2*x%mod
    else:
        return power(x,n//2,mod)**2%mod
def modinv(n,mod):
    return power(n,mod-2,mod)

Pb,Pw=[0]*n,[0]*n
inv2=modinv(2,mod)
for i in range(1,n):
    Pb[i]=(Pb[i-1]+comb(i-1,b-1)*power(inv2,i,mod))%mod
    Pw[i]=(Pw[i-1]+comb(i-1,w-1)*power(inv2,i,mod))%mod
for i in range(n):
    print((1-Pb[i]+Pw[i])*inv2%mod)

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
mod=10**9+7
b,w=map(int,input().split())
n=b+w

def power(x,n):
    if n==0:
        return 1
    elif n%2:
        return power(x,n//2)**2*x%mod
    else:
        return power(x,n//2)**2%mod
def modinv(n):
    return power(n,mod-2)

factorial=[1]
for i in range(1,n+1):
    factorial.append(factorial[i-1]*i%mod)
inverse=[0]*(n+1)
inverse[-1]=modinv(factorial[-1])
for i in range(n)[::-1]:
    inverse[i]=inverse[i+1]*(i+1)%mod
def comb(n,r):
    if n<r or r<0:
        return 0
    return factorial[n]*inverse[r]*inverse[n-r]%mod

Pb,Pw=[0]*n,[0]*n
inv2=modinv(2)
P=[1]*(n+1)
for i in range(1,n+1):
    P[i]=P[i-1]*inv2%mod
for i in range(1,n):
    Pb[i]=(Pb[i-1]+comb(i-1,b-1)*P[i])%mod
    Pw[i]=(Pw[i-1]+comb(i-1,w-1)*P[i])%mod
for i in range(n):
    print((1-Pb[i]+Pw[i])*inv2%mod)
### BUGGY CODE ###

import queue
N=int(input())
A=sorted([int(i) for i in input().split()],reverse=True)
B=[2**(len(bin(i))-2) for i in A]
R=[0 for i in range(N)]
D=dict()
for i in range(N):
    if not(A[i] in D):
        D[A[i]]=queue.Queue()
    D[A[i]].put(i)
ans=0
for i in range(N):
    if R[i]==1:
        continue
    if (B[i]-A[i]) in D:
        flag=1
        if not(D[B[i]-A[i]].empty()):
            j=D[B[i]-A[i]].get()
            if i!=j:
                R[i]=1
                R[j]=1
                #print(i,j)
                ans+=1
            else:
                if not(D[B[i]-A[i]].empty()):
                    j=D[B[i]-A[i]].get()
                    R[i]=1
                    R[j]=1
                    #print(i,j)
                    ans+=1
print(ans)



### FIXED CODE ###

N=int(input())
A=sorted([int(i) for i in input().split()],reverse=True)
B=[2**(len(bin(i))-2) for i in A]
D=dict()
for i in range(N):
    if not(A[i] in D):
        D[A[i]]=1
    else:
        D[A[i]]+=1
ans=0
for i in range(N):
    if D[A[i]]<=0:
        continue
    if B[i]==2*A[i]:
        if D[A[i]]>=2:
            D[A[i]]-=2
            ans+=1
    else:
        if (B[i]-A[i]) in D:
            if D[B[i]-A[i]]!=0:
                D[A[i]]-=1
                D[B[i]-A[i]]-=1
                ans+=1
print(ans)
### BUGGY CODE ###

x, k, d = map(int, input().split())
x = abs(x)
if x > k*d:
    print(x-k*d)
else:
    for i in range(1,k+1):
        p = x-i*d
        c = k-i
        if p <= 0:
            if c%2 != 0:
                print(abs(d+p))
                break
            elif c%2 == 0:
                print(abs(p))
                break

### FIXED CODE ###

x, k, d = map(int, input().split())
x = abs(x)
if x > k*d:
    print(x-k*d)
else:
    p = x//d
    c = k-p
    if p == 0 or p==1:
          for i in range(1,k+1):
            p2 = x-i*d
            c = k-i
            if p2 <= 0:
                if c%2 != 0:
                    print(abs(d+p2))
                    break
                elif c%2 == 0:
                    print(abs(p2))
                    break
    elif (c%2 == 0):
        print(abs(x-p*d))
    else:
        print(abs(d-abs(x-p*d)))
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
for i in range(1,n):
    print(li.count(i))
print(0)

### FIXED CODE ###

n = int(input())
li = [0]*n
li1 = list(map(int,input().split()))
for i in range(n-1):
    li[li1[i]-1] += 1
for i in range(n):
    print(li[i])
### BUGGY CODE ###

import numpy as np
N,K = map(int,input().split())
h = list(map(int,input().split()))
dp=np.array([0 for i in range(N)])
dp[0]= 0
if N<=K:
    dp[N-1]=abs(h[0]-h[N-1])
else:   
    for j in range(1,K+1):
        dp[j]= abs(h[0]-h[j])
    
    for i in range(K,N):
        
        
        dp[i]= min(dp[i-k]+abs(h[i-k]-h[i]) for k in range(1,K+1))
        
        #dp[i]=np.min(list1)
         
print(dp[N-1])

### FIXED CODE ###

import numpy as np
N,K = map(int,input().split())
h = np.array(list(map(int,input().split())))
dp=np.array([0 for i in range(N)])
dp[0]= 0
dp[1]=abs(h[1]-h[0])
if N<=K:
    dp[N-1]=abs(h[0]-h[N-1])
else:  
    for i in range(2,N):
      j=max(0,i-K)
      dp[i]=np.min(dp[j:i]+np.abs(h[i]-h[j:i]))
      #dp[i]=min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1,min(k+1,i+1))])
print(int(dp[-1]))
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
MOD = 10 ** 9 + 7
ret = 0
for i in range(n-1):
  for j in range(i+1,n):
    ret += ((A[i] %MOD) * A[j]) % MOD
    ret = ret % MOD
print(ret)

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
MOD = 10 ** 9 + 7
ret = 0
S = [A[0]]
for i in range(1, n):
  S.append(S[i-1] +A[i])

for i in range(n):
  ret += A[i] * (S[-1]-S[i])
  ret = ret % MOD
print(ret)
### BUGGY CODE ###

A = [0] * (2 * 10**5)

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)


### FIXED CODE ###

from collections import defaultdict
from bisect import bisect_right

def sol():
    S = input()
    T = input()

    setS = set(S)
    setT = set(T)
    for t in setT:
        if not t in setS:
            print('-1')
            return

    posS = defaultdict(list)

    for i, s in enumerate(S):
        posS[s].append(i)

    for s in enumerate(S):
        posS[s].sort()

    prev = -1
    ans = 0
    N = len(S)

    for t in T:
        next = bisect_right(posS[t], prev)
        if next >= len(posS[t]):
            ans += N - prev
            ans += posS[t][0]
            prev = posS[t][0]
        else:
            ans += posS[t][next] - prev
            prev = posS[t][next]

    print(ans)

sol()
### BUGGY CODE ###

N, K = map(int, input().split())
h = [int(x) for x in input().split()]

INF = 1e9
dp = [INF] * N
dp[0] = 0
dp[1] = abs(h[1] - h[0])
for i in range(2, N):
    for j in range (1, K + 1):
        if i - j < 0:
            break;
        dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))

print(dp[N - 1])


### FIXED CODE ###

N, K = map(int, input().split())
h = [int(x) for x in input().split()]

INF = 1e9
dp = [INF] * N
dp[0] = 0
dp[1] = abs(h[1] - h[0])
for i in range(2, N):
    for j in range (1, K + 1):
        if i - j < 0:
            break;
        dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))

print(dp[N - 1])
### BUGGY CODE ###

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

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

from collections import defaultdict
ar = defaultdict(list)
al = defaultdict(list)

for i in range(n):
    al[i+a[i]].append(i)
    ar[i-a[i]].append(i)

mi = 0-max(a)
ma = n+max(a)

ans = 0
for i in range(mi,ma):
    ans += len(ar[i]) * len(al[i])

print(ans)



### FIXED CODE ###

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

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

from collections import defaultdict
ar = defaultdict(list)
al = defaultdict(list)

for i in range(n):
    al[i+a[i]].append(i)
    ar[i-a[i]].append(i)

x = al.keys()

ans = 0
for i in x:
    ans += len(ar[i]) * len(al[i])

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

import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, Q = il()
    S = iss()
    for _ in range(Q):
        l, r = il()
        print(S[l - 1:r].count('AC'))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, Q = il()
    S = iss()
    ret = [0] * N
    for n in range(N - 1):
        if S[n] == 'A' and S[n + 1] == 'C':
            ret[n] += ret[n - 1] + 1
        else:
            ret[n] += ret[n - 1]

    for _ in range(Q):
        l, r = il()
        print(ret[r - 2] - ret[l - 2])


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

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

def flog(n):
	inf=float('inf')
	dp=[inf]*n
	
	dp[0]=0
	
	for i in range(n):
		for j in range(1,min(k+1,n-i)):
			dp[i+j]=min(dp[i+j],dp[i]+abs(H[i+j]-H[i]))
	
	return dp[n-1]
print(flog(n))

### FIXED CODE ###

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

def flog(n):
	inf=float('inf')
	dp=[inf]*n
	
	dp[0]=0
	
	for i in range(n):
		for j in range(1,min(k+1,n-i)):
			dp[i+j]=min(dp[i+j],dp[i]+abs(H[i+j]-H[i]))
	
	return dp[n-1]
print(flog(n))
### BUGGY CODE ###

def C(_mid):
    if _mid <= target_list[K - 1]:
        return True
    else:
        return False


N, K = list(map(int, input().split()))
target_list = []
ab = []
for i in range(N):
    a, b = list(map(int, input().split()))
    ab.append([a, b])

ab.sort(key=lambda x: x[0])
# print(ab)

for i in range(N):
    for j in range(ab[i][1]):
        target_list.append(ab[i][0])

# print(target_list)

lb = 1
ub = 100000
while ub - lb > 1:
    # print(str(lb) + " " + str(ub))
    mid = int((lb + ub) / 2)
    if C(mid):
        lb = mid
    else:
        ub = mid

print(lb)


### FIXED CODE ###

def C(_mid):
    tmp_sum = 0
    if len(ab) <= _mid:
        return False
    for i in range(0, _mid):
        tmp_sum += ab[i][1]
    if tmp_sum < K:
        return True
    else:
        return False


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

ab.sort(key=lambda x: x[0])

lb = 0
ub = 100000
while ub - lb > 1:
    # print(str(lb) + " " + str(ub))
    mid = int((lb + ub) / 2)
    if C(mid):
        lb = mid
    else:
        ub = mid

print(ab[lb][0])
### BUGGY CODE ###

import numpy as np
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    s=STR()
    count=np.zeros(2019,dtype=int)
    ans=0
    count_t=np.zeros(2019,dtype=int)
    for i in range(len(s)):
        count_t[int(s[i])]+=1
        for k in range(2019):
            if count[k]==0:
                continue
            else: 
                t=(k*10+int(s[i]))%2019
                count_t[k]-=count[k]
                count_t[t]+=count[k]
                if t==0:
                    ans+=count[k]
        #print(count[0:20])
        #print(count_t[0:20])
        count=count+count_t
        count_t-=count_t
    print(ans)
                
if __name__ == '__main__':
    do()

### FIXED CODE ###

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    s=STR()
    cnt=[0]*2019
    cnt[0]=1
    temp=0
    keta=1
    ans=0
    for i in s[::-1]:
        temp=(temp+int(i)*keta)%2019
        keta=(keta*10)%2019
        cnt[temp]+=1
    for i in cnt:
        ans+=(i*(i-1))//2
    print(ans)
    
    
if __name__ == '__main__':
    do()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
n, q = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

p = [0] * n
for _ in range(q):
    pp, x = [int(i) for i in input().split()]
    p[pp - 1] += x


def dfs(i=0, r=-1):
    if r!=-1:
        p[i] += p[r]
    for j in e[i]:
        if j == r:
            continue
        dfs(j, i)
dfs()

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


### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)


def input():
    return sys.stdin.readline()


n, q = [int(i) for i in input().split()]
ab = [[] for _ in range(n)]
for _ in range(n - 1):
    i, j = [int(i)-1 for i in input().split()]
    ab[i].append(j)
    ab[j].append(i)
p = [0]*n
for _ in range(q):
    i, j = [int(i) for i in input().split()]
    p[i-1] += j

al = [False]*n
pp = [0]*n


def a(i=0, j=0):
    al[i] = True
    j += p[i]
    pp[i] = str(j)
    for k in ab[i]:
        if not al[k]:
            a(k, j)


a()
print(" ".join(pp))