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

"""
https://atcoder.jp/contests/dp/tasks/dp_a
"""
from copy import deepcopy
N = int(input())
arr = [int(i) for i in input().split(" ")]

def getMinSteps():
    dp_2 = [0, ]
    dp_1 = [abs(arr[1] - arr[0]), ]
    
    total_cost = 0
    i = 2
    
    while i < N:
        diff1 = abs(arr[i] - arr[i-1])
        diff2 = abs(arr[i] - arr[i-2])
        temp = deepcopy(dp_2)
        dp_2 = deepcopy(dp_1)

        for j in range(len(dp_1)):
            dp_1[j] += diff1

        for j in range(len(temp)):
            dp_1.append(temp[j] + diff2)

        i += 1
    return min(dp_1)

        
print(getMinSteps())

### FIXED CODE ###

"""
https://atcoder.jp/contests/dp/tasks/dp_a
"""
from copy import deepcopy
N = int(input())
arr = [int(i) for i in input().split(" ")]

def getMinSteps():
    dp_2 = [0, ]
    dp_1 = [abs(arr[1] - arr[0]), ]
    
    total_cost = 0
    i = 2
    
    while i < N:
        diff1 = abs(arr[i] - arr[i-1])
        diff2 = abs(arr[i] - arr[i-2])
        temp = deepcopy(dp_2)
        dp_2 = deepcopy(dp_1)

        for j in range(len(dp_1)):
            dp_1[j] += diff1

        for j in range(len(temp)):
            dp_1.append(temp[j] + diff2)
            
        dp_1 = sorted(dp_1)[0:2]
        
        i += 1
    return min(dp_1)

        
print(getMinSteps())
### BUGGY CODE ###

INT_MAX = (1<<31) - 1
_N,query_num = map(int, input().split())
queries = [list(map(int, input().split())) for i in range(query_num)]
N = 1<<17

arr_size = 2*N - 1
A = [INT_MAX]*(arr_size)
lazy_A = [None]*(arr_size)

def tree_propagate(k):
    if(lazy_A[k] is None):
        return
    if(k < N // 2):
        A[k*2+1] = A[k*2+2] = lazy_A[k*2+1] = lazy_A[k*2+2] = lazy_A[k]
        lazy_A[k] = None
        return
    if(k < N-1):
        A[k*2+1] = A[k*2+2] = lazy_A[k]
        lazy_A[k] = None

def update(s,t,x,k,l,r):
    if (r <= s or t <= l):
        return
    if (s <= l and r <= t):
        A[k] = x
        if(k < N-1):
            lazy_A[k] = x
        return

    tree_propagate(k)
    center = (l+r)//2
    update(s, t, x, k*2 + 1, l, center)
    update(s, t, x, k*2 + 2, center, r)
    A[k] = min(A[k*2+1], A[k*2+2])

def find(s,t,k,l,r):
    if (r <= s or t <= l):
        return INT_MAX
    if(s <= l and r <= t):
        return A[k]

    tree_propagate(k)
    center = (l+r)//2
    v_left = find(s, t, k*2 + 1, l, center)
    v_right = find(s, t, k*2 + 2, center, r)
    return min(v_left,v_right)

answers = []
for query in queries:
    if(query[0]==0):
        update(query[1],query[2]+1,query[3],0,0,N)
    else:
        answers.append(find(query[1],query[2]+1,0,0,N))

print("\n".join([str(ans) for ans in answers]))



### FIXED CODE ###

import sys
input = sys.stdin.readline
INT_MAX = (1<<31) - 1
_N,num = map(int, input().split())
Q = [list(map(int, input().split())) for i in range(num)]
N = 1<<17
N1 = N - 1
N2 = N1 // 2
ars = 2*N - 1
A = [INT_MAX]*(ars)
L = [-1]*(ars)

def propagate(k):

    if(L[k] == -1):
        return
    left = k*2+1
    right = k*2+2
    if(k < N2):
        A[left] = A[right] = L[left] = L[right] = L[k]
        L[k] = -1
        return
    if(k < N1):
        A[left] = A[right] = L[k]
        L[k] = -1

def update(s,t,x,k,l,r):

    if (r <= s or t <= l):
        return
    if (s <= l and r <= t):
        A[k] = x
        if(k < N1):
            L[k] = x
        return

    propagate(k)
    mid = (l+r)//2
    left = k*2 + 1
    right = k*2 + 2
    update(s, t, x, left, l, mid)
    update(s, t, x, right, mid, r)

    A[k] = min(A[left], A[right])

def find(s,t,k,l,r):

    if (r <= s or t <= l):
        return INT_MAX

    if(s <= l and r <= t):
        return A[k]

    propagate(k)
    mid = (l+r)//2
    left = k*2 + 1
    right = k*2 + 2
    v_left = find(s, t, left, l, mid)
    v_right = find(s, t, right, mid, r)
    return min(v_left,v_right)

res = []
for q in Q:
    # update
    if(q[0]==0):
        update(q[1],q[2]+1,q[3],0,0,N)
    # find
    else:
        res.append(find(q[1],q[2]+1,0,0,N))

print("\n".join([str(r) for r in res]))
### BUGGY CODE ###

x = input()
while 'ST' in x:
    # print(x)
    x = x.replace('ST', '')

print(len(x))

### FIXED CODE ###

x = input()
n = len(x)
ans = []
for i in range(n):
    if x[i] == 'S':
        ans.append(x[i])
    else:
        if len(ans) > 0:
            if ans[-1] == 'S':
                ans.pop()
            else:
                ans.append(x[i])
        else:
            ans.append(x[i])
    # print(ans)

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

pos_black_mapping = {}
pos_num_mapping = {}
H, W, N = map(int, raw_input().split())
for i in range(N):
    a, b = map(int, raw_input().split())
    a, b = a-1, b-1
    pos_black_mapping[a, b] = 1
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            na, nb = a+dx, b+dy
            if (0 <= na < H-2) and (0 <= nb < W-2):
                pos_num_mapping[na, nb] = 1

ans = [0 for _ in range(10)]
for a, b in pos_num_mapping.keys():
    cnt = 0
    for dy in range(3):
        for dx in range(3):
            na, nb = a+dx, b+dy
            if (na, nb) in pos_black_mapping:
                cnt += 1
    ans[cnt] += 1
ans[0] = (W-2)*(H-2) - sum(ans[1:])
for v in ans:
    print v

### FIXED CODE ###

pos_black_mapping = {}
pos_num_mapping = {}
H, W, N = map(int, raw_input().split())
for i in range(N):
    a, b = map(int, raw_input().split())
    a, b = a-1, b-1
    if (a, b) in pos_black_mapping:
        continue
    pos_black_mapping[a, b] = 1
    for da in range(-1, 2):
        for db in range(-1, 2):
            na, nb = a+da, b+db
            if (0 < na < H-1) and (0 < nb < W-1):
                if not (na, nb) in pos_num_mapping:
                    pos_num_mapping[na, nb] = 0
                pos_num_mapping[na, nb] += 1

ans = [0 for _ in range(10)]
for a, b in pos_num_mapping.keys():
    ans[pos_num_mapping[a, b]] += 1
ans[0] = (W-2)*(H-2) - sum(ans[1:])
for v in ans:
    print v
### BUGGY CODE ###

n = int(input())
s = list(input())

ans = 0

for x in range(n):
  for y in range(n):
    for z in range(n):
      if not x < y < z:
        # print("SKIP: ", x, y, z)
        continue

      if "".join( sorted([s[x], s[y], s[z]]) ) != "BGR":
        # print("SKIP: ", x, y, z)
        continue

      if y-x == z-y:
        # print("SKIP: ", x, y, z)
        continue

      ans += 1
      # print(x, y, z)
      # print(s[x], s[y], s[z])

print(ans)


### FIXED CODE ###

n = int(input())
s = list(input())

ans = s.count("R") * s.count("G") * s.count("B")

for i in range(n):
  for j in range(n):
    if not i < j:
      continue
    k = j + (j-i)
    if k < n and "".join(sorted([s[i], s[j], s[k]])) == "BGR":
      ans -= 1

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

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

mod = 10**9+7
n = int(input())
edges = [[] for i in range(n)]
for i in range(n-1):
    x,y = map(int, input().split())
    x,y = x-1, y-1
    edges[x].append(y)
    edges[y].append(x)

def rec(cur, prev=None):
    white = 1
    black = 1
    for to in edges[cur]:
        if to == prev:
            continue
        w,b = rec(to, cur)
        white *= (w+b)
        white %= mod
        black *= w
        black %= mod
    return white, black

w, b = rec(0)
print((w+b)%mod)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

def main():
    input = sys.stdin.readline

    mod = 10**9+7
    n = int(input())
    edges = [[] for i in range(n)]
    for i in range(n-1):
        x,y = map(int, input().split())
        x,y = x-1, y-1
        edges[x].append(y)
        edges[y].append(x)

    def rec(cur, prev=None):
        white = 1
        black = 1
        for to in edges[cur]:
            if to == prev:
                continue
            w,b = rec(to, cur)
            white *= (w+b)
            white %= mod
            black *= w
            black %= mod
        return white, black

    w, b = rec(0)
    print((w+b)%mod)

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

from collections import deque


H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

checked = [[False for _ in range(W)] for _ in range(H)]

que = deque()
flag = False
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            que.append((i, j))
            checked[i][j] = True
            flag = True

if flag is False:
    print(0)
    exit()

n_que = deque()
step = 0
while len(que):

    h, w = que[0][0], que[0][1]
    que.popleft()
    for d in range(4):
        nh, nw = h + dy[d], w + dx[d]
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if checked[nh][nw] is True:
            continue
        n_que.append((nh, nw))
        checked[nh][nw] = True

    if len(que) == 0:
        if len(n_que) == 0:
            print(step)
            exit()
        que = n_que
        n_que = deque()
        step += 1


### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

checked = [[False for _ in range(W)] for _ in range(H)]

que = deque()
flag = False
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            que.append((i, j))
            checked[i][j] = True
        else:
            flag = True

if flag is False:
    print('0')
    exit()

n_que = deque()
step = 0
while len(que):

    h, w = que[0][0], que[0][1]
    que.popleft()
    for d in range(4):
        nh, nw = h + dy[d], w + dx[d]
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if checked[nh][nw] is True:
            continue
        n_que.append((nh, nw))
        checked[nh][nw] = True

    if len(que) == 0:
        if len(n_que) == 0:
            print(step)
            exit()
        que = n_que
        n_que = deque()
        step += 1
### BUGGY CODE ###

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

for _ in range(M):
    b, c = map(int, input().split())
    for _ in range(b):
        A.append(c)

A.sort()
print(sum(A[-1:-N-1:-1]))


### FIXED CODE ###

import sys
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
origin = sum(A)
heapq.heapify(A)

BC = [list(map(int, input().split())) for _ in range(M)]
BC = sorted(BC, reverse=True, key=lambda x: x[1])

count = 0

for i in range(M):
    b = BC[i][0]
    c = BC[i][1]
    for _ in range(b):
        smallest = heapq.heappop(A)
        tmp = c - smallest
        if tmp <= 0:
            heapq.heappush(A, smallest)
            break
        else:
            heapq.heappush(A, c)
            origin += tmp
            count += 1
            if count >= N:
                print(origin)
                sys.exit()

print(origin)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    a = [ord(c) - 97 for c in S()]
    l = len(a)
    r = []
    t = [0] * l
    s = set()
    u = [[] for _ in range(26)]
    k = 1
    sl = 0
    for i in range(l-1,-1,-1):
        c = a[i]
        u[c].append(i)
        t[i] = k
        if c not in s:
            if sl == 25:
                k += 1
                s = set()
                sl = 0
            else:
                sl += 1
                s.add(c)
    t.append(1)
    for i in range(26):
        u[i].reverse()

    def bs(i,c):
        t = u[c]
        if not t or t[-1] <= i:
            return -1
        ma = len(t) - 1
        mi = 0
        mm = (ma+mi) // 2
        while ma > mi:
            mm = (ma+mi) // 2
            if t[mm] > i:
                ma = mm
            else:
                mi = mm + 1
        return t[mm]

    j = -1
    while j < l:
        for c in range(26):
            bi = bs(j,c)
            if bi < 0:
                r.append(c)
                j = l
                break
            if t[bi] < k:
                r.append(c)
                k = t[bi]
                j = bi
                break

    return ''.join([chr(c+97) for c in r])

print(main())





### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    a = S()
    l = len(a)
    t = {}
    for c in string.ascii_lowercase:
        t[c] = l
    b = [(1,0,0) for _ in range(l)]
    b.append((1,'a',l))
    b.append((0,'',l+1))

    for c,i in reversed(list(zip(a,range(l)))):
        t[c] = i
        b[i] = min([(b[t[d]+1][0] + 1,d,t[d]+1) for d in string.ascii_lowercase])

    r = ''
    i = 0
    while i < l:
        r += b[i][1]
        i = b[i][2]
    return r

print(main())
### BUGGY CODE ###

'''
参考
https://qiita.com/c-yan/items/f7c99c8f8ec418a58c42

棒の全長をL、切断箇所をCとすると、かかるコストは|2C-L|となる
（左端から切断箇所までの長さを2倍し、元の棒の全長を引いたものの絶対値）
∵
・CがL/2よりも左にある場合（=棒の左端からCまでの長さのほうが短い）
⇒Cよりも左側に2C-L足すか、右側を2C-L減らす
・CがL/2よりも右にある場合（=棒の左端からCまでの長さのほうが長い）
⇒Cよりも左側を2C-L減らすか、右側に2C-L足す

与えられたリストAのうち、どの地点をCとするかは
リストAの先頭の要素からN-1個の要素をそれぞれ調べ、
先頭要素から現在の要素までの合計（累積和）を格納するリストを別途作成、
そのリストに対して|2C-L|が最小となるケースを調べる
'''
N = int(input())
A = list(map(int, input().split()))
L = sum(A)
tmp = []

for i in range(N):
    tmp.append(sum(A[:i+1]))

cost = max(A)
for c in tmp:
    if abs(c*2-L) <= cost:
        cost = abs(c*2-L)

print(cost)


### FIXED CODE ###

'''
参考
https://qiita.com/c-yan/items/f7c99c8f8ec418a58c42

棒の全長をL、切断箇所をCとすると、かかるコストは|2C-L|となる
（左端から切断箇所までの長さを2倍し、元の棒の全長を引いたものの絶対値）
∵
・CがL/2よりも左にある場合（=棒の左端からCまでの長さのほうが短い）
⇒Cよりも左側に2C-L足すか、右側を2C-L減らす
・CがL/2よりも右にある場合（=棒の左端からCまでの長さのほうが長い）
⇒Cよりも左側を2C-L減らすか、右側に2C-L足す

与えられたリストAのうち、どの地点をCとするかは
リストAの先頭の要素からN-1個の要素をそれぞれ調べ、
先頭要素から現在の要素までの合計（累積和）を格納するリストを別途作成、
そのリストに対して|2C-L|が最小となるケースを調べる
'''
N = int(input())
A = list(map(int, input().split()))
L = sum(A)
#tmp = []
tmp = A[:-1]

for i in range(1, N-1):
#    tmp.append(sum(A[:i+1]))       # 実行時間超過してしまうためコメントアウト
    tmp[i] += tmp[i-1]

cost = min(abs(c*2-L) for c in tmp)
print(cost)
### BUGGY CODE ###

from collections import deque
import sys

def main():
    s = sys.stdin.readline().strip()
    qn = int(sys.stdin.readline().strip())
    qs = [input().split() for _ in range(qn)]

    c = cn = 0
    s = deque(s)

    for _ in qs:
        if qs[c][0] == '1':
            cn+=1
        else:
            if cn%2 == 1:
                s.reverse()
            cn = 0

        if qs[c][0] == '2':
            if qs[c][1] == '1':
                s.appendleft(qs[c][2])
            else:
                s.append(qs[c][2])
        c+=1
    if cn%2 == 1:
        s.reverse()
    print('%s' % ''.join(s))

if __name__ == "__main__":

    main()

### FIXED CODE ###

from collections import deque
import sys

def main():
    s = sys.stdin.readline().strip()
    qn = int(sys.stdin.readline().strip())
    qs = [input().split() for _ in range(qn)]

    s = deque(s)
    r = 1
    for q in qs:
        if len(q) == 1:
            r = r * -1

        else:
            if q[1] == '1':
                if r == 1:
                    s.appendleft(q[2])
                else:
                    s.append(q[2])
            else:
                if r == 1:
                    s.append(q[2])
                else:
                    s.appendleft(q[2])

    if r == 1:
        print(''.join(s))
    else:
        s.reverse()
        print(''.join(s))

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

X,Y,Z,K= map(int,input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))


A.sort()
A.reverse()
B.sort()
B.reverse()
C.sort()
C.reverse()

ab_list = []

for i in range(X):
    for j in range(Y):
        ab_list.append(A[i]+B[j])

ab_list.sort()
ab_list.reverse()
abc_list = []

count = 0
count2 = 0

for i in range(min(X*Y,K)):
    for j in range(Z):
        abc_list.append(ab_list[i]+C[j])

abc_list.sort()
abc_list.reverse()

for i in range(K):
    print(abc_list[i])

### FIXED CODE ###

X,Y,Z,K= map(int,input().split())
A = sorted(list(map(int,input().split())), reverse=True)
B = sorted(list(map(int,input().split())), reverse=True)
C = sorted(list(map(int,input().split())), reverse=True)



ab_list = []

for i in range(X):
    for j in range(Y):
        ab_list.append(A[i]+B[j])

ab_list2 = sorted(ab_list,reverse = True)[:min(X*Y,K)]
abc_list = []

count = 0
count2 = 0

for i in range(min(X*Y,K)):
    for j in range(Z):
        abc_list.append(ab_list2[i]+C[j])


abc_list2 = sorted(abc_list,reverse = True)[:K]

for i in range(K):
    print(abc_list2[i])
### BUGGY CODE ###

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def lm(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def gm(a, b):
    return a * b // lm(a, b)


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()
    A.sort()

    l = 1
    res = 0
    for a in A:
        if l % a == 0:
            res = (res + l // a) % mod
        else:
            l2 = gm(a, l)
            res = (res * l2 // l) % mod
            res = (res + l2 // a) % mod
            l = l2
    print(res)


if __name__ == "__main__":
    main()



### FIXED CODE ###

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def g(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()

    B = 1
    for a in A:
        B *= a // g(B, a)
    
    print(sum(B // a for a in A) % mod)


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

H,W = map(int,input().split())
s = [input() for _ in range(H)]
ans = [[-1 for w in range(W)] for h in range(H)]
ans0 = ans[:]
for h in range(H):
    sh = s[h]
    st = -1
    gl = -1
    cnt = 0
    for w in range(W):
        if sh[w] == '.':
            cnt += 1
            if st == -1:
                st,gl = w,w
            gl +=1
            if w == W-1:
                for i in range(st,w+1):
                    ans[h][i] += cnt
        else:
            for i in range(st,gl):
                ans[h][i] += cnt
            cnt = 0
            st,gl = -1,-1
#print(*ans,sep='\n')
#ans1 = ans[:]
#ans = [[0 for w in range(W)] for h in range(H)]
for w in range(W):
    st = -1
    gl = -1
    cnt = 0
    for h in range(H):
        if s[h][w] == '.':
            cnt += 1
            if st == -1:
                st,gl = h,h
            gl +=1
            if h == H-1:
                for i in range(st,h+1):
                    ans[i][w] += cnt
        else:
            for i in range(st,gl):
                ans[i][w] += cnt
            cnt = 0
            st,gl = -1,-1
#print(*ans,sep='\n')
mx = 0
for x in ans:
    mx = max(max(x),mx)
print(mx)

### FIXED CODE ###

H,W = map(int,input().split())
s = [input() for _ in range(H)]
ans = [[-1 for w in range(W)] for h in range(H)]
ans0 = ans[:]
for h in range(H):
    sh = s[h]
    st = -1
    gl = -1
    cnt = 0
    for w in range(W):
        if sh[w] == '.':
            cnt += 1
            if st == -1:
                st,gl = w,w
            gl +=1
            if w == W-1:
                for i in range(st,w+1):
                    ans[h][i] += cnt
        else:
            for i in range(st,gl):
                ans[h][i] += cnt
            cnt = 0
            st,gl = -1,-1
#print(*ans,sep='\n')
#ans1 = ans[:]
#ans = [[0 for w in range(W)] for h in range(H)]
for w in range(W):
    st = -1
    gl = -1
    cnt = 0
    for h in range(H):
        if s[h][w] == '.':
            cnt += 1
            if st == -1:
                st,gl = h,h
            gl +=1
            if h == H-1:
                for i in range(st,h+1):
                    ans[i][w] += cnt
        else:
            for i in range(st,gl):
                ans[i][w] += cnt
            cnt = 0
            st,gl = -1,-1
#print(*ans,sep='\n')
mx = 0
for x in ans:
    mx = max(max(x),mx)
print(mx)
### BUGGY CODE ###

def is_753(s) :
	if (s.find("0") > -1) :
		return False
	elif (s.find("1") > -1) :
		return False
	elif (s.find("2") > -1) :
		return False
	elif (s.find("4") > -1) :
		return False
	elif (s.find("6") > -1) :
		return False
	elif (s.find("8") > -1) :
		return False
	elif (s.find("9") > -1) :
		return False
	
	if (s.find("7") > -1 and s.find("5") > -1 and s.find("3") > -1) :
		return True
	
	return False

N = int(input())
count = 0
# index = 0

for i in range(N+1) :
	s = str(i)
	if (is_753(s)) :
		count += 1

print(count)

### FIXED CODE ###

import math
def is_753(s) :
	
	if ("0" in s) :
		return False
	elif ("1" in s) :
		return False
	elif ("2" in s) :
		return False
	elif ("4" in s) :
		return False
	elif ("6" in s) :
		return False
	elif ("8" in s) :
		return False
	elif ("9" in s) :
		return False
	
	if ("7" in s and "5" in s and "3" in s) :
		return True
	
	return False

def hoge(s) :
	for i in range(len(s)) :
		if (s[i] != "3" and s[i] != "5" and s[i] != "7") :
			return int(math.pow(10, len(s) - (i+1)))

	return 0

def main() :
	N = int(input())
	count = 0
	index = 356
	
	if (N < 357) :
		print("0")
		return

	while index <= N :
		s = str(index)
		a = hoge(s)
		if (a != 0) :
			index += a
			continue		
		
		if (is_753(s)) :
			count += 1
		
		index += 1
	
	print(count)


main()
### BUGGY CODE ###

class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        while i > 1:
            y = self.tree[i ^ 1]
            if y <= x:
                break
            i >>= 1
            self.tree[i] = x

    def get_min(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.INF

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result = min(result, self.tree[r - 1])
            if l & 1:
                result = min(result, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return result


def solve(n, m, s):
    INF = 10 ** 18
    sgt = SegTreeMin(n + 1, (INF,))
    sgt.update(0, (0, 0))
    for i in range(1, n + 1):
        if s[i] == '1':
            continue
        r = i
        l = max(0, i - m)
        prev = sgt.get_min(l, r)
        if prev[0] == INF:
            return (-1,)
        dice = i - prev[-1]
        curr = (prev[0] + 1,) + prev[1:-1] + (dice, i)
        sgt.update(i, curr)
    return sgt.get_min(n, n + 1)[1:-1]


n, m = map(int, input().split())
s = input()
print(*solve(n, m, s))


### FIXED CODE ###

from heapq import heappop, heappush


def solve(n, m, s):
    curr = n
    l = max(0, n - m)
    r = n
    ans = []
    while r > 0:
        for i, c in enumerate(s[l:r], start=l):
            if c == '0':
                dice = curr - i
                ans.append(dice)
                curr = i
                l = max(0, i - m)
                r = i
                break
        else:
            return (-1,)

    return reversed(ans)


n, m = map(int, input().split())
s = input()
print(*solve(n, m, s))