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

import queue
h, w=map(int, input().split())
grid = []
dydx = [[0, 1], [1,0], [-1, 0], [0, -1]]
done = [[0]*w for _ in range(h)]
que = queue.Queue()
res=0

for i in range(h):
    s = list(input().rstrip())
    grid.append(s)

def search(i , j, vec):
    t=0
    while i+vec[0]<h and j+vec[1]<w and i+vec[0]>-1 and j+vec[1]>-1 and grid[i+vec[0]][j+vec[1]]==".":
        i+=vec[0]
        j+=vec[1]
        t+=1
    return t;

for i in range(h):
    for j in range(w):
        if(grid[i][j]!="#") and not done[i][j]:
            tmp = 1
            for vec in dydx:
                tmp+=search(i, j, vec)

            res = max(res, tmp)

print(res)


### FIXED CODE ###

from collections import defaultdict

def dfs(i,j,dx,dy,kum):
    visited[i][j] = 1
    if grid[i][j]!="#" and visited[i][j]!=1:
        num[i][j]=max(num[i][j],dfs(i+dx,j+dy,dx,dy,kum+1))
    num[i][j] = max(num[i][j],kum)
    return kum
def main():
    h,w = map(int, input().split())
    grid = []
    for i in range(h):
        s = list(input().rstrip())
        grid.append(s)
    l = [[0]*w for _ in range(h)]
    r = [[0]*w for _ in range(h)]
    d = [[0]*w for _ in range(h)]
    u = [[0]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if grid[i][j]!="#":
                if j==0:
                    l[i][j]=1
                else:
                    l[i][j]=l[i][j-1]+1
            if grid[i][j]=="#":
                l[i][j]=0
            if grid[i][j]!="#":
                if i==0:
                    d[i][j]=1
                else:
                    d[i][j]=d[i-1][j]+1
            if grid[i][j]=="#":
                d[i][j]=0
    for i in range(h):
        for j in range(w-1,-1,-1):
            if grid[i][j]!="#":
                if j==w-1:
                    r[i][j]=1
                else:
                    r[i][j]=r[i][j+1]+1
            if grid[i][j]=="#":
                r[i][j]=0

    for i in range(h-1,-1,-1):
        for j in range(w):
            if grid[i][j]!="#":
                if i==h-1:
                    u[i][j]=1
                else:
                    u[i][j]=u[i+1][j]+1
            if grid[i][j]=="#":
                u[i][j]=0
    tmp = 0

    for i in range(h):
        for j in range(w):
            tmp = max(tmp, l[i][j]+r[i][j]+u[i][j]+d[i][j]-3)



    print(tmp)

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

N, K = map(int, input().split())
p = list(map(int, input().split()))
  
ans = []
for i in range(N - (K - 1)):
  a = p[i: i + K]
  if sum(a) > sum(ans):
    ans = a


print((sum(ans) + K) /2)

### FIXED CODE ###

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

a = 0
for i in range(N - K + 1):
  if i == 0:
    b = sum(p[0:K])
  else:
    b = b - p[i-1] + p[i + K - 1]
  
  if b > a:
    a = b
    f = i

ans = 0
for j in range(K):
  ans += (p[f + j] + 1) / 2

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

N, Q = [int(v) for v in input().split()]

va = [N-1] * (N - 1)
ha = [N-1] * (N - 1)

count = 0
black = (N - 2) * (N - 2)
vmax = N - 1
hmax = N - 1
for i in range(Q):
    a, b = [int(v)-1 for v in input().split()]
    if a == 0:
        if vmax > b:
            vmax = b
            va[1:ha[b]] = [b] * (ha[b] - 1)
        count += ha[b] - 1
    else:
        if hmax > b:
            hmax = b
            ha[1:va[b]] = [b] * (va[b] - 1)
        count += va[b] - 1

print(black - count)


### FIXED CODE ###

def main():
    N, Q = [int(v) for v in input().split()]

    Query = [[int(v)-1 for v in input().split()] for _ in range(Q)]

    rows = [N-1] * (N - 1)
    cols = [N-1] * (N - 1)

    black = (N - 2) * (N - 2)
    min_row = N - 1
    min_col = N - 1

    for ty, x in Query:
        if ty == 0:
            if x < min_col:
                for j in range(x, min_col):
                    rows[j] = min_row
                min_col = x
            black -= rows[x] - 1
        else:
            if x < min_row:
                for j in range(x, min_row):
                    cols[j] = min_col
                min_row = x
            black -= cols[x] - 1

    print(black)

main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()

h,n=MI()
lis=[LI() for i in range(n)]
mx=sorted(lis,reverse=True)[0][0]
#print(mx)
dp=[0 for i in range(h+mx)]
for i in range(1,h+mx):
    mn=inf
    #print(i,i)
    for j in range(n):
        u=dp[max(i-lis[j][0],0)]+lis[j][1]
        #print(u)
        if u<mn:
            mn=u
    dp[i]=mn
#print(dp)
z=[]
for i in range(mx):
    z.append(dp[h+i])
print(min(z))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()

h,n=MI()
lis=[LI() for i in range(n)]
mx=sorted(lis,reverse=True)[0][0]
#print(mx)
dp=[0 for i in range(h+mx)]
for i in range(1,h+mx):
    mn=inf
    #print(i,i)
    for j in range(n):
        u=dp[max(i-lis[j][0],0)]+lis[j][1]
        #print(u)
        if u<mn:
            mn=u
    dp[i]=mn
#print(dp)
z=[]
for i in range(mx):
    z.append(dp[h+i])
print(min(z))
### BUGGY CODE ###

def prime_decomp(n):
    i=2
    res = []
    while n>1:
        if n%i==0:
            res.append(i)
            while n%i==0:
                n //= i
        i+=1
    return res


def main():
    from fractions import gcd
    A, B = [int(x) for x in input().split()]

    g = gcd(A, B)
    d = prime_decomp(g)
    print(len(d)+1)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def prime_factors(n: int) -> list:
    tmp = n
    i = 2
    res = []
    while i*i <= n:
        if tmp%i==0:
            res.append(i)
            while tmp%i==0:
                tmp //= i
        i += 1
    # add remaining factor
    if tmp > 1:
        res.append(tmp)
    return res


def main():
    from fractions import gcd
    A, B = [int(x) for x in input().split()]

    g = gcd(A, B)
    factors = prime_factors(g)
    print(len(factors)+1)


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

h,w=map(int,input().split())
c=eval('list(input()),'*h)
q=[]
e=q.append
for i in range(h):
 for j in range(w):
  if'.'>c[i][j]:e((i,j,0))
a=0
while q:
 y,x,v=q.pop(0);a=max(a,v)
 for i,j in((y,x-1),(y,x+1),(y-1,x),(y+1,x)):
  if h>i>=0and w>j>=0and'#'<c[i][j]:c[i][j]='#';e((i,j,v+1))
print(a)

### FIXED CODE ###

from collections import*
h,w=map(int,input().split())
c=eval('list(input()),'*h)
q=deque()
for i in range(h):
    for j in range(w):
        if c[i][j]=='#':
            q.append((i,j,0))
ans=0
while q:
    y,x,v=q.popleft()
    ans=max(ans,v)
    for i,j in((y,x-1),(y,x+1),(y-1,x),(y+1,x)):
        if h>i>=0 and w>j>=0 and c[i][j]=='.':
            c[i][j]='#'
            q.append((i,j,v+1))
print(ans)
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
for i in range(n):
    t = x[:i] + x[i + 1:]
    t = sorted(t)
    print(t[n // 2 - 1])

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
t = sorted(x)
mid1, mid2 = t[n // 2 - 1], t[n // 2]
for i in range(n):
    if x[i] <= mid1:
        print(mid2)
    else:
        print(mid1)
### BUGGY CODE ###

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

def trans(arr):
    result=[]
    for i in range(1,len(arr)+1):
        ans=0
        for j in range(1,len(arr)+1):
            kyori=abs(i-j)
            if kyori<=arr[j-1]:
                ans+=1
            else:
                continue
        result.append(ans)
    arr=result
    return arr

if N<=K:
    ans=[N]*N
    ans=" ".join(map(str,ans))
    print(ans)
else:
    for i in range(K):
        A=trans(A)
    A=" ".join(map(str,A))
    print(A)

### FIXED CODE ###

#素のPythonでは通りませんでしたが，PyPyを使ったら通りました
N, K = map(int, input().split())
As = list(map(int, input().split()))

for i in range(K):
    table = [0 for _ in range(N*2)]
    # imos法 - メモ
    for j in range(N):
        ai = As[j]
        # 電球が照らす左端をメモ
        table[max((j-ai)*2-1, 0)] += 1
        # 電球が照らす右端をメモ
        table[min((j+ai)*2+1, N*2-1)] -= 1
    
    # imos法 - シミュレート
    for j in range(N*2):
        if j > 0:
            table[j] += table[j-1]
    
    # 答えになおす
    for j in range(N):
        As[j] = table[j*2]
    
    exit_condition = True
    for j in range(N):
        if As[j] != N:
            exit_condition = False
            break
    
    if exit_condition:
        print(*As)
        exit(0)
            

print(*As)
### BUGGY CODE ###

n =int(input())
values = list(map(int, input().split()))
import operator
from functools import reduce
a = reduce(operator.mul, values)

if  a > 10**18:
  print(-1)
else:
  print(a)

### FIXED CODE ###

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

N = int(input())
S = input()
ans = 0
P = []
for a in range(10):
  A = str(a)
  k = 0
  ind1 = -1
  while k < len(S)-2:
    s = S[k]
    if A == s:
      ind1 = k
      break
    k += 1
  if ind1 == -1:
    continue
  for b in range(10):
    B = str(b)
    l = ind1+1
    ind2 = -1
    while l < len(S)-1:
      s = S[l]
      if B == s:
        ind2 = l
        break
      l += 1
    #print(a,b,ind1,ind2)
    if ind2 == -1:
      continue
    for c in range(10):
      C = str(c)
      m = ind2+1
      while m < len(S):
        s = S[m]
        if C == s:
          ans += 1
          break
        m += 1
print(ans)

#print(*ans, sep='/n')

### FIXED CODE ###

n=int(input())
s=input()
ans=0
 
for i in range(10):
    for j in range(10):
        for k in range(10):
            x=s.find(str(i))
            if x!=-1:
                y=s.find(str(j),x+1)
                if y!=-1:
                    z=s.find(str(k),y+1)
                    if z!=-1:
                        ans+=1
print(ans)
### BUGGY CODE ###

while 1:
    n,p = map(int,input().split())
    if p+n<1:break
    man = [i for i in [0]*n]
    ball,a = p,0
    while p not in man:
        if ball >0:ball,man[a%n] =ball-1, man[a%n]+1
        elif ball == 0:ball,man[a%n] = man[a%n],ball
        a+=1
    print(man.index(max(man)))        

### FIXED CODE ###

while 1:
    n,p = map(int,input().split())
    if n==0:break
    man =  [0]*n
    ball,a = p,0
    while 1:
        a%=n
        if ball >0:
            ball-=1
            man[a]+=1
        elif ball == 0:ball,man[a] = man[a],ball
        if man[a]==p:break
        a+=1
    print(a)
### BUGGY CODE ###

n, k = [int(i) for i in input().split()]
heights = []
for i in range(0,n):
    heights.append(int(input()))

heights.sort()

answer = -1
for i in range(0, n-k+1):
    xlist = heights[i:i + k]
    item = max(xlist) - min(xlist)
    if answer == -1 or item < answer:
        answer = item

print(answer)

### FIXED CODE ###

n, k = [int(i) for i in input().split()]
heights = [int(input()) for i in range(n)]

heights.sort()

# あり得る最大のサイズ差
answer = max(heights) - min(heights)

for i in range(0, n-k+1):
    candidate = heights[i+k-1] - heights[i]
    if candidate < answer:
        answer = candidate

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

s = str(input())
q = int(input())
queries = list()
for ii in range(0,q):
  queries.append(input())
  
#print(queries)

for query in queries:
  if query.startswith("1"):
    s = s[::-1]
  elif query.startswith("2"):
    if query[2] == "1":
      s = query[4] + s
    elif query[2] == "2":
      s = s + query[4]

print(s)

### FIXED CODE ###

from collections import deque

s = deque(list(input()))
#print(s)
q = int(input())
queries = list()
for ii in range(0,q):
  queries.append(input())
  
#print(queries)
# True -> straight, False -> back
order_flag = True

for query in queries:
  if query.startswith("1"):
    order_flag = not order_flag
  elif query.startswith("2"):
    if query[2] == "1":
      if order_flag:
        s.appendleft(query[4])
      else:
        s.append(query[4])
    elif query[2] == "2":
      if order_flag:
        s.append(query[4])
      else:
        s.appendleft(query[4])
        
if order_flag:
  print(''.join(list(s)))
else:
  s.reverse()
  print(''.join(list(s)))
### BUGGY CODE ###

S = input()
K = int(input())
ans = 0

T = ""
for _ in range(K):
    T += S

for ti in range(1, len(T)):
    if T[ti] == T[ti - 1]:
        T = T[: ti] + "?" + T[ti + 1:]
        ans += 1

print(ans)


### FIXED CODE ###

S = input()
K = int(input())
ans_s2, ans_s3 = 0, 0

# 例外処理
if len(S) == 1:
    print(K // 2)
    exit()
elif len(set(S)) == 1:
    print(len(S) * K // 2)
    exit()

S_double = S + S
for i in range(1, len(S_double)):
    if S_double[i] == S_double[i - 1]:
        S_double = S_double[: i] + "?" + S_double[i + 1:]
        ans_s2 += 1

S_triple = S + S + S
for j in range(1, len(S_triple)):
    if S_triple[j] == S_triple[j - 1]:
        S_triple = S_triple[: j] + "?" + S_triple[j + 1:]
        ans_s3 += 1

ans_increase = ans_s3 - ans_s2  #K>=3のときの増分

ans = ans_s2 + max(0, ans_increase * (K - 2))
print(ans)
### BUGGY CODE ###

z,s=1,0
d=[1]+[0]*7**6
e=d[:]
for _ in'_'*input():
 a=input();s+=a;i=s;z*=3
 while~i:d[i]+=d[i]+d[i-a];e[i]+=e[i-a];i-=1
print(z+~s%2*e[s//2]*3-3*sum(d[-~s//2:]))%998244353

### FIXED CODE ###

M,z,s=998244353,1,0
d=[1]+[0]*7**6
e=[1]+[0]*7**6
for _ in'_'*input():
 a=input();s+=a;i=s;z*=3
 while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
i=s
while i*2>=s:z-=d[i]*3;i-=1
print(z+~s%2*e[i+1]*3)%M
### BUGGY CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline

D, G = [int(x) for x in input().strip().split()]
P = [''] * D
for d in range(D):
    p, c = [int(x) for x in input().strip().split()]
    P[d] = [0] + [(d + 1) * 100 * (i + 1) for i in range(p)]
    P[d][-1] += c

d = defaultdict(int)
def f(P, D, qnum, trial, d, score=[]):
    if (qnum, trial, sum(score)) in d:
        return d[(qnum, trial, sum(score))]
    #print('x={}, a={}, c={}'.format(x, a, c))
    if qnum == D:
        if sum(score) >= G:
            #print('  OK : {}'.format(a))
            return trial
        else:
            #print('  NG')
            return 10 ** 9 + 7
    ret = 10 ** 9 + 7
    for n in range(len(P[qnum])):
        t = score[:]
        t.append(P[qnum][n])
        ret = min(ret, f(P, D, qnum+1, trial+n, d, t))
    d[(qnum, trial, sum(score))] = ret
    return ret

print(f(P, D, 0, 0, d))

### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline

D, G = [int(x) for x in input().strip().split()]
P = [''] * D
for d in range(D):
    p, c = [int(x) for x in input().strip().split()]
    P[d] = [0] + [(d + 1) * 100 * (i + 1) for i in range(p)]
    P[d][-1] += c

d = defaultdict(int)
def f(P, D, qnum, trial, d, flag=False, score=[]):
    if (qnum, trial, sum(score)) in d:
        return d[(qnum, trial, sum(score))]
    #print('qnum={}, trial={}, score={}'.format(qnum,trial,score))
    if qnum == D:
        if sum(score) >= G:
            #print('  OK : {}'.format(trial))
            return trial
        else:
            #print('  NG')
            return 10 ** 9 + 7
    ret = 10 ** 9 + 7
    if flag:
        N = [0, len(P[qnum])-1]
    else:
        N = range(len(P[qnum]))
    for n in N:
        flag2 = flag
        t = score[:]
        t.append(P[qnum][n])
        if not flag and n != len(P[qnum]) - 1 and n != 0:
            flag2 = True
        ret = min(ret, f(P, D, qnum+1, trial+n, d, flag2, t))
    d[(qnum, trial, sum(score))] = ret
    return ret

print(f(P, D, 0, 0, d))
### BUGGY CODE ###

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

def rev(x):
    if x=="S":
        return "W"
    else:
        return "S"

def wolfsheep(xy):
    global n,s
    result=[xy[0],xy[1]]

    for i in range(1,n+1):
        s+=s[0]
        if result[i]=="S":
            if s[i]=="o":
                result.append(result[i-1])
            else:
                result.append(rev(result[i-1]))
        else:
            if s[i]=="o":
                result.append(rev(result[i-1]))
            else:
                result.append(result[i-1])

    if result[0]==result[n] and result[1]==result[n+1]:
        return result
    else:
        return 0

#SWパターン
tmp= wolfsheep("SW")
if tmp!=0:
    print("".join(tmp[:-2]))
    exit()

#SSパターン
tmp= wolfsheep("SS")
if tmp!=0:
    print("".join(tmp[:-2]))
    exit()
#WWパターン
tmp= wolfsheep("WW")
if tmp!=0:
    print("".join(tmp[:-2]))
    exit()
#WSパターン
tmp= wolfsheep("WS")
if tmp!=0:
    print("".join(tmp[:-2]))
    exit()

print(-1)

### FIXED CODE ###

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

def rev(x):
    if x=="S":
        return "W"
    else:
        return "S"

def wolfsheep(xy):
    global n,s
    result=[xy[0],xy[1]]

    for i in range(1,n+1):
        s+=s[0]
        if result[i]=="S":
            if s[i]=="o":
                result.append(result[i-1])
            else:
                result.append(rev(result[i-1]))
        else:
            if s[i]=="o":
                result.append(rev(result[i-1]))
            else:
                result.append(result[i-1])

    if result[0]==result[n] and result[1]==result[n+1]:
        return result
    else:
        return 0

#SWパターン
tmp= wolfsheep("SW")
if tmp!=0:
    print("".join(tmp[:-2]))
    exit()

#SSパターン
tmp= wolfsheep("SS")
if tmp!=0:
    print("".join(tmp[:-2]))
    exit()
#WWパターン
tmp= wolfsheep("WW")
if tmp!=0:
    print("".join(tmp[:-2]))
    exit()
#WSパターン
tmp= wolfsheep("WS")
if tmp!=0:
    print("".join(tmp[:-2]))
    exit()

print(-1)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
l = []
r = []
for i in range(Q):
    L, R = map(int, input().split())
    l.append(L-1)
    r.append(R)
for i in range(Q):
    print((S[l[i]:r[i]]).count('AC'))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]

cnt = [0] * (N + 1)
for i in range(N):
    if S[i:i+2] == 'AC':
        cnt[i+1] = cnt[i] + 1 
    else:
        cnt[i+1] = cnt[i]

for i in range(Q):
    print(cnt[lr[i][1]-1]-cnt[lr[i][0]-1])
### BUGGY CODE ###

n = int(input())
#l = [0]*n
l = [int(input()) for i in range(n)]

for i in range(n):
  l_b = l[:i]
  l_a = l[i+1:]
  if i == 0:
    print(max(l_a))
  elif i == n-1:
    print(max(l_b))
  else:
    print(max(max(l_b), max(l_a)))

### FIXED CODE ###

n = int(input())
#l = [0]*n
l = [int(input()) for i in range(n)]

m_l = [0]
m_r = [0]

for i in range(n):
  m_l.append(max(m_l[i], l[i]))
  m_r.append(max(m_r[i], l[-(i+1)]))
m_r = m_r[::-1]
#print(m_l) 
#print(m_r)

for i in range(n):
  print(max(m_l[i], m_r[i+1]))
### BUGGY CODE ###

def modpow(a,n,mod=10**9+7):
    res=1
    while n>0:
        if n&1:
            res=res*a%mod
        a=a*a%mod
        n>>=1
    return res%mod

def modcmb(n,r,mod=10**9+7):
    res=1
    div=min(r,n-r)
    for i in range(div):
        res=res*(n-i)*modpow(div-i,mod-2)%mod
    return res%mod

n,a,b=[int(i) for i in input().split()]
ans=modpow(2,n)-1
ans-=modcmb(n,a)
ans%=10**9+7
ans-=modcmb(n,b)
ans%=10**9+7
print(ans)

### FIXED CODE ###

def modpow(a,n,mod=10**9+7):
    res=1
    while n>0:
        if n&1:
            res=res*a%mod
        a=a*a%mod
        n>>=1
    return res%mod

def modcmb(n,r,mod=10**9+7):
    res=1
    div=min(r,n-r)
    for i in range(div):
        res=res*(n-i)*modpow(div-i,mod-2)%mod
    return res%mod

n,a,b=[int(i) for i in input().split()]
ans=modpow(2,n)-1
ans-=modcmb(n,a)
ans%=10**9+7
ans-=modcmb(n,b)
ans%=10**9+7
print(ans)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
x = input()

ppc = {}

def popcount(n):    
  if n in ppc:
    return ppc[n]  
  if n == 0:
    return 0
  b = bin(n).count('1')  
  tmp = n%b
  ppc[n] = popcount(tmp) + 1
  return ppc[n]

bit = int('0b'+x,0)
for i in range(n,0,-1):      
  print(popcount(bit ^ (1 << (i-1))))

### FIXED CODE ###

n = int(input())
X = input()

def goes_to_zero(n):
  cnt = 0
  while(n > 0):
    n %= bin(n).count('1')
    cnt += 1
  return cnt
  
c1 = X.count('1')
xint = int(X,2)
xtp = xint % (c1 + 1)
if (c1 - 1) == 0:  
  xtm = 0
else:
  xtm = xint % (c1 - 1)
  
for i in range(n)  :
  if X[i] == '0':
    print(goes_to_zero( (xtp + pow(2,n-1-i,(c1+1))) % (c1+1) ) + 1)
  else:
    if (c1-1) == 0:
      print(0)
    else:
      print(goes_to_zero( (xtm - pow(2,n-1-i,(c1-1)) ) % (c1-1) ) +1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
read = sys.stdin.read

import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

def main():
  n, m, s, t = map(int, input().split())
  U, V, A, B = np.array(read().split(), dtype=np.int64).reshape(m, 4).T
  csr_yen = csr_matrix((A, (U, V)), shape=(n+1, n+1))
  csr_snuuk = csr_matrix((B, (U, V)), shape=(n+1, n+1))
  G_yen = dijkstra(csr_yen, directed=False, indices=s)
  G_snuuk = dijkstra(csr_snuuk, directed=False, indices=t)
  L = []
  L_append = L.append
  U = 10**15
  now = U
  for i in range(n, 0, -1):
    now = min(now, int(G_yen[i]+G_snuuk[i]))
    L_append(U-now)
  print(*L[::-1], sep="\n")
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
import heapq

def dijkstra(n, start, edge):
    dist = [float("inf")]*n
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, v = heapq.heappop(que)
        if dist[v] < d:
            continue
        for nv, nd in edge[v]:
            if dist[nv] > d + nd:
                dist[nv] = d + nd
                heapq.heappush(que, (dist[nv], nv))
    return dist
    
n, m, s, t = map(int, input().split())
G_yen = [[] for _ in range(n+1)]
G_snuuk = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    G_yen[u].append((v, a))
    G_yen[v].append((u, a))
    G_snuuk[u].append((v, b))
    G_snuuk[v].append((u, b))
dijk_yen = dijkstra(n+1, s, G_yen)
dijk_snuuk = dijkstra(n+1, t, G_snuuk)
L = []
U = 10**15
now = U
for i in range(n, 0, -1):
    now = min(now, dijk_yen[i]+dijk_snuuk[i])
    L.append(U-now)
print(*L[::-1], sep="\n")
### BUGGY CODE ###

#E
n,m,k = list(map(int,input().split()))
fac = [1 for i in range(n)]
finv = [1 for i in range(n)]
inv = [1 for i in range(n)]
MOD = 998244353
for i in range(2,n):
    fac[i] = fac[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD
def comb(n,k):
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
ans = 0
for i in range(k+1):
#     print(comb(n-1,i),m*(m-1)**(n-i-1))
    ans += (comb(n-1,i)*(m*(m-1)**(n-i-1)%MOD))%MOD
    ans %= MOD
print(ans)

### FIXED CODE ###

#E
n,m,k = list(map(int,input().split()))
fac = [1]*n
finv = [1]*n
inv = [1]*n
MOD = 998244353
for i in range(2,n):
    fac[i] = fac[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD
def comb(n,k):
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD

ans = 0
for i in range(k+1):
#     print(comb(n-1,i),m*(m-1)**(n-i-1))
    ans += comb(n-1,i)*m*pow(m-1,n-i-1,MOD)%MOD
    ans %= MOD
print(ans)