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

H,W=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
B=[list(map(int,input().split())) for i in range(H)]
import numpy as np
d=np.zeros((H+1,W+1,80*(H+W)),dtype=int)
d[1][1][A[0][0]-B[0][0]]=d[1][1][B[0][0]-A[0][0]]=1
for h in range(H):
    for w in range(W):
        x=A[h][w]-B[h][w]
        d[h+1][w+1]|=(np.roll(d[h][w+1],x))|(np.roll(d[h][w+1],-x))|(np.roll(d[h+1][w],x))|(np.roll(d[h+1][w],-x))
for i in range(99):
    if d[H][W][i] or d[H][W][-i]:
        print(i)
        exit()

### FIXED CODE ###

H,W=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
B=[list(map(int,input().split())) for i in range(H)]
d=[[0]*W for j in range(H)]
m=80*(H+W)
d[0][0]=1<<m
for h in range(H):
    for w in range(W):
        x=abs(A[h][w]-B[h][w])
        if h>0:
            d[h][w]|=d[h-1][w]
        if w>0:
            d[h][w]|=d[h][w-1]
        d[h][w]=d[h][w]<<x|d[h][w]>>x
x,y=1<<m,1<<m
for i in range(99):
    if d[H-1][W-1]&x or d[H-1][W-1]&y:
        print(i)
        exit()
    x<<=1
    y>>=1
### 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, Q = in_nn()
    C = in_nl()
    LR = []

    for q in range(Q):
        l, r = in_nn()
        LR.append((r, l, q))

    t = [-1] * (N + 1)
    sect = []
    for i in range(N):
        x = C[i]
        if t[x] != -1:
            sect.append((i + 1, t[x], -1))
        t[x] = i + 1

    sect += LR
    sect.sort(key=lambda x: (x[0], x[2]))

    bit = [0] * (N + 1)

    def add(i, val):
        while i <= N:
            bit[i] += val
            i += i & -i

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i & -i
        return res

    ans = [0] * Q
    for s in sect:
        r, l, n = s

        if n == -1:
            add(l, 1)
        else:
            t = sum(r) - sum(l - 1)
            ans[n] = r - l + 1 - t

    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

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, Q = in_nn()
    C = in_nl()
    LR = []

    for q in range(Q):
        l, r = in_nn()
        LR.append((r + 0.1, l, q))

    t = [-1] * (N + 1)
    sect = []
    for i in range(N):
        x = C[i]
        if t[x] != -1:
            sect.append((i + 1, t[x], -1))
        t[x] = i + 1

    sect += LR
    sort_index = sorted(list(range(len(sect))), key=lambda i: sect[i][0])

    bit = [0] * (N + 1)

    def add(i, val):
        while i <= N:
            bit[i] += val
            i += i & -i

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i & -i
        return res

    ans = [0] * Q
    for i in sort_index:
        r, l, n = sect[i]
        r = int(r)

        if n == -1:
            add(l, 1)
        else:
            t = sum(r) - sum(l - 1)
            ans[n] = r - l + 1 - t

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


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

MOD = 10 ** 9 + 7


def solve(n, a):
    m = 62
    b = [('0'*m + bin(a[i])[2:])[-1:-m:-1] for i in range(n)]
    cnt_bit = [0] * m
    for i in range(n):
        for j, c in enumerate(b[i]):
            if c == '1':
                cnt_bit[j] += 1
    total = 0
    for i in range(n):
        for j, c in enumerate(b[i]):
            if c == '0':
                total += 2 ** j * cnt_bit[j]
            if c == '1':
                total += 2 ** j * (n - cnt_bit[j])
    return (total//2) % MOD


def bf(n, a):
    total = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            total += (a[i] ^ a[j])
    return total % MOD


if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))

    print(solve(n, a))
    # print(bf(n, a))


### FIXED CODE ###

MOD = 10 ** 9 + 7


def solve(n, a):
    m = 61
    b = [('0'*m + bin(a[i])[2:])[-1:-m:-1] for i in range(n)]
    cnt_bit = [0] * m
    for i in range(n):
        for j, c in enumerate(b[i]):
            if c == '1':
                cnt_bit[j] += 1
    total = 0
    k = 1
    for i in range(m - 1):
        t = 0
        for j in range(n):
            if b[j][i] == '0':
                t += k * cnt_bit[i]
            if b[j][i] == '1':
                t += k * (n - cnt_bit[i])
        t //= 2
        total += t
        k = (k*2 % MOD)
    return total % MOD


def bf(n, a):
    total = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            total += (a[i] ^ a[j])
    return total % MOD


if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))

    print(solve(n, a))
    # print(bf(n, a))
### BUGGY CODE ###

# coding: utf-8
# Your code here!

def Bellman_Ford(g,start):
    n = len(g)    
    dist = [float("inf")]*n
    dist[start] = 0
    a0 = float("inf")
    negative = [False]*n
    for i in range((2*n)):
        updated = False
        for v in range(n):
            for to, cost in g[v]:
                if negative[v]: negative[to] = True
                if dist[to] <= dist[v] + cost: continue
                dist[to] = dist[v] + cost
                updated = True
                if i >= n:
                    negative[to] = True
        if not updated: break
    if negative[-1]: return None, False
    return dist, True
 

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,m,p = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    a,b,c = [int(i) for i in readline().split()]
    g[a-1].append((b-1,-c+p))
#    g[b-1].append((a-1,c))

dist, TF = Bellman_Ford(g, 0)

if TF: print(max(-dist[-1],0))
else: print(-1)




### FIXED CODE ###

# coding: utf-8
# Your code here!

def Bellman_Ford(g,start):
    n = len(g)    
    dist = [float("inf")]*n
    dist[start] = 0
    a0 = float("inf")
    
    for i in range(n<<1):
        updated = False
        for v in range(n):
            for to, cost in g[v]:
                if dist[to] <= dist[v] + cost: continue
                dist[to] = dist[v] + cost
                updated = True
        if not updated: break
        if i <= n: a0 = dist[-1]
    if a0 != dist[-1]: return None, False
    return dist, True


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,m,p = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    a,b,c = [int(i) for i in readline().split()]
    g[a-1].append((b-1,-c+p))
#    g[b-1].append((a-1,c))

dist, TF = Bellman_Ford(g, 0)

if TF: print(max(-dist[-1],0))
else: print(-1)
### BUGGY CODE ###

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


def gcd(a, b):
    if a < b:
        return gcd(b, a)
    else:
        return a if b == 0 else gcd(b, a % b)


def lcm(a, b):
    return a * b // gcd(b, a%b)

L = lcm(N, M)

r = ["*" for i in range(L)]
s = 0
t = 0
f = False

s_step = L // N
t_step = L // M
j = 0
m = 0

for i in range(L):
    if i == 0:
        if S[0] == T[0]:
            r[i] = S[i]
            j += 1
            m += 1
            continue
        else:
            f = True
            break

    if i % s_step == 0 and j < N:
        if r[i] == "*":
            r[i] = S[j]
            j += 1
        else:
            if r[i] != S[j]:
                f = True
                break
            else:
                j += 1

    if i % t_step == 0 and m < M:
        if r[i] == "*":
            r[i] = T[m]
            m += 1
        else:
            if r[i] != T[m]:
                f = True
                break
            else:
                m += 1
if f:
    print(-1)
else:
    print(L)


### FIXED CODE ###

N, M = map(int, input().split())
S = input()
T = input()
# def gcd(a, b):
#     if a < b:
#         return gcd(b, a)
#     else:
#         return a if b == 0 else gcd(b, a % b)

import fractions
def lcm(a, b):
    return a * b // fractions.gcd(b, a % b)


L = lcm(N, M)

f = False

s_step = L // N
t_step = L // M
sL = lcm(s_step, t_step)
s = 0
t = 0

for i in range(0, L, sL):
    if i == 0:
        if S[i] == T[i]:
            continue
        else:
            f = True
            break
    else:
        s = i // s_step
        t = i // t_step
        if s > N - 1:
            break
        if t > M - 1:
            break
        if S[s] == T[t]:
            continue
        else:
            f = True
            break

if f:
    print(-1)
else:
    print(L)
### BUGGY CODE ###

#154_D
n, k = map(int, input().split())
p = [(int(x)+1) / 2 for x in input().split()]

ans = 0
for i in range(n-k+1):
    ans = max(ans, sum(p[i:i+k]))
print(ans)

### FIXED CODE ###

#154_D
n, k = map(int, input().split())
p = list(map(int, input().split()))

tmp = sum(p[0:k])
ans = tmp
for i in range(1,n-k+1):
    tmp += p[i+k-1] - p[i-1]
    ans = max(ans, tmp)

print((ans + k) / 2)
### BUGGY CODE ###

n,h = map(int,input().split())
x = []
for i in range(n):
	x.append(list(map(int,input().split())))
a = []
for i in range(n):
	a.append(x[i][0])
b = []
for i in range(n):
	b.append(x[i][1])

t = 0
c = []#強い投げ刀たち
for i in range(n):
	if b[i]>max(a)-1:
		c.append(b[i])
c.sort()
c.reverse()

if sum(c)>h-1:
	for i in range(n):
		t += 1
		h -= c[i]
		if h<1:
			print(t)
			break
else:
	h -=sum(c)
	q = (h-1)//max(a)+1
	print(q+len(c))

### FIXED CODE ###

n,h = map(int,input().split())
x = []
for i in range(n):
	x.append(list(map(int,input().split())))

t = 0
c = []#強い投げ刀たち
M = max(x[i][0] for i in range(n))

for i in range(n):
	if x[i][1]>M-1:
		c.append(x[i][1])
c.sort()
c.reverse()

if sum(c)>h-1:
	for i in range(len(c)):
		t += 1
		h -= c[i]
		if h<1:
			print(t)
			break
else:
	h -=sum(c)
	q = (h-1)//M+1
	print(q+len(c))
### BUGGY CODE ###

from sys import stdin
input = stdin.readline
L, R = map(int, input().split())
min_mod = 2020
for i in range(L, R):
    for j in range(i + 1, R + 1):
        min_mod = min(min_mod, (i * j) % 2019)
print(min_mod)


### FIXED CODE ###

L, R = map(int, input().split())
min_mod = 10**9
for i in range(L, min(L + 2019, R + 1)):
    for j in range(i + 1, min(L + 2019, R + 1)):
        min_mod = min(min_mod, (i * j) % 2019)
print(min_mod)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()
print(sum([i for i in range(N)]))


### FIXED CODE ###

n = int(input())
print((n*(n-1))//2)
### BUGGY CODE ###

N, M = map(int, input().split())
A = sorted(map(int, input().split()))
L = []
for _ in range(M):
    b, c = map(int, input().split())
    L.append([b, c])

L.sort(key=lambda x: x[1], reverse=True)

# 変更前のカードの枚数
# 変更後のカードの枚数
# をそれぞれ保存しておく
ans = []
remain = []
idx = 0
able_change = 0
check = False
for i in range(M):
    able_change = L[i][0]
    while True:
        if (able_change == 0 or idx > len(A) - 1):
            remain = A[idx:]
            break
        if (L[i][1] > A[idx]):
            ans.append(L[i][1])
            able_change -= 1

        else:
            # print(idx, able_change)
            check = True
            remain = A[idx:]
            break
        idx += 1

    if (check):
        break
    able_change = 0

ans_sum = sum(ans)
remain_sum = sum(remain)

print(ans_sum + remain_sum)


### FIXED CODE ###

N, M = map(int, input().split())
A = sorted(map(int, input().split()))
L = []
for _ in range(M):
    b, c = map(int, input().split())
    L.append([b, c])
L.sort(key=lambda x: x[1], reverse=True)
# 変更前のカードの枚数
# 変更後のカードの枚数
# をそれぞれ保存しておく

idx = 0
for i in range(N):
    if (idx > len(L) - 1):
        break
    if (A[i] < L[idx][1]):
        A[i] = L[idx][1]
        L[idx][0] -= 1
        if (L[idx][0] != 0):
            continue
        else:
            idx += 1
    else:
        break
print(sum(A))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = 1
for i in range(n):
  b *= a[i]
if b > 10**18:
  b = -1
print(b)

### FIXED CODE ###

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

import array
n, k = map(int, input().split())
tel = array.array('i', list(map(int, input().split())))
log = array.array('i', [1])
end = True
while(end):
    log.append(tel[log[-1] - 1])
    for i in range(len(log) - 1):
        if(log[i] == log[-1]):
            star = i
            mod = len(log) - star - 1
            end = False
if(k < len(log)):
    print(log[k])
else:
    print(log[(k - star) % mod + star])


### FIXED CODE ###

n, k = map(int, input().split())
tel = list(map(int, input().split()))
log = [1]
record = [0] * n
while(True):
    log.append(tel[log[-1] - 1])
    if(record[log[-1] - 1] == 1):
        break
    record[log[-1] - 1] += 1
for i in range(len(log) - 1):
    if(log[i] == log[-1]):
        star = i
        mod = len(log) - star - 1
        break
if(k < len(log)):
    print(log[k])
else:
    print(log[(k - star) % mod + star])
### BUGGY CODE ###

N, M = map(int, input().split())
L = []
P = []
#Y = []
var = []
for i in range(M):
    p, y = map(int, input().split())
    if p not in P:
        var.append(p)
    P.append(p)
    #Y.append(y)
    L.append([i, p, y])

#L = list(zip(range(M), P, Y))     

Order = [None]*M

for v in var:
    l = filter(lambda x:x[1] == v, L)
    l_ = sorted(l, key = lambda x:x[2])
    
    for n in l_:
        Order[n[0]] = (n[1], l_.index(n)+1)
        
for n in Order:
    print('{0:0>6d}{1:0>6d}'.format(n[0], n[1]))

### FIXED CODE ###

N, M = map(int, input().split())
L = []
P = [0]*(N+1)
for i in range(M):
    p, y = map(int, input().split())
    L.append([i, p, y, 0])

L = sorted(L, key = lambda x:x[2])

for l in L:
    P[l[1]] += 1
    l[3] = P[l[1]]    
        
for l in sorted(L, key = lambda x:x[0]):
    print('{0:0>6d}{1:0>6d}'.format(l[1], l[3]))
### BUGGY CODE ###

from sys import stdin
import numpy as np


def dp_solve(dp, lim, n):
    for i in range(n):
        w, v = map(int, input().split())
        for j in range(lim+1):
            if w <= j:
                dp[i+1][j] = max(dp[i][j], dp[i][j-w]+v)
            else:
                dp[i+1][j] = dp[i][j]

    return dp[n][lim]


if __name__ == "__main__":
    n, lim = map(int, stdin.readline().split())
    items = []

    dp = np.zeros((n+1, lim+1), dtype='uint64')
    print(dp_solve(dp, lim, n))


### FIXED CODE ###

from sys import stdin
import numpy as np


def dp_solve(dp, lim, n):
    for i in range(n):
        w, v = map(int, input().split())
        dp[i+1][:w] = dp[i][:w]
        dp[i+1][w:] = np.maximum(dp[i][w:], dp[i][:-w]+v)
    return np.max(dp[n])


if __name__ == "__main__":
    n, lim = map(int, stdin.readline().split())
    items = []

    dp = np.zeros((n+1, lim+1), dtype='uint64')
    print(dp_solve(dp, lim, n))
### BUGGY CODE ###

import math
n=int(input())
s = [''.join(sorted(input())) for i in range(n)]
a=set(s)
c=0

for i in a:
    if s.count(i)>1:
        c+=(s.count(i)*(s.count(i)-1))//2
print(c)

### FIXED CODE ###

n=int(input())
s = [''.join(sorted(input())) for i in range(n)]
s.sort()
s.append("a")
b=1
c=0
for i in range(n):
    if s[i]!=s[i+1]:
        c+=(b*(b-1))//2
        b=1
    else:
        b+=1
print(c)
### BUGGY CODE ###

N=int(input())
S=list(map(int,input().split()))
S.sort(reverse=True)
p = [S.pop(0)]
c = S
f = False

for i in range(N):
    np = []
    nc = []
    for p_ in p:
        for k in range(len(c)):
            if c[k] < p_:
                np.append(c.pop(k))
                f = True
                break
        if f == False:
            print("No")
            exit(0)
        f = False
    p += np
    p.sort(reverse=True)

print("Yes")

### FIXED CODE ###

N=int(input())
S=list(map(int,input().split()))
S.sort()
p = [S.pop(-1)]
r = S

for i in range(N):
    nr = []
    for p_ in p[::-1]:
        while r:
            r_ = r.pop()
            if r_ < p_:
                p.append(r_)
                break
            nr.append(r_)
    p.sort()
    r+=nr[::-1]

print("Yes" if len(r)==0 else "No")
### BUGGY CODE ###

def gcd(a,b):
    if (b==0):
        return a
    else:
        return gcd(b, a%b)


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

LCM = 1
for i in a:
    LCM = LCM // gcd(LCM,i) * i

ans = 0
for i in a:
    ans += (LCM // i)

ans %= mod
print(ans)


### FIXED CODE ###

import fractions 
mod = 1000000007;
n = int(input())
a = list(map(int, input().split()))

LCM = 1
for i in a:
    LCM = LCM // fractions.gcd(LCM,i) * i

ans = 0
for i in a:
    ans += (LCM // i)

ans %= mod
print(ans)
### BUGGY CODE ###


from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from functools import reduce

from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import statistics
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm(a, b):
  return a*b//gcd(a, b)

def main():
  S = input()
  Q = int(input())
  TFC = list(list(input().split()) for _ in range(Q))
  #q = deque(S)
  for i in range(Q):
    if TFC[i][0] == '1':
      S = S[::-1]
    else:
      if TFC[i][1] == '1':
        S = TFC[i][2] + S
      else:
        S = S + TFC[i][2]
  print(S)
  
if __name__ == '__main__':
  main()

### FIXED CODE ###


from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from functools import reduce

from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import statistics
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm(a, b):
  return a*b//gcd(a, b)

def main():
  S = input()
  Q = int(input())
  TFC = list(list(input().split()) for _ in range(Q))
  rev = 0
  q = deque(S)
  for i in range(Q):
    if TFC[i][0] == '1':
      rev ^= 1
    else:
      if TFC[i][1] == '1':
        if rev == 0:
          q.appendleft(TFC[i][2])
        else:
          q.append(TFC[i][2])
      else:
        if rev == 0:
          q.append(TFC[i][2])
        else:
          q.appendleft(TFC[i][2])
  ans = ''.join(q)
  print(ans if rev==0 else ans[::-1])
  
if __name__ == '__main__':
  main()
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

n = int(input())

sum = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            sum += gcd(i,j,k)

print(sum)

### FIXED CODE ###

import math
from functools import reduce
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
n = int(input())
 
sum = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            sum += gcd(i,j,k)
 
print(sum)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)
from itertools import count
from functools import lru_cache
from collections import defaultdict
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#


def main():
    N, M = mis()
    S = input()

    @lru_cache(maxsize=None)
    def rec(n):
        if n < 0 or S[n] == '1':
            return None, INF
        elif n == 0:
            return None, 0
        min_i = None
        min_v = INF
        for i in range(max(n-M, 0), n):
            _, v = rec(i)
            if min_v > v:
                min_v = v
                min_i = i
        return min_i, min_v

    flag, _ = rec(N)
    if flag is None:
        print(-1)
    else:
        ans = []
        pos = N
        while pos != 0:
            prev_pos, _ = rec(pos)
            ans.append(pos - prev_pos)
            pos = prev_pos
        ans.reverse()
        print(*ans, sep=' ')



main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
from itertools import count
from functools import lru_cache
from collections import defaultdict
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#


def main():
    N, M = mis()
    S = input()

    ans = []
    r = N
    l = max(r - M, 0)
    while r > 0:
        for i in range(l, r):
            if S[i] == '0':
                ans.append(r - i)
                r = i
                l = max(r - M, 0)
                break
        else:
            print(-1)
            return
    ans.reverse()
    print(*ans, sep=' ')


main()
### BUGGY CODE ###



anslist = []


def solve():

    S = input()

    ans = 0
    for i in range(len(S)-3):
        for j in range(i, len(S)-3):
            if int(S[i:j+4]) % 2019 == 0:
                ans += 1
                i = j+4

    print(ans)


if __name__ == "__main__":
    solve()


### FIXED CODE ###



def solve():

    s = input()
    mod = 2019
    remains = [0]*mod

    ans = 0
    now = 0
    remains[0] = 1
    for i, val in enumerate(s[::-1]):
        now += int(val) * pow(10, i, mod)
        now %= mod
        ans += remains[now]
        remains[now] += 1

    print(ans)


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

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

ans = 1

for a in A:
  ans *= a
  
if ans > pow(10, 18):
  print(-1)
  import sys
  sys.exit()

print(ans)
  

### FIXED CODE ###

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

ans = 1

import sys

if 0 in A:
  print(0)
  sys.exit()
  
for a in A:
  ans *= a
  if ans > pow(10, 18):
      print(-1)
      sys.exit()

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

n, k = map(int, input().split())
AB = []
for i in range(n):
    a, b = map(int, input().split())
    AB.append((a, b))
AB.sort()
cnt = 0
X = []
for i in range(n):
    a, b = AB[i]
    X += [a]*b
    cnt += b
    if cnt > k:
        break
X.sort()
print(X[k-1])


### FIXED CODE ###

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

ab = [[0, 0] for _ in range(n)]

for i in range(n):
  a, b = map(int, input().split())
  ab[i][0] = a
  ab[i][1] = b

ab.sort()
s = 0
i = 0
while s< k:
  s += ab[i][1]
  ans = ab[i][0]
  i += 1
print(ans)