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

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

count = {}

for a in A:
    count[a] = count.get(a, 0) + 1

sorted_ = sorted(count.items(), key=lambda x: x[1])

total = 0
while K < len(sorted_):
    k, v = sorted_[0]
    sorted_ = sorted_[1:]
    total += v

if len(sorted_) == 0:
    total = 0

print(total)

### FIXED CODE ###

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

count = {}

for a in A:
    count[a] = count.get(a, 0) + 1

tmp = []
for k, v in count.items():
    tmp.append(v)

tmp = sorted(tmp)

total = 0
for i in range(len(tmp) - K):
    total += tmp[i]

print(total)
### BUGGY CODE ###

from operator import mul
from functools import reduce
n = int(input())
a = list(map(int, input().split()))
ans = reduce(mul, a)
print(ans if ans <= 10**18 else -1)


### FIXED CODE ###

n = input()
a = list(map(int, input().split()))
if 0 in a:
  print(0)
  exit()
ans = 1
for x in a:
  ans *= x
  if ans > 10**18:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

def gcd(a,b):
  if b == 0:
    return a
  return gcd(b, a % b)
 
def lcm(a,b):
  return a * b // gcd(a,b)
 
n = int(input())
av = list(map(int, input().split(' ')))
alcm = 1
for i in av:
  alcm = lcm(alcm, i)
 
tot = 0
for i in range(n):
  tot += alcm // av[i]
 
print(tot % 1000000007)

### FIXED CODE ###

def gcd(a,b):
  if b == 0:
    return a
  return gcd(b, a % b)
 
def lcm(a,b):
  return a * b // gcd(a,b)
 
n = int(input())
av = list(map(int, input().split(' ')))
alcm = 1
for i in av:
  alcm = lcm(alcm, i)
 
tot = 0
for i in range(n):
  tot += alcm // av[i]
 
print(tot % 1000000007)
### BUGGY CODE ###

import sys
import copy

def partition(A, p, r):
    x = A[r - 1][1]
    i = p - 1
    for j in range(p, r - 1):
        if A[j][1] <= x:
            i += 1
            tmp = A[i]
            A[i] = A[j]
            A[j] = tmp

    tmp = A[i+1]
    A[i+1] = A[r-1]
    A[r-1] = tmp
    return i+1

def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q)
        quicksort(A, q + 1, r)
    return A

def babble_sort(A, n):
    for j in range(n):
        for i in range(n-1):
            if A[i+1][1] < A[i][1]:
                tmp = A[i+1]
                A[i+1] = A[i]
                A[i] = tmp
    return A

def stable(A, B):
    for i in range(0, len(A)):
        if A[i][0] != B[i][0]:
            return False
    return True


n = int(sys.stdin.readline())

A = [[x[0], int(x[1])] for x in [y.split() for y in sys.stdin.read().split("\n")[:-1]]]

B = babble_sort(copy.deepcopy(A), n)
C = quicksort(copy.deepcopy(A), 0, n)

if stable(C, B):
    print('Stable')
else:
    print("Not stable")

for i in C:
    print(*i)

### FIXED CODE ###

import sys
import copy

def partition(A, p, r):
    x = A[r - 1][1]
    i = p - 1
    for j in range(p, r - 1):
        if A[j][1] <= x:
            i += 1
            tmp = A[i]
            A[i] = A[j]
            A[j] = tmp

    tmp = A[i+1]
    A[i+1] = A[r-1]
    A[r-1] = tmp
    return i+1

def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q)
        quicksort(A, q + 1, r)
    return A

def babble_sort(A, n):
    for j in range(n):
        for i in range(n-1):
            if A[i+1][1] < A[i][1]:
                tmp = A[i+1]
                A[i+1] = A[i]
                A[i] = tmp
    return A

def stable(A, B):
    for i in range(0, len(A)):
        if A[i][0] != B[i][0]:
            return False
    return True


n = int(sys.stdin.readline())

A = [[x[0], int(x[1])] for x in [y.split() for y in sys.stdin.read().split("\n")[:-1]]]

B = sorted(copy.deepcopy(A), key=lambda x: x[1])
C = quicksort(copy.deepcopy(A), 0, n)

if stable(C, B):
    print('Stable')
else:
    print("Not stable")

for i in C:
    print(*i)
### BUGGY CODE ###

def check(pos, c):
    if pos < 0 or pos >= len(S):
        return False
    return S[pos] == c
N = int(input())
S = input()
R_pos = [i for i, c in enumerate(S) if c == 'R']
G_pos = [i for i, c in enumerate(S) if c == 'G']
B_pos = [i for i, c in enumerate(S) if c == 'B']
B_l = len(B_pos)
res = 0
for i in R_pos:
    for j in G_pos:
        res += B_l
        dis = abs(i - j)
        res -= check(min(i, j) - dis, 'B')
        res -= check(max(i, j) + dis, 'B')
        if dis % 2 == 0:
            res -= check(max(i, j) - dis // 2, 'B')
print(res)

### FIXED CODE ###

def check(pos, c):
  if pos < 0 or pos >= len(S):
    return False
  return S[pos] == c
N = int(input())
S = input()
R_pos = [i for i, c in enumerate(S) if c == 'R']
G_pos = [i for i, c in enumerate(S) if c == 'G']
B_pos = [i for i, c in enumerate(S) if c == 'B']
B_l = len(B_pos)
res = 0
for i in R_pos:
  for j in G_pos:
    res += B_l
    dis = abs(i - j)
    res -= check(min(i, j) - dis, 'B')
    res -= check(max(i, j) + dis, 'B')
    if dis % 2 == 0:
      res -= check(max(i, j) - dis // 2, 'B')
print(res)
### BUGGY CODE ###

from math import sin,cos,pi
x=[0]*100;y=[0]*100
h=1000
while 1:
    n=int(input())
    if n==0:break
    a=0
    for i in range(n):x[i],y[i]=map(float,input().split(','))
    for i in range(n):
        for j in range(h):
            cx=x[i]+cos(2*pi*j/h)
            cy=y[i]+sin(2*pi*j/h)
            c=0
            for k in range(n):
                if (cx-x[k])*(cx-x[k])+(cy-y[k])*(cy-y[k])<1.0+1e-7:c+=1
            a=max(a,c)
    print(a)

### FIXED CODE ###

import itertools
x=[0.]*100;y=[0.]*100
while 1:
    n=int(input())
    if n==0:break
    a=0
    for i in range(n):x[i],y[i]=map(float,input().split(','))
    for i,j in itertools.product(range(100),range(100)):
            c=0
            for k in range(n):
                if pow(x[k]-(i/10),2)+pow(y[k]-(j/10),2)<=1.01:c+=1
            if c>a:a=c
    print(a)
### BUGGY CODE ###

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

L,R=map(int, input().split())
s=[i for i in range(L,R+1)]
t=[]
for i in range(M-1):
    L,R=map(int, input().split())
    t=[j for j in range(L,R+1)]
    s = set(s) & set(t)
    #print(s)

print(len(s))

### FIXED CODE ###

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

L=[]
R=[]

for i in range(M):
    a,b=map(int, input().split())
    L.append(a)
    R.append(b)

ans=min(R)-max(L)+1
print("0" if ans<0 else ans)
### BUGGY CODE ###

N = int(input())
l = list(map(int, input().split()))
ans = 1
for e in l:
    ans *= e

if ans > 10 ** 18:
    print('-1')
else:
    print(str(ans))

### FIXED CODE ###

import sys
N = int(input())
l = list(map(int, input().split()))
ans = 1

if 0 in l:
    print('0')
    sys.exit()
    
for e in l:
    ans *= e
    if ans > 10 ** 18:
        print('-1')
        sys.exit()

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

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

ans = max(C)
for i in range(N):
    s = i
    l = []
    while True:
        s = P[s]-1
        l.append(C[s])
        if s == i:
            break

    if sum(l) > 0:
        c = K//len(l)*sum(l)
        n = K%len(l)
        ans = max(ans,c)
        s = i
        x = 0
        for j in range(n):
            s = P[s]-1
            x += C[s]
            ans = max(ans,c+x)

    n = min(N,K)
    s = i
    x = 0
    for j in range(n):
        s = P[s]-1
        x += C[s]
        ans = max(ans,x)
            
print(ans)


### FIXED CODE ###

N,K = map(int,input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int,input().split()))

ans = max(C)
for i in range(N):
    s = i
    l = [C[i]]
    while True:
        s = P[s]
        if s == i:
            break
        l.append(C[s])
        

    if sum(l) > 0:
        if K>=len(l):
            c = (K//len(l)-1)*sum(l)
            n = K%len(l)+len(l)
        else:
            c = 0
            n = K
        ans = max(ans,c)
        s = i
        for j in range(n):
            c += C[s]
            s = P[s]
            ans = max(ans,c)

    n = min(N,K)
    s = i
    c = 0
    for j in range(n):
        c += C[s]
        s = P[s]
        ans = max(ans,c)
            
print(ans)
### BUGGY CODE ###

n = int(input())
strs = ["".join(sorted(list(input()))) for _ in range(n)]
cnt = 0
for i in range(n):
  for j in range(i+1, n):
    if strs[i]==strs[j]:
      cnt+=1
print(cnt)

### FIXED CODE ###

n = int(input())
strs = ["".join(sorted(list(input()))) for _ in range(n)]
ans = {}
cnt = 0
for i in range(n):
  if strs[i] in ans:
    cnt += ans[strs[i]]
    ans[strs[i]] +=  1
  else:
    ans[strs[i]] = 1

print(cnt)
### BUGGY CODE ###

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

ans = -float('inf')

for i in range(1, N+1):
    score = [0]
    alr = set()
    now = i
    while not now in alr:
        alr.add(now)
        now = P[now-1]
        score.append(score[-1] + C[now-1])
    if len(score)-1 >= K:
        for j in range(K):
            ans = max(ans, score[j+1])
    else:
        base = 0
        if score[-1] > 0:
            base = score[-1]*(K//(len(score)-1))
            L = K % (len(score)-1)
            for j in range(len(score)-1):
                ans = max(ans, (base-score[-1])+score[j+1])
            for j in range(L):
                ans = max(ans, base+score[j+1])
        else:
            for j in range(len(score)-1):
                ans = max(ans, base+score[j+1])

print(ans)
        


### FIXED CODE ###

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

ans = -float('inf')

for i in range(1, N+1):
    score = [0]
    alr = set()
    now = i
    while not now in alr:
        alr.add(now)
        now = P[now-1]
        score.append(score[-1] + C[now-1])
    if len(score)-1 >= K:
        for j in range(K):
            ans = max(ans, score[j+1])
    else:
        base = 0
        if score[-1] > 0:
            base = score[-1]*(K//(len(score)-1))
            L = K % (len(score)-1)
            for j in range(len(score)-1):
                ans = max(ans, (base-score[-1])+score[j+1])
            for j in range(L):
                ans = max(ans, base+score[j+1])
        else:
            for j in range(len(score)-1):
                ans = max(ans, base+score[j+1])

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

n = int(input())
S = [input() for _ in range(n)]
cnt = 0
for i in range(len(S)):
    for j in range(i+1, len(S)):
        if ''.join(sorted(S[i])) == ''.join(sorted(S[j])):
            cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
S = [list(input()) for _ in range(N)]
cnt = 0
dic = {}
for s in S:
    s.sort()
    s_ = "".join(s)
    if s_ in dic.keys():
        cnt += dic[s_]
        dic[s_] += 1
    else:
        dic[s_] = 1
print(cnt)
### BUGGY CODE ###

n, m = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
C = []
if m <= n:
	print(0)
	exit()
for i in range(1, m):
	C.append(abs(X[i] - X[i-1]))
for i in range(n-1):
	t = max(C)
	C[C.index(t)] = 0
print(sum(C))

### FIXED CODE ###

n, m = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
C = []
if m <= n:
	print(0)
	exit()
for i in range(1, m):
	C.append(abs(X[i] - X[i-1]))
C.sort()
for i in range(n-1):
	C[m-2-i] = 0
print(sum(C))
### BUGGY CODE ###

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

ans = 0

for i in range(n-1):
  for j in range(i+1, n):
    ans += a[i]*a[j]
  
print(ans % (1000000000+7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
zenbu = sum(a)
ans = 0

for i in range(n):
  ans += a[i]*(zenbu-a[i])
 
print(ans // 2 % 1000000007)
### BUGGY CODE ###

N, Q = map(int, input().split())
A = [int(a) for a in input().split()][::-1]
for _ in range(Q):
    x = int(input())
    l, r = 0, (N+1)//2
    while r - l > 1:
        m = (l+r) // 2
        if A[m] + A[2*m] >= 2 * x:
            l = m
        else:
            r = m
    l += 1
    print(sum(A[:l] + A[2*l::2]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
def calc(x):
    l, r = 0, (N+1)//2
    while r - l > 1:
        m = (l+r) // 2
        if A[m] + A[2*m] >= 2 * x:
            l = m
        else:
            r = m
    return l
    
N, Q = map(int, input().split())
A = [int(a) for a in input().split()][::-1]
B = [A[0]] + [0] * (N-1)
for i in range(1, N):
    B[i] = B[i-1] + A[i]
C = [A[0]] + [0] * (N-1)
for i in range(2, N, 2):
    C[i] = C[i-2] + A[i]
C[-1] += C[-2]
for _ in range(Q):
    x = int(input())
    c = calc(x)
    print(B[c] + (C[-1] - C[2*c] if c*2<=N else 0))
### BUGGY CODE ###

n = int(input())
N = 1
for i in range(1, n + 1):
    N *= i
ans = 0
for j in range(1, N + 1):
    if N % j == 0:
        ans += 1
print(ans % (10 ** 9 + 7))

### FIXED CODE ###

n = int(input())
mod = 10 ** 9 + 7
prime = [1] * 1001  # 素因数の個数の初期値を1に設定する
for num in range(2, n + 1):
    while num % 2 == 0:  # 偶数のとき
        prime[2] += 1  # 2で割れる回数を記録
        num //= 2  # 2で割っておく
    odd = 3
    while odd ** 2 <= num:  # 奇数の素因数を考える
        while num % odd == 0:  # ある奇数で割れた時
            prime[odd] += 1  # 奇数の素因数の個数を記録する
            num //= odd  # 奇数で割っておく
        odd += 2 # 次の奇数にする
    if num != 1:  # numが1でない時はそれ自身で割れるので1追加する
        prime[num] += 1
ans = 1  # ansの初期値を定義する
for i in range(1001):
    ans *= prime[i]  # 約数の個数を計算する
print(ans % mod)  # modで割った余りを出力する
### BUGGY CODE ###

n = int(input()) #n行の入力をリストに入れる
l = []
for i in range(n):
    l.append(input()) 

from collections import Counter

def get_counter(s):
    return Counter(s.upper().replace(' ', ''))

def verify_anagrams(first_word, second_word):
    return get_counter(first_word) == get_counter(second_word)

count =0 
for i in range(n):
    for j in range(i+1,n):
        if verify_anagrams(l[i],l[j])==True:
            count += 1

print(count)
#print(verify_anagrams(l[0],l[2]))

### FIXED CODE ###

from collections import Counter

n = int(input()) #n行の入力をリストに入れる
S = [''.join(sorted(input())) for i in range(n)] #inputの文字列をソートできる
counter = Counter(S) #Sの中の文字列を集計し、dict型で返せる

ans =0 
for i in counter.values():
    ans += i*(i-1)//2

print(ans)

""""
l = []
for i in range(n):
    l.append(input()) 

def get_counter(s):
    return Counter(s.upper().replace(' ', ''))

def verify_anagrams(first_word, second_word):
    return get_counter(first_word) == get_counter(second_word)

count =0 
for i in range(n):
    for j in range(i+1,n):
        if verify_anagrams(l[i],l[j])==True:
            count += 1


print(count)

#print(verify_anagrams(l[0],l[2]))
"""
### BUGGY CODE ###

def resolve():
    s = input()
    k = int(input())
    c = 0
    for i in s:
        if i == "1":
            c += 1
        else:
            c += int(i)**((5*10**16)-1)
        if k <= c:
            print(i)
            break
resolve()

### FIXED CODE ###

def resolve():
    s = input()
    k = int(input())
    c = 0
    for i in range(k):
        if s[i] != "1":
            print(s[i])
            break
        if i == k-1:
            print(1)
resolve()
### BUGGY CODE ###

import numpy as np

S = input()
MOD = 2019
dp = np.zeros(MOD, dtype=np.int64)
dp[0] = 1

def shift(s):
    global dp
    dp = np.roll(dp, s)

ans = 0
for i, s in enumerate(S[::-1]):
    shift(int(s) * pow(10, i, MOD) % MOD)
    ans += dp[0]
    dp[0] += 1
print(ans)


### FIXED CODE ###

from collections import defaultdict
S = input()
MOD = 2019

cnt = [0] * MOD
cnt[0] = 1

now = 0
ans = 0
for d, n in enumerate(map(int, S[::-1])):
    now = (n * pow(10, d, MOD) + now) % MOD
    ans += cnt[now]
    cnt[now] += 1

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

#!/usr/bin/env python3
import sys

def min(val: int, new: int):
    if new < val:
        return new
    else:
        return val

def solve(N: int, K: int, h: "List[int]"):
    dp = [sys.maxsize] * N
    dp[0] = 0

    for i in range(1,N):
        for j in range(1,K+1):
            if i-j >= 0:
                dp[i] = min(dp[i],dp[i-j] + abs(h[i]-h[i-j]))

    print(dp[N-1])

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    h = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, h)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def min(val: int, new: int):
    if new < val:
        return new
    else:
        return val

def solve(N: int, K: int, h: "List[int]"):
    dp = [sys.maxsize] * N
    dp[0] = 0

    for i in range(1,N):
        for j in range(1,K+1):
            if i-j >= 0:
                dp[i] = min(dp[i],dp[i-j] + abs(h[i]-h[i-j]))

    print(dp[N-1])

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    h = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, h)

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

# -*- coding: utf-8 -*-
from fractions import Fraction

N = int(input())

dict_F = {}
count_0 = 0

def insert(A,B,s): # A>=0, B>0, s=0or1
  if Fraction(A,B) not in dict_F.keys():
    dict_F[Fraction(A,B)] = [0,0]
  dict_F[Fraction(A,B)][s] += 1

def power2(A):
  result = 1
  for _ in range(A):
    result = (2*result)%mod
  return result

for _ in range(N):
  A,B = map(int, input().split())
  if A==0 and B==0:
    count_0 += 1
  elif A>=0 and B>0:
    insert(A,B,0)
  elif A>0 and B<=0:
    insert(-B,A,1)
  elif A<=0 and B<0:
    insert(-A,-B,0)
  elif A<0 and B>=0:
    insert(B,-A,1)

mod = 1000000007
answer = 1
for A,B in dict_F.values():
  answer = (answer*(power2(A)+power2(B)-1))%mod
answer = (answer+count_0-1)%mod
print(answer)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from math import gcd

N, *AB = map(int, sys.stdin.buffer.read().split())

dict_F = {}
count_0 = 0

def insert(A,B,s): # A>=0, B>0, s=0or1
  if (A,B) not in dict_F.keys():
    dict_F[(A,B)] = [0,0]
  dict_F[(A,B)][s] += 1

def make_power2(N):
  result = 1
  list_result = [1]
  for _ in range(N):
    result = (2*result)%mod
    list_result.append(result)
  return list_result

for i in range(N):
  A,B = AB[2*i], AB[2*i+1]
  if A==0 and B==0:
    count_0 += 1
    continue
  g = gcd(A,B)
  A //= g
  B //= g
  if A>=0 and B>0:
    insert(A,B,0)
  elif A>0 and B<=0:
    insert(-B,A,1)
  elif A<=0 and B<0:
    insert(-A,-B,0)
  elif A<0 and B>=0:
    insert(B,-A,1)

mod = 1000000007
power2 = make_power2(N)
answer = 1

for A,B in dict_F.values():
  answer = (answer*(power2[A]+power2[B]-1))%mod
answer = (answer+count_0-1)%mod

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

N=int(input())
A,B,C=[sorted(map(int,input().split())) for i in range(3)]
ans=a=c=0
for i in B:
    for j in A[a:]:
        if i>j:a+=1
        else: break
    for k in C[c:]:
        if i<k:break
        else: c+=1
    ans+=a*(N-c)
print(ans)

### FIXED CODE ###

N=int(input())
A,B,C=[sorted(map(int,input().split())) for i in range(3)]
ans=a=c=0
for i in B:
    while a<N and A[a]<i:
        a+=1
    while c<N and C[c]<=i:
        c+=1
    if c==N:break
    ans+=a*(N-c)
print(ans)
### BUGGY CODE ###

h,w,m=map(int, input().split())
from collections import defaultdict
hd=defaultdict(int)
wd=defaultdict(int)
hd2=defaultdict(list)
wd2=defaultdict(list)
for i in range(m):
    h0,w0=map(int, input().split())
    hd[h0]+=1
    hd2[h0].append(w0)
    wd[w0]+=1
    wd2[w0].append(h0)

max_h_list = [kv[0] for kv in hd.items() if kv[1] == max(hd.values())]
max_w_list = [kv[0] for kv in wd.items() if kv[1] == max(wd.values())]

ans=float('inf')

if len(max_h_list)>=len(max_w_list):
    for x in max_h_list:
        hlist=hd2[x]
        for y in max_w_list:
            if y in hlist:
                ans=min(ans,1)
            else:
                ans=min(ans,0)
else:
    for x in max_w_list:
        wlist=wd2[x]
        for y in max_h_list:
            if y in wlist:
                ans=min(ans,1)
            else:
                ans=min(ans,0)
print(hd[max_h_list[0]]+wd[max_w_list[0]]-ans)

### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline
h,w,m=map(int, input().split())
hd=[0 for i in range(h+1)]
wd=[0 for i in range(w+1)]
hw=defaultdict(int)
hmax=0
wmax=0
for i in range(m):
    h0,w0=map(int, input().split())
    hd[h0]+=1
    hmax=max(hmax,hd[h0])
    wd[w0]+=1
    wmax=max(wmax,wd[w0])
    hw[(h0,w0)]+=1

max_h_list=[]
max_w_list=[]
for k in range(h+1):
    if hd[k]==hmax:
        max_h_list.append(k)

for k in range(w+1):
    if wd[k]==wmax:
        max_w_list.append(k)

ans=float('inf')

for x in max_h_list:
    for y in max_w_list:
        if hw[(x,y)]==1:
            ans=min(ans,1)
        else:
            ans=min(ans,0)
            break
print(hmax+wmax-ans)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(K)]

mod = 998244353

dp = [0]*(N+1)
tmp = 1

for i in range(N-1):
    tmp = (tmp + dp[i]) % mod
    # dp[i] = tmp
    for l, r in LR:
        dp[min(i+l, N)] = (dp[min(i+l, N)] + tmp) % mod
        dp[min(i+r+1, N)] = (dp[min(i+r+1, N)] - tmp) % mod
print(dp[N-1])

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(K)]

mod = 998244353

dp = [0]*(N+1)
tmp = 1

for i in range(N-1):
    tmp = (tmp + dp[i]) % mod
    # dp[i] = tmp
    for l, r in LR:
        dp[min(i+l, N)] = (dp[min(i+l, N)] + tmp) % mod
        dp[min(i+r+1, N)] = (dp[min(i+r+1, N)] - tmp) % mod
print(dp[N-1])
### BUGGY CODE ###

N = int(input())
l = list()
for i in range(N):
    a = input()
    if a in l:
        a ==0
    else:
        l.append(a)

print(len(l))


### FIXED CODE ###

N = int(input())
l = list()
for i in range(N):
    a = input()
    l.append(a)

print(len(set(l)))
### BUGGY CODE ###

N = int(input())
X = str(input())


def popcount(bits: str):
    return len([elm for elm in bits if elm == '1'])


def f(num):
    if num == 0:
        return 0
    else:
        pc = popcount('{:b}'.format(num))
        return 1 + f(num % pc)


def reverse_bit(bits: str, digit):
    def toggle(a):
        if a == '1':
            return '0'
        else:
            return '1'

    ret = list(bits)
    ret[digit-1] = toggle(bits[digit-1])
    return ''.join(ret)

def convert(x: str):
    ans = 0
    i = 0
    for elm in list(x)[::-1]:
        if elm == '1':
            ans += 2 ** i
        i += 1
    return ans


for i in range(1, N+1):
    bits = reverse_bit(X, i)
    pc = popcount(bits)
    # print(f'# {bits} {convert(bits)} {pc}')
    print(f(convert(bits)))

### FIXED CODE ###

n = int(input())
# for i in range(n):
#     print('0', end='')
# print(flush=True)
s = input()
x = int(s, base=2)
popcount = s.count('1')
y_zero = x % (popcount + 1)
if popcount > 1:
    y_one = x % (popcount - 1)
dp = [-1] * n
dp[0] = 0
 
 
def calc(y):
    if dp[y] != -1:
        return dp[y]
    dp[y] = 1 + calc(y % bin(y).count('1'))
    return dp[y]
 
 
ans = [0] * n
rem_zero = 1
if popcount > 1:
    rem_one = popcount - 2
for i in range(n):
    if s[n - 1 - i] == '0':
        ans[n - 1 - i] = 1 + calc((y_zero + rem_zero) % (popcount + 1))
    elif popcount > 1:
        ans[n - 1 - i] = 1 + calc((y_one + rem_one) % (popcount - 1))
    else:
        ans[n - 1 - i] = 0
    rem_zero = rem_zero * 2 % (popcount + 1)
    if popcount > 1:
        rem_one = rem_one * 2 % (popcount - 1)
for i in range(n):
    print(ans[i])