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

import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    N = H*W+W

    def pos(h,w):
        return h*W+w

    G = []
    for h in range(H):
        G.append(list(input()))

    dp = [[INF] * N for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0

    for h in range(H):
        for w in range(W):
            if G[h][w] == "#": continue

            for i in range(4):
                dh = [0,1,0,-1][i]
                dw = [1,0,-1,0][i]
                if 0<=h+dh<H and 0<=w+dw<W:
                    if G[h+dh][w+dw] == "#": continue
                    dp[pos(h,w)][pos(h+dh,w+dw)] = 1
                    dp[pos(h+dh,w+dw)][pos(h,w)] = 1


    ans = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])


    for i in range(N):
        for j in range(N):
            if dp[i][j] != INF:
                ans = max(ans,dp[i][j])
    

    print(ans)





if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
from numba import njit
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

@njit(cache=True)
def pos(W,h,w):
    return h*W+w

def solve(H,W,G):
    N = H*W+W
    INF=10**18

    dp = np.full((N,N),INF)
    for i in range(N):
        dp[i][i] = 0

    for h in range(H):
        for w in range(W):
            if G[h][w]: continue

            for i in range(4):
                dh = [0,1,0,-1][i]
                dw = [1,0,-1,0][i]
                if 0<=h+dh<H and 0<=w+dw<W:
                    if G[h+dh][w+dw]: continue
                    dp[pos(W,h,w)][pos(W,h+dh,w+dw)] = 1
                    dp[pos(W,h+dh,w+dw)][pos(W,h,w)] = 1


    ans = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])


    for i in range(N):
        for j in range(N):
            if dp[i][j] != INF:
                ans = max(ans,dp[i][j])
    

    return ans





def main():
    H,W=mi()
    G = [[0] * W for _ in range(H)]
    for h in range(H):
        S = list(input())
        for w in range(W):
            G[h][w] = S[w] == "#"

    print(solve(H,W,np.array(G,bool)))


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('pos', '(i8,i8,i8,)')(pos)
    cc.export('solve', '(i8,i8,b1[:,:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    try:
        from my_module import solve
        from my_module import pos
    except:
        cc_export()
        exit()

    main()
### BUGGY CODE ###

H, N= map(int,input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())

def chmin(a, b):
    if a > b:
        return b
    else:
        return a

ma = max(A)
dp = [float("inf")] * (H + ma)
dp[0] = 0
for i in range(N):
    a = A[i]
    b = B[i]
    for j in range(1, H + ma):
        dp[j] = min(dp[j - a] + b, dp[j])
print(min(dp[H:]))


### FIXED CODE ###

H, N= map(int,input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())
ma = max(A)
dp = [float("inf")] * (H + ma)
dp[0] = 0
for i in range(N):
    a = A[i]
    b = B[i]
    for j in range(1, H + ma):
        dp[j] = min(dp[j - a] + b, dp[j])
print(min(dp[H:]))
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix
# CreatedDate:  2020-02-21 01:20:19 +0900
# LastModified: 2020-02-21 02:04:42 +0900
#


import os
import sys
import numpy as np
import heapq
#import pandas as pd
def make_matrix(matrix,a,b,c):
    matrix[a-1][b-1] = c
    matrix[b-1][a-1] = c

def initial_signal(i,matrix):
    d = [float("inf")]*(matrix.shape[0])
    d[i] = 0
    Q = []
    heapq.heappush(Q,(0,i))
    return d,Q

def relax(matrix,u,v,d,Q):
    if d[v] > d[u]+matrix[u][v]:
        d[v] = d[u]+matrix[u][v]
        heapq.heappush(Q, (d[v],v))


def dijkstra(i,matrix):
    d,Q = initial_signal(i,matrix)
    while Q:
        cost,u = heapq.heappop(Q)
        if d[u]<cost:
            continue
        for v in range(matrix.shape[0]):
            if matrix[u][v]!=0:
                relax(matrix,u,v,d,Q)
    return d
    

def main():
    N,M = map(int, input().split())
    matrix = np.zeros((N,N),dtype=np.int32)
    for _ in range(M):
        a,b,c = map(int,input().split())
        make_matrix(matrix,a,b,c)
    shortest = []
    for i in range(matrix.shape[0]):
        shortest.append(dijkstra(i,matrix))
    ans=0
    for i in range(N):
        for j in range(N):
            if matrix[i][j]!=0 and matrix[i][j]>shortest[i][j]:
                ans+=1
    print(ans//2)


if __name__ == "__main__":
    main()


### FIXED CODE ###

## https://atcoder.jp/contests/abc051/submissions/3281251
import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]
    
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    
    while q:
        cost, cur_node = heapq.heappop(q)
        
        if dist[cur_node] < cost:
            continue
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist

def main():
    n, m = map(int, input().split())
    adj = [[] for _ in range(n)]
    for i in range(m):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        adj[a].append((c, b))
        adj[b].append((c, a))
    shortest = []
    for i in range(n):
        shortest.append(dijkstra(adj, n, i))
    ans = 0
    for i in range(n):
        for cost, j in adj[i]:
            if cost > shortest[i][j]:
                ans += 1
    print(ans // 2)
                                                                                                                                                                                                     
if __name__=='__main__':
    main()
### BUGGY CODE ###

n=int(input())
s=[''.join(sorted(input())) for _ in range(n)]
ans=0
for x in set(s):
  cnt=s.count(x)
  ans+=cnt*(cnt-1)/2
print(int(ans))

### FIXED CODE ###

n=int(input())
s=[''.join(sorted(input())) for _ in range(n)]
ans=0
cnt={}
for i in range(n):
  if s[i] in cnt:
    cnt[s[i]]+=1
  else:
    cnt[s[i]]=1
print(sum(cnt[key]*(cnt[key]-1)//2 for key in cnt))
### BUGGY CODE ###

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

def resolve(a):
    target = N
    result = 0
    for i in a:
        if target > i:
            target = i
            result += i
        else:
            result += target
    return result

print(sum([resolve(a[x:]) for x in range(N)]))


### FIXED CODE ###

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

index = [-1] * (n + 1)
for i, v in enumerate(a):
    index[v] = i

area = [[i, i] for i in range(n + 1)]
result = 0
for i in range(n, 0, -1):
    position = index[i]
    l, r = area[position]
    area[r + 1][0] = l # right
    area[l - 1][1] = r # left
    result += (position - l + 1) * (r - position + 1) * i
print(result)
### BUGGY CODE ###

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

# 隣接リスト
graph = [[] for _ in range(n)]
for v in p:
    graph[v[0]-1].append(v[1])
    graph[v[1] - 1].append(v[0])

cnt = 0
for x in graph:
    point = 'good'
    for y in x:
        if h[graph.index(x)] <= h[y-1]:
            point = 'bad'
    if point == 'good':
        cnt += 1
print(cnt)

### FIXED CODE ###

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


n, m = map(int, readline().split())
h = list(map(int, readline().split()))
ab = [list(map(int, input().split())) for _ in range(m)]
l = [1]*n
for i in range(m):
    if h[ab[i][0] - 1] < h[ab[i][1] - 1]:
        l[ab[i][0] - 1] = 0
    elif h[ab[i][0] - 1] > h[ab[i][1] - 1]:
        l[ab[i][1] - 1] = 0
    else:
        l[ab[i][0] - 1] = 0
        l[ab[i][1] - 1] = 0
print(sum(l))
### BUGGY CODE ###

n, x = list(map(int, input().split()))
B = 0
blu = []

for i in range(n):
  b, l, u = list(map(int, input().split()))
  blu.append((b, l, u, x*u-b*u+b*l))
  B += b*l
blu.sort(key=lambda x: x[3], reverse=True)

ans = n*x
for i in range(n):
  ok = n*x
  ng = -1
  while ok-ng>1:
    A = 0
    tB = B
    mid = (ok+ng)//2
    k = mid//x
    t = mid%x
    for j in range(n):
      if j!=i and k>0:
        A += x*blu[j][2]
        tB += blu[j][0]*(blu[j][2]-blu[j][1])
        k -= 1
      elif k<=0:
        break
    if t!=0:
      if t<=blu[i][0]:
        A += t*blu[i][1]
      else:
        A += t*blu[i][2]
        tB += blu[i][0]*(blu[i][2]-blu[i][1])
    if A>=tB:
      ok = mid
    else:
      ng = mid
  ans = min(ans, ok)

print(ans)

### FIXED CODE ###

n, x = list(map(int, input().split()))
B = 0
blu = []
s = [0 for i in range(n)]

for i in range(n):
  b, l, u = list(map(int, input().split()))
  blu.append((b, l, u, x*u-b*u+b*l))
  B += b*l
blu.sort(key=lambda x: x[3], reverse=True)

for i in range(n):
  if i==0:
    s[i] = blu[i][3]
  else:
    s[i] = s[i-1] + blu[i][3]

ok = n*x
ng = -1
while ok-ng>1:
  A = 0
  mid = (ok+ng)//2
  k = mid//x
  t = mid%x
  for i in range(n):
    if t<=blu[i][0]:
      rm = t*blu[i][1]
    else:
      rm = t*blu[i][2] - blu[i][0]*(blu[i][2]-blu[i][1])
    if k==0:
      A = max(A, rm)
    elif i<k:
      A = max(A, s[k]-blu[i][3]+rm)
    else:
      A = max(A, s[k-1]+rm)
  if A>=B:
    ok = mid
  else:
    ng = mid

print(ok)
### BUGGY CODE ###

class SegTree:
    init_val = -1  # 問題によって変える

    def __init__(self, init_l):
        self.n = len(init_l)
        self.n0 = 2 ** (self.n - 1).bit_length()  # n以上で最小の2のべき乗
        self.l = [self.init_val] * 2 * self.n0  # 区間外の値を初期化
        for i in range(self.n):
            self.l[i + self.n0 - 1] = init_l[i]
        for i in range(self.n0 - 2, -1, -1):
            self.l[i] = self.func(self.l[2 * i + 1], self.l[2 * i + 2])

    # 問題によって変える
    def func(self, x, y):
        return max(x, y)

    def update(self, i, new):
        i += self.n0 - 1
        self.l[i] = new
        while i + 1:
            i = (i - 1) // 2
            self.l[i] = self.func(self.l[i * 2 + 1], self.l[i * 2 + 2])

    # Gets min between [a, b)
    def query(self, a, b):
        return self._query(a, b, 0, 0, self.n0)

    def _query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.init_val
        if a <= l and r <= b:
            return self.l[k]
        vl = self._query(a, b, k * 2 + 1, l, (l + r) // 2)
        vr = self._query(a, b, k * 2 + 2, (l + r) // 2, r)
        return self.func(vl, vr)

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
ba = []
for _ in range(n):
    a, b = map(int, input().split())
    ba.append([b, a])
ba.sort(reverse=True)
days = [x for x in range(m)]
ans = 0
s = SegTree(days)
for x in ba:
    a = x[1]
    b = x[0]
    lim = m - a
    if lim < 0:
        continue
    d = s.query(0, lim+1)
    if d >= 0:
        ans += b
        s.update(d, -1)
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
from heapq import *


n, m = map(int, input().split())
tmp = [ [] for _ in range(10 ** 5 + 1) ]
for _ in range(n):
    a, b = map(int, input().split())
    tmp[a].append(b)

h = []
ans = 0
for i in range(1, m+1):
    for bb in tmp[i]:
        heappush(h, -bb)
    if h:
        ans += -heappop(h)
print(ans)
### BUGGY CODE ###

n,k=map(int, input().split())
d=abs(n-k)
if n%k==0:
    print(0)
elif n>d:
    while d>abs(d-k):
        d=abs(d-k)
    print(d)
else:
    print(n)


### FIXED CODE ###

n,k=map(int, input().split())
d=abs(n-k)
t=n//k
if n%k==0:
    print(0)
elif n>d:
    a=n-t*k
    if a>abs(a-k):
        print(abs(a-k))
    else:
        print(a)
else:
    print(n)
### BUGGY CODE ###

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)
n = int(input())
A = list(map(int, input().split()))
ans = 0
def gcdEx(L, a):
    if A[0] == a:
        g = A[1]
    else:
        g = A[0]
    for l in L:
        if l != a:
            g = gcd(l, g)
    return g
for a in A:
    tmp = gcdEx(A, a)
    if tmp > ans:
        ans = tmp
print(ans)

### FIXED CODE ###

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)
n = int(input())
A = list(map(int, input().split()))
L = [0]*n
R = [0]*n
for i in range(n-1):
    R [i+1] = gcd(R[i], A[i])
    L[i+1] = gcd(L[i], A[-i-1])
print(max(gcd(R[i], L[-i-1]) for i in range(n)))
### BUGGY CODE ###

from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy
import collections
from operator import itemgetter
#以下てんぷら
def j(q):
    if q==1: print("Yes")
    else:print("No")
    exit(0)


def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")

def ip():
    return int(input())
def printrow(a):
    for i in range(len(a)):
        print(a[i])
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)

n = ip()                                     #入力整数1つ
#a,b,t= (int(i) for i in input().split())       #入力整数横2つ以上
a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#k = ip()                      #入力セット(整数改行あり)(1/2)
#v=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
#こっから本文
s = [a[0]]
if n%2:
    for i in range(1,n):
        if i%2:
            s.append(a[i])
        else: s.insert(0,a[i])
else:
    for i in range(1, n):
        if i % 2==0:
            s.append(a[i])
        else:
            s.insert(0, a[i])
for i in range(n):
    print(s[i],end=' ')
print()

### FIXED CODE ###

from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy
import collections
from operator import itemgetter
#以下てんぷら
def j(q):
    if q==1: print("Yes")
    else:print("No")
    exit(0)


def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")

def ip():
    return int(input())
def printrow(a):
    for i in range(len(a)):
        print(a[i])
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)

n = ip()                                     #入力整数1つ
#a,b,t= (int(i) for i in input().split())       #入力整数横2つ以上
a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#k = ip()                      #入力セット(整数改行あり)(1/2)
#v=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
#こっから本文
if n%2==0:
    for i in range(n-1,-1,-2):
        print(a[i],end=' ')
    for i in range(0,n,2):
        print(a[i],end=' ')
else:
    for i in range(n-1,-1,-2):
        print(a[i],end=' ')
    for i in range(1,n,2):
        print(a[i],end=' ')
### BUGGY CODE ###

n=int(input())
s=input()
if n<=3:
    print(0)
    exit()
ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        if s[i]==s[j]:
            continue
        for k in range(j+1,n):
            if s[i]!=s[k] and s[j]!=s[k]:
                if j-i!=k-j:
                    ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
if n<=3:
    print(0)
    exit()
r=set()
g=set()
b=set()
for i,c in enumerate(s):
    if c=='R':
        r.add(i)
    elif c=='G':
        b.add(i)
    else:
        g.add(i)
ans=0
lb=len(b)
for i in r:
    for j in g:
        t1=-1
        if abs(i-j)%2==0:
            t1=min(i,j)+abs(i-j)//2
        t2=max(i,j)+abs(i-j)
        t3=min(i,j)-abs(i-j)
        tc=0
        if t1 in b:
            tc+=1
        if t2 in b:
            tc+=1
        if t3 in b:
            tc+=1
        ans+=max(0,lb-tc)
print(ans)
### BUGGY CODE ###

import math
from functools import reduce

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

ans=0

k=int(input())
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans += gcd(a, b, c)
            
print(ans)

### FIXED CODE ###

from math import gcd

K = int(input())

result = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        t = gcd(a, b)
        for c in range(1, K + 1):
            result += gcd(t, c)
print(result)
### BUGGY CODE ###

N,Q = map(int,input().split(" "))
A = []

B = [0 for j in range(N)]
for i in range(N-1):
    tmp = list(map(int,input().split(" ")))
    A.append(tmp)
A.sort()
for j in range(Q):
    tmp = list(map(int,input().split(" ")))
    B[tmp[0]-1] += tmp[1]


for i in range(N-1):
        B[A[i][1]-1] += B[A[i][0]-1]

for i in range(N):
        print(B[i],end=" ")

### FIXED CODE ###

N,Q = map(int,input().split(" "))
A = [0]*N

B = [0 for j in range(N)]
for i in range(N-1):
    a,b = map(int,input().split(" "))
    A[b-1] = a-1
    
for j in range(Q):
    tmp = list(map(int,input().split(" ")))
    B[tmp[0]-1] += tmp[1]

for i in range(1,N):
        B[i] += B[A[i]]
for i in range(N):
        print(B[i],end=" ")
### BUGGY CODE ###

# ABC129D - Lamp
def main():
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    L, R = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    U, D = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    for x1 in range(H):
        for y1 in range(W):
            if S[x1][y1] == ".":  # left and upper sides of S
                U[x1][y1] = U[x1 - 1][y1] + 1
                L[x1][y1] = L[x1][y1 - 1] + 1
            x2, y2 = -x1 - 1, -y1 - 1
            if S[x2][y2] == ".":  # right and under sides
                D[x2][y2] = D[x2 + 1][y2] + 1
                R[x2][y2] = R[x2][y2 + 1] + 1
    ans = max(
        L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3 for i in range(H) for j in range(W)
    )
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

# ABC129D - Lamp
import sys
input = sys.stdin.readline

def main():
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    L, R = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    U, D = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == "#":
                L[i][j] == 0
                U[i][j] == 0
            else:
                if j == 0:
                    L[i][j] = 1
                else:
                    L[i][j] = L[i][j - 1] + 1
                if i == 0:
                    U[i][j] = 1
                else:
                    U[i][j] = U[i - 1][j] + 1
    for i in range(H - 1, -1, -1):
        for j in range(W - 1, -1, -1):
            if S[i][j] == "#":
                R[i][j] == 0
                D[i][j] == 0
            else:
                if j == W - 1:
                    R[i][j] = 1
                else:
                    R[i][j] = R[i][j + 1] + 1

                if i == H - 1:
                    D[i][j] = 1
                else:
                    D[i][j] = D[i + 1][j] + 1
    ans = max(
        L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3 for i in range(H) for j in range(W)
    )
    print(ans)


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

#!/usr/bin/env python3

n=int(input())

x,y=map(int, input().split())
for i in range(n-1):
    t,a=map(int, input().split())
    if (x<=t and y<=a):
        x=t
        y=a
    else:
        tmp=1
        while 1:
            if x<=t*tmp and y<=a*tmp:
                x=t*tmp
                y=a*tmp
                break
            tmp+=1
print(x+y)

### FIXED CODE ###

n=int(raw_input())
t=a=1

for i in range(n):
    x,y=map(int,raw_input().split())
    n=max((t+x-1)/x,(a+y-1)/y)
    t=n*x
    a=n*y
print t+a
### BUGGY CODE ###

h,w,m = list(map(int,input().split()))
t = [list(map(int,input().split())) for _ in range(m)]
from collections import Counter

x,y = zip(*t)
xcnt = Counter(x)
ycnt = Counter(y)

xcmax = max( xcnt.values() )
ycmax = max( ycnt.values() )
xlist = [k for k,v in xcnt.items() if v == xcmax]
ylist = [k for k,v in ycnt.items() if v == ycmax]
xylist = [ i*(10**6)+j for i in xlist for j in ylist ]
tlist = [ i[0]*(10**6) + i[1] for i in t ]
if len( set(xylist) - set(tlist) ) == 0:
  print( xcmax + ycmax -1 )
else:
  print( xcmax + ycmax )


### FIXED CODE ###

h,w,m = list(map(int,input().split()))
t = [list(map(int,input().split())) for _ in range(m)]
from collections import Counter
 
x,y = zip(*t)

xcnt = Counter(x)
ycnt = Counter(y)
 
xcmax = max( xcnt.values() )
ycmax = max( ycnt.values() )
xlist = [k for k,v in xcnt.items() if v == xcmax]
ylist = [k for k,v in ycnt.items() if v == ycmax]
if len(xlist) * len(ylist) > m:
  print( xcmax + ycmax )
else:
  xylist = { i*(10**6)+j for i in xlist for j in ylist }
  tlist = { i[0]*(10**6) + i[1] for i in t }
  if len( xylist - tlist ) == 0:
    print( xcmax + ycmax -1 )
  else:
    print( xcmax + ycmax )
### BUGGY CODE ###

import sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]


def my_popcount(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c


def f(x, cur):
    #print(x, cur)
    cnt = cur
    tmp = x
    while tmp:
        tmp = tmp%my_popcount(tmp)
        cnt +=1
    return cnt


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

Xint = int(X, 2)
popcountX = X.count("1")
#print("test", Xint, popcountX)
plus = Xint%(popcountX+1)
minus = 0
if popcountX != 1:
    minus = Xint%(popcountX-1)

X = list(X)
for i in range(N):
    if X[i] == "0":
        #print("arg", Xint%(popcountX+1), (2**(N-1-i))%(popcountX+1))
        print(f((plus + (2**(N-1-i))%(popcountX+1))%(popcountX+1), 1))
    else:
        if popcountX == 1:
            print(0)
        else:
            print(f((minus - (2**(N-1-i))%(popcountX-1))%(popcountX-1), 1))


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
X = input()
Xint = int(X, 2)
Xcount = X.count("1")

"""
0010
1010 10(mod2) -> 0
i = n-1の時だけ +1
0011 -> 3 -> 1->0
0110 -> 6(mod2) -> 0
"""

if Xcount == 1:
    for i in range(N):
        if X[i] == "1":
            print(0)
        elif i == N-1:
            print(2)
        else:
            print(1)
    exit()

Modplus, Modminus = Xint%(Xcount+1), Xint%(Xcount-1)

def f(x):
    if x == 0:
        return 0
    return f(x%bin(x).count("1"))+1

for i in range(N):
    if X[i] == "1":
        print(1+f((Modminus-pow(2, N-1-i, Xcount-1))%(Xcount-1)))
    else:
        print(1+f((Modplus+pow(2, N-1-i, Xcount+1))%(Xcount+1)))
### BUGGY CODE ###

a, b, k = map(int, input().split())
numlist = []

for i in range(a, b+1):
    if i < a + k or i >  b - k:
        numlist.append(i)

numSet = set(numlist)
numlist = list(numSet)
numlist.sort()
 
for l in range(len(numlist)):
    print(numlist[l])

### FIXED CODE ###

a, b, k = map(int, input().split())

if (b-a+1)/2 < k:
    for i in range(a, b+1):
        print(i)
else:
    for j in range(a, a+k):
        print(j)
    for k in range(b-k+1, b+1):
        print(k)