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

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

from collections import defaultdict

# union find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(N)
REL = defaultdict(set)

for _ in range(M):
    a, b = map(int, input().split())
    # REL[a].add(b)
    # REL[b].add(a)
    a -= 1
    b -= 1
    if a > b:
        c = b
        b = a
        a = c

    uf.union(a, b)

mm = 0
for root in uf.roots():
    mm = max(mm, len(uf.members(root)))

ic = 0
for m in range(N):
    if uf.members(m) == 0:
        ic += 1

# for r, g in uf.all_group_members():
#     if len(g) == 1:
#         ic += 1
#     else:
#         mm = max(mm, len(g))

if mm < ic:
    mm += 1

print(mm)

### FIXED CODE ###

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

from collections import defaultdict

# union find
class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n
 
    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

uf = UnionFind(N)

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a > b:
        c = b
        b = a
        a = c

    uf.union(a, b)

# member = defaultdict(int)
r = min(uf.table)
if r != -1:
    mm = abs(r)
    # ic = 0
    # for n in uf.table:
    #     if n == -1:
    #         ic += 1

    # if ic%mm != 0:
    #     mm += 1
else:
    mm = 1

print(mm)
### BUGGY CODE ###

S = input()
ans = {0:1}
memo = [0]
for ind, s in enumerate(S[::-1]):
    memo.append(int(S[-ind-1:]) % 2019)
    if(memo[-1] in ans):
        ans[memo[-1]] += 1
    else:
        ans[memo[-1]] = 1

res = 0
for key in ans.keys():
    res += ans[key]*(ans[key]-1)//2
print(res)

### FIXED CODE ###

S = input()
ans = {0:1}
memo = [0]
last = 1
for ind, s in enumerate(S[::-1]):
    memo.append((int(s) * last + memo[-1]) % 2019)
    last *= 10
    last %= 2019
    if(memo[-1] in ans):
        ans[memo[-1]] += 1
    else:
        ans[memo[-1]] = 1

res = 0
for key in ans.keys():
    res += ans[key]*(ans[key]-1)//2
print(res)
### BUGGY CODE ###

import math
n= int(input())

l = list(map(int,input().split()))
ans = 1
if 0 in l:
  print(0)
else:
  for i in range(n):
    ans *= l[i]
  print(ans if ans <= 10**18 else -1)


### FIXED CODE ###

import math
n= int(input())

l = list(map(int,input().split()))
l.sort(reverse = True)

ans = 1
if 0 in l:
  print(0)
else:
  for i in range(n):
    ans *= l[i]
#    print(ans)
    if ans > 10**18:
      break
  print(ans if ans <= 10**18 else -1)
### BUGGY CODE ###


N,W = map(int,input().split())
lis = [[[0,0]]]

for i in range(N):

    w,v = map(int,input().split())

    new = []

    for j in lis[i]:

        if j[0] + w <= W:

            new.append([j[0] + w , j[1] + v])
            
        new.append([j[0] ,j[1]])

    lis.append(new)

ans = 0

for i in lis[-1]:

    ans = max( ans , i[1] )

print (ans)


### FIXED CODE ###


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

lis = [ [0] * (W+1) ]


for i in range(N):

    w,v = map(int,input().split())

    new = [0] * (W+1)

    for j in range(W+1):

        new[j] = max(new[j],lis[-1][j])

        if j+w <= W:

            new[j+w] = max(new[j+w],lis[-1][j]+v)

    lis.append(new)

print (lis[-1][W])
### BUGGY CODE ###

import sys

N = int(sys.stdin.readline())
L = tuple([int(x) for x in sys.stdin.readline().split()])

answer = 0

for i in range(len(L)-2):
    for j in range(i+1, len(L)-1):
        for k in range(j+1,len(L)):
            if L[i] + L[j] > L[k] and L[j] + L[k] > L[i] and L[k] + L[i] > L[j]:
                answer += 1
print(answer)


### FIXED CODE ###

import sys
import bisect

N = int(sys.stdin.readline())
L = [int(x) for x in sys.stdin.readline().split()]
L.sort()

answer = 0

for i in range(len(L)-2):
    for j in range(i+1, len(L)-1):
        answer += bisect.bisect_left(L, L[i]+L[j])-j-1

print(answer)
### BUGGY CODE ###

def sieve(n):
    a = [1 for i in range(n + 1)]
    for i in range(2, n + 1):
        if a[i]:
            for j in range(2 * i, n + 1, i):
                a[j] = 0
    return a[2:]

while True:
    try:
        n = int(raw_input())
        print len(filter(lambda x: x, sieve(n)))
    except (EOFError):
        break

### FIXED CODE ###

def sieve(n):
    a = [1] * (n + 1)
    for i in range(2, n):
        if i * i > n: break
        if a[i]:
            for j in range(2 * i, n + 1, i):
                a[j] = 0
    return a[2:]

while True:
    try:
        n = int(raw_input())
        print len(filter(lambda x: x, sieve(n)))
    except (EOFError):
        break
### BUGGY CODE ###

import numpy as np
from itertools import product
H, W, K = map(int, input().split())
G = np.array([list(map(int, list(input()))) for _ in range(H)])

ans = float("inf")

for pattern in product([0, 1], repeat = H - 1):
    div = [0] + [i for i, p in enumerate(pattern, 1) if p == 1] + [20]
    rows = []
    for i in range(len(div) - 1):
        rows.append(np.sum(G[div[i]: div[i + 1]], axis=0)) # 列方向

    tmp_ans = 0
    cnt = [0] * len(rows)
    w = 0
    flag = False
    rows = [r.tolist() for r in rows]

    while w < W:
        for r in range(len(rows)):
            cnt[r] += rows[r][w]
        if np.any(np.array(cnt) > K):
            if w == 0:
                flag = True
                break
            cnt = [0] * len(rows)
            tmp_ans += 1
            w -= 1
        w += 1
    
    if not flag:
        tmp_ans += pattern.count(1)
        ans = min(ans, tmp_ans)

print(ans)

### FIXED CODE ###

from itertools import product
H, W, K = map(int, input().split())
G = [list(map(int, list(input()))) for _ in range(H)]

ans = float("inf")

for pattern in product([0, 1], repeat = H - 1):
    div = [0] + [i for i, p in enumerate(pattern, 1) if p == 1] + [H]
    rows = []
    for i in range(len(div) - 1):
        row = []
        for j in range(W):
            tmp = 0
            for k in range(div[i], div[i + 1]):
                tmp += G[k][j]
            row.append(tmp)
        rows.append(row)
        
    flag = True
    for row in rows:
        if [r for r in row if r > K]:
            flag = False
            break
    if not flag:
        continue

    tmp_ans = 0
    cnt = [0] * len(rows)
    w = 0

    while w < W:
        for r in range(len(rows)):
            cnt[r] += rows[r][w]
        if [c for c in cnt if c > K]:
            cnt = [0] * len(rows)
            tmp_ans += 1
            w -= 1
        w += 1
    
    tmp_ans += pattern.count(1)
    ans = min(ans, tmp_ans)

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

# -*- coding: utf-8 -*-
import math

N = int(input())
f = [0] * N
for i in range(1, N+1):
  count = 0
  for x in range(1, i):
    for y in range(x, i):
      z = i-x-y
      if z < y:
        break
      n = x**2 + y**2 + z**2 + x*y + y*z + z*x
      if z > math.sqrt(n + 1):
        break
      if n <= N:
        if x == y and x == z:
          f[n-1] += 1
        elif x == y or y == z:
          f[n-1] += 3
        elif x != y and x != z and y != z:
          f[n-1] += 6
for i in f:
  print(i)



### FIXED CODE ###

# -*- coding: utf-8 -*-
import math

N = int(input())
f = [0] * N
for i in range(1, N+1):
  count = 0
  for x in range(1, i):
    if x**2 > N:
      break
    for y in range(x, i):
      if y**2 > N:
        break
      z = i-x-y
      if z < y:
        break
      n = x**2 + y**2 + z**2 + x*y + y*z + z*x
      if z > math.sqrt(n + 1):
        break
      if n <= N:
        if x == y and x == z:
          f[n-1] += 1
        elif x == y or y == z:
          f[n-1] += 3
        elif x != y and x != z and y != z:
          f[n-1] += 6
for i in f:
  print(i)
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
a=0
c=0
m=max(A)
while(m):
    o=sum(map(lambda x:x&1,A))
    a+=(n-o)*o*2**c
    A=list(map(lambda x:x>>1,A))
    c+=1
    a%=10**9+7
    m//=2
print(a)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
a=0
c=0
m=max(A)
while(m):
    o=sum(map(lambda x:x&1,A))
    a+=(n-o)*o*2**c
    A=list(map(lambda x:x>>1,A))
    c+=1
    a%=10**9+7
    m//=2
print(a)
### BUGGY CODE ###

n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    g[a-1].append([b-1,c])
    g[b-1].append([a-1,c])
q,k=map(int,input().split())
qu=[[k-1,0]]
v=[0]*n
d=[0]*n
while len(qu)>0:
    s=qu[0]
    qu=qu[1:]
    v[s[0]]=1
    for j in g[s[0]]:
        if not v[j[0]]:
            v[j[0]]=1
            d[j[0]]=s[1]+j[1]
            qu+=[[j[0],d[j[0]]]]
for i in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])


### FIXED CODE ###

from collections import deque
n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    g[a-1].append([b-1,c])
    g[b-1].append([a-1,c])
q,k=map(int,input().split())
qu=deque([[k-1,0]])
v=[0]*n
d=[0]*n
while len(qu)>0:
    s=qu.popleft()
    v[s[0]]=1
    for j in g[s[0]]:
        if not v[j[0]]:
            v[j[0]]=1
            d[j[0]]=s[1]+j[1]
            qu+=[[j[0],d[j[0]]]]
for i in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])
### BUGGY CODE ###

from collections import deque
n = int(input())
Ps = list(map(lambda x: int(x)-1, input().split()))
cost = [min(i, n-1-i, j, n-1-j) for i in range(n) for j in range(n)]
DIRC = [(-1, 0), (0, 1), (1, 0), (0, -1)]
exist = [1]*(n**2)


def to_idx(p):
    return divmod(p, n)


def to_v(i, j):
    return i*n+j


def bfs(init_v):
    next_v = deque([init_v])
    exist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        i, j = to_idx(v)
        for di, dj in DIRC:
            x, y = i+di, j+dj
            v2 = to_v(x, y)
            if x < 0 or y < 0 or n <= x or n <= y:
                continue
            c = cost[v]+exist[v]
            if cost[v2] <= c:
                continue
            cost[v2] = c
            next_v.append(v2)


ans = 0
for p in Ps:
    ans += cost[p]
    bfs(p)
print(ans)

### FIXED CODE ###

from collections import deque
n = int(input())
Ps = list(map(lambda x: int(x)-1, input().split()))
cost = [min(i, n-1-i, j, n-1-j) for i in range(n) for j in range(n)]
exist = [1]*(n**2)


def to_idx(p):
    return divmod(p, n)


def to_v(i, j):
    return i*n+j


def bfs(init_v):
    next_v = deque([init_v])
    exist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        i, j = to_idx(v)
        if 0 < i:
            v2 = v-n
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if i < n-1:
            v2 = v+n
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if 0 < j:
            v2 = v-1
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if j < n-1:
            v2 = v+1
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

ans = 0
for p in Ps:
    ans += cost[p]
    bfs(p)
print(ans)
### BUGGY CODE ###

import sys
import copy
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
A = MAP()

B = copy.deepcopy(A)
B.sort()

med = N//2

for i,a in enumerate(A):
	if B.index(a)>=med:
		print(B[med-1])
	else:
		print(B[med])

### FIXED CODE ###

import sys
import copy
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
A = MAP()

# print(A)
med = N//2

B = copy.deepcopy(A)
B.sort()
l_m = B[med-1]
h_m = B[med]

for a in A:
	if a > l_m:
		print(l_m)
	else:
		print(h_m)
### BUGGY CODE ###

k = int(input())
x = 7
ans = 1
if k%2 == 0 or k%5 ==0:
  ans = -1
else:
  while x%k != 0:
    ans +=1
    x = x*10+7

print(ans)



### FIXED CODE ###

k = int(input())
x = 7
ans = 1
if k%2 == 0 or k%5 ==0:
  print(-1)
  exit()
elif 7%k == 0:
  ans = 1

else:
  for i in range (1,k):
    x = (x*10+7)%k

    if x%k == 0:
      ans = i+1
      break

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

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

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

inf = 1e10

dp_list = [inf for _ in range(N)]
dp_list[0] = 0

# import heapq

sys.setrecursionlimit(1000000)
def dp_memo(i):
  if dp_list[i] != inf:
    return dp_list[i]

  result = dp_list[i]

  for j in range(1, K+1):
    if i-j < 0:
      break
    result = min(result, dp_memo(i-j) + abs(hs[i] - hs[i-j]))

  dp_list[i] = result
  return result


def dp_recur(N):
  for i in range(1, N):
    for j in range(1,K+1):
      if i-j < 0:
        break
      dp_list[i] = min(dp_list[i], dp_list[i-j] + abs(hs[i] - hs[i-j]))
  return dp_list[N-1]

# print(dp_recur(N))
print(dp_memo(N-1))


### FIXED CODE ###

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

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

inf = 1e10

dp_list = [inf for _ in range(N)]
dp_list[0] = 0

# import heapq

sys.setrecursionlimit(1000000)
def dp_memo(p):
  if dp_list[p] != -1:
    return dp_list[p]

  costs = []
  # heapq.heapify(costs)
  if K <= p:
    for i in range(1,K+1):
        # heapq.heappush(costs, dp_memo(p-i) + abs(hs[p] - hs[p-i]))
        costs.append(dp_memo(p-i) + abs(hs[p] - hs[p-i]))
  else:
    for i in range(1,p+1):
        # heapq.heappush(costs, dp_memo(p-i) + abs(hs[p] - hs[p-i]))
        costs.append(dp_memo(p-i) + abs(hs[p] - hs[p-i]))
  result = min(costs)
  # result = heapq.heappop(costs)
  dp_list[p] = result
  return result


def dp_recur(N):
  for i in range(1, N):
    for j in range(1,K+1):
      if i-j < 0:
        break
      dp_list[i] = min(dp_list[i], dp_list[i-j] + abs(hs[i] - hs[i-j]))
  return dp_list[N-1]

print(dp_recur(N))
# print(dp_memo(N-1))
### BUGGY CODE ###

n, m = map(int, input().split())
broken = [int(input()) for _ in range(m)]

mod = 10 ** 9 + 7

dp = [0] * (n + 1)
dp[0] = 1
if 1 not in broken:
    dp[1] = 1

for i in range(2, n + 1):
    if i -1 not in broken:
        dp[i] = dp[i] + dp[i - 1]
    if i - 2 not in broken:
        dp[i] = dp[i] + dp[i - 2]
    
    dp[i] %= 1000000007
    
print(dp[n])

### FIXED CODE ###

n, m = map(int, input().split())
issafe = [True] * (n +1)
for _ in range(m):
    a = int(input())
    issafe[a] = False

dp = [0] * (n + 1)
dp[0] = 1
if issafe[1]:
    dp[1] = 1

for i in range(2, n + 1):
    if  issafe[i - 1]:
        dp[i] = dp[i] + dp[i - 1]
    if issafe[i -  2]:
        dp[i] = dp[i - 2] + dp[i] 
    
    dp[i] %= 1000000007
    
print(dp[n])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]
n,k = map(int,input().split())
lis = list(map(int,input().split()))
lis.sort()
ans = 0
for i in range(n):
    if i >= k-1:
        ans += lis[i] * cmb(i,k-1)
    if n-i-1 >= k-1:
        ans -= lis[i] * cmb(n-i-1,k-1)
    ans %= 10 ** 9+7
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル


n,k = map(int,input().split())
lis = list(map(int,input().split()))
lis.sort()
ans = 0
for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
for i in range(n):
    if i >= k-1:
        ans += lis[i] * cmb(i,k-1,mod)
    if n-i-1 >= k-1:
        ans -= lis[i] * cmb(n-i-1,k-1,mod)
    ans %= 10 ** 9+7
print(ans)
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
a=[i for i in range(n-1) if s[i:i+2]=="AC"]
for i in range(q):
  l,r=map(int,input().split())
  print(len([x for x in a if l-1<=x<r-1]))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
a=[0 for _ in range(n)]
for i in range(n-1):
  a[i+1]=a[i]+(1 if s[i:i+2]=="AC" else 0)
for i in range(q):
  l,r=map(int,input().split())
  print(a[r-1]-a[l-1])
### BUGGY CODE ###

n, m = map(int, input().split())
s = []
e = []
for i in range(m):
    x, y = map(int, input().split())
    if x == 1:
        s.append(y)
    elif y == n:
        e.append(x)
flag = False
for i in s:
    for j in e:
        if i == j:
            flag = True
if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

n, m = map(int, input().split())
s = [0 for i in range(n)]
e = [0 for i in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    if x == 1:
        s[y] = 1
    elif y == n:
        e[x] = 1
flag = False
for i in range(n):
    if s[i] == 1 and e[i] == 1:
        flag = True
        break
if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

N,K = map(int,input().split())
A = [int(i) for i in input().split()]
loop = min(41,K)
for _ in range(loop):
    B = [0]*N
    for n in range(N):
        l = max(0,n-A[n])
        r = min(N-1,n+A[n])
        B[l]+=1
        if r+1<N:
            B[r+1] -= 1
    for n in range(1,N):
        B[n] += B[n-1]
    A = [b for b in B]
print(*A)

### FIXED CODE ###

N,K = map(int,input().split())
A = [int(i) for i in input().split()]
loop = min(41,K)
for _ in range(loop):
    B = [0]*N
    for n in range(N):
        l = max(0,n-A[n])
        r = min(N-1,n+A[n])
        B[l]+=1
        if r+1<N:
            B[r+1] -= 1
    for n in range(1,N):
        B[n] += B[n-1]
    A = [b for b in B]
print(*A)
### BUGGY CODE ###

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():
    N = in_n()
    X = int(in_s(), 2)

    #t = '1101101010' * 10**3
    #X = int(t, 2)
    #N = 10**4

    ans = [0] * N
    for i in range(N):
        a = X ^ (1 << N - i - 1)
        a = bin(a)[2:]
        count = 0
        while int(a, 2):
            a = bin(int(a, 2) % a.count('1'))[2:]
            count += 1
        ans[i] = count

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    N = int(readline())
    X = readline().rstrip().decode('utf-8')
    nx = int(X, 2)

    ans = [0] * N

    oc = X.count('1')

    if oc - 1 != 0:
        mx = nx % (oc - 1)
        f = True
    else:
        f = False

    px = nx % (oc + 1)

    for i in range(N):

        if X[i] == '0':
            a = (px + pow(2, N - i - 1, oc + 1)) % (oc + 1)
        elif f:
            a = (mx - pow(2, N - i - 1, oc - 1)) % (oc - 1)
        else:
            ans[i] = 0
            continue

        count = 1
        while a:
            a = a % bin(a).count('1')
            count += 1

        ans[i] = count

    print('\n'.join(map(str, ans)))


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

w = []
v = []
n, W = map(int, input().split())
#dp = [[0 for i in range(n)] for j in range(W)]
dp = [[None for i in range(W+1)] for j in range(n+1)]

for i in range(n):
    v1, v2 = map(int, input().split())
#    v2, v1 = map(int, input().split())
    w.append(v1)
    v.append(v2)

# i: Index (Tracing all items)
# j: Remaining weight
# Return the sum of value
def knap(i, j):
    # print("\n# i: " + str(i))
    # print("# j: " + str(j))
    if dp[i][j] is not None:
        return dp[i][j]

    res = 0

    if i == n:
#        dp[i][j] = 0
        res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        # if dp[i][j] is None:
        #     dp[i][j] = dp[i-1][j] + v[i]
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    dp[i][j] = res
    return dp[i][j]
#    return res

print(knap(0, W))


### FIXED CODE ###

n, W = map(int, input().split())
w = [0]*(n+1)
v = [0]*(n+1)

#dp = [[None for i in range(W+1)] for j in range(n+1)]
dp = [[0 for i in range(W+1)] for j in range(n+1)]

for i in range(n):
    w[i], v[i] = map(int, input().split())

def knap(i, j):
    if dp[i][j] is not None:
        return dp[i][j]

    res = 0

    if i == n:
       	res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    dp[i][j] = res
    return dp[i][j]

for i in reversed(range(n)):
    for j in range(W+1):
#        res = 0
        # if i == n-1:
        #     res = 0
        if j < w[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i])

#print(knap(0, W))
print(dp[0][W])
### BUGGY CODE ###

s = str(input())
l = len(list(s))

if l<=3:
    print(0)
else:
    n=0
    for i in range(0,l-3):
        for j in range(i+3,l):
            if int(s[i:j+1])%2019==0:
                n += 1
            else:
                n += 0
    print(n)

### FIXED CODE ###

s = input()[::-1]

dp = [0]*2019
dp[0]=1
total = 0
a = 1

for i in list(s):
  total += int(i)*a
  total %= 2019
  dp[total] += 1
  a *= 10
  a %= 2019
count=0
  
for i in range(2019):
    count += dp[i]*(dp[i]-1)//2
 
print(count)