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

import itertools


def main():
    n = int(input())
    a = map(int, input().split())
    count = 0
    al = list(itertools.combinations(a, 2))
    for i in al:
        count += i[0]*i[1]
    return count % (10**9+7)


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

import itertools


def main():
    count = 0
    MOD = 10**9+7
    n = int(input())
    a = list(map(int, input().split()))
    s = [0]
    for i in range(n-1):
        s.append((s[i]+a[i]) % MOD)
    for ai, si in zip(a, s):
        count += (ai*si) % MOD
    return count % MOD


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

n, W = map(int, input().split())
wv = (map(int, input().split()) for _ in range(n))
dp = [0] * (W+1)

for w, v in wv:
    for j in range(W, w-1, -1):
        DP = dp[j-w] + v
        if dp[j] < DP:
            dp[j] = DP
print(dp[-1])

### FIXED CODE ###

def dp():
    n, W = map(int, input().split())
    wv = (map(int, input().split()) for _ in range(n))
    dp = [0] * (W+1)

    for w, v in wv:
        for j in range(W, w-1, -1):
            DP = dp[j-w] + v
            if dp[j] < DP:
                dp[j] = DP
    return max(dp)
print(dp())
### BUGGY CODE ###

import collections
import string

def s_to_hist(s):
    hist = collections.Counter()
    for c in s:
        hist[c] += 1
    hist_list = []
    for al in string.ascii_letters:
        hist_list.append(str(hist[al]))
    return " ".join(hist_list)

s_hist = collections.Counter()

N = int(input())
for n in range(N):
    s = input().strip()
    s_hist[s_to_hist(s)] += 1

ans = 0
for key in s_hist:
    ans += s_hist[key]*(s_hist[key]-1)/2
print(int(ans))

### FIXED CODE ###

import collections

N = int(input())
s_hist = collections.Counter()

for n in range(N):
    s = input().strip()
    s_hist[" ".join(sorted(s))] += 1

ans = 0
for pair in s_hist.most_common():
    ans += s_hist[pair[0]]*(s_hist[pair[0]]-1)/2
    if(pair[1] == 1):
        break
print(int(ans))
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

maxa = max(A)

for i in range(N):
    if A[i] == maxa:
        if i == 0:
            print(max(A[1:]))
        elif i == N-1:
            print(max(A[:-1]))
        else:
            print(max(max(A[:i]), max(A[i+1:])))
    else:
        print(maxa)

### FIXED CODE ###

n=int(input())
a = [int(input()) for i in range(n)]
b = sorted(a)
for i in a:
    print(b[-2] if i==b[-1] else b[-1])
### BUGGY CODE ###

import sys

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

### FIXED CODE ###

from collections import*
from bisect import*
s=input()
n=len(s)
t=input()
d=defaultdict(list)
for i,c in enumerate(s):
    d[c].append(i)
m=-1
o=0
for c in t:
    if not d[c]:
        print(-1)
        exit()
    i=bisect(d[c],m)
    if len(d[c])==i:
        o+=1
        m=d[c][0]
    else:
        m=d[c][i]
print(o*n+m+1)
### BUGGY CODE ###

N=int(input())
D=list(map(int,input().split()))
D.sort()
mi=D[0]
ma=D[N-1]
point=0
for j in range(mi,ma+1): #Kはj
    i=0
    while D[i]<j and i<N-1:
        i+=1
    if i==N//2 :
        point+=1
print(point)

### FIXED CODE ###

N=int(input())
D=list(map(int,input().split()))
D.sort()
mi=D[0]
ma=D[N-1]
point=0
for j in range(mi,ma+1): #Kはj
    if D[N//2-1]<j<=D[N//2]:
        point+=1
print(point)
### BUGGY CODE ###

import numpy as np
import sys

input = sys.stdin.readline

R, C, K = map(int, input().split())
table = [[None] * (C + 1) for _ in range(R + 1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    table[r][c] = v

dp = np.zeros((R + 1, C + 1, 4), dtype=int)
for r in range(1, R + 1):
    for c in range(1, C + 1):
        m = dp[r - 1, c].max()
        dp[r, c] = np.maximum(m, dp[r, c - 1])
        if table[r][c] is not None:
            dp[r, c, 1:] = np.maximum(dp[r, c, 1:],
                                      np.maximum(m, dp[r, c - 1, :-1]) + table[r][c])

print(dp[-1, -1].max())


### FIXED CODE ###

import sys

input = sys.stdin.readline

R, C, K = map(int, input().split())
D = dict()
for _ in range(K):
    r, c, v = map(int, input().split())
    D[(r, c)] = v

dp0 = [[0] * (C + 1) for _ in range(R + 1)]
dp1 = [[0] * (C + 1) for _ in range(R + 1)]
dp2 = [[0] * (C + 1) for _ in range(R + 1)]
dp3 = [[0] * (C + 1) for _ in range(R + 1)]

for r in range(1, R + 1):
    for c in range(1, C + 1):
        m = max(dp0[r - 1][c], dp1[r - 1][c], dp2[r - 1][c], dp3[r - 1][c])
        dp0[r][c] = max(m, dp0[r][c - 1])
        dp1[r][c] = max(m, dp1[r][c - 1])
        dp2[r][c] = max(m, dp2[r][c - 1])
        dp3[r][c] = max(m, dp3[r][c - 1])
        if (r, c) in D:
            dp1[r][c] = max(dp1[r][c], m + D[(r, c)], dp0[r][c - 1] + D[(r, c)])
            dp2[r][c] = max(dp2[r][c], m + D[(r, c)], dp1[r][c - 1] + D[(r, c)])
            dp3[r][c] = max(dp3[r][c], m + D[(r, c)], dp2[r][c - 1] + D[(r, c)])
print(max(dp0[-1][-1], dp1[-1][-1], dp2[-1][-1], dp3[-1][-1]))
### BUGGY CODE ###

n, m = map(int, input().split())
lst = [[] for _ in range(n + 1)]
py = []
for i in range(m):
    p, y = map(int, input().split())
    py.append([p, y])
    lst[p].append(y)

for i in range(n+1):
    lst[i] = sorted(lst[i])
ans = []
for i, j in py:
    ans.append(str(i).zfill(6) + str(lst[i].index(j)+1).zfill(6))
print(*ans, sep=('\n'))


### FIXED CODE ###

n, m = map(int, input().split())
lst = [[] for _ in range(n + 1)]
py = [tuple(map(int, input().split())) for i in range(m)]

for i, (p, y) in enumerate(py):
    lst[p].append((y, i))

ans = [None] * m

for p, l in enumerate(lst):
    l.sort()
    for j, (y, i) in enumerate(l):
        ans[i] = str(p).zfill(6) + str(j + 1).zfill(6)

print(*ans, sep=('\n'))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)
from collections import defaultdict

ans=[]
V=defaultdict(set)

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

a,b=map(int,input().split())
V[a].add(b)
V[b].add(a)
ans.append(a)
ans.append(b)

for i in range(1,M):
  a,b=map(int,input().split())
  V[a].add(b)
  V[b].add(a)

def solve(li):
  s=li[0]
  e=li[-1]
  for v in V[s]:
    if not(v in li):
      return solve([v]+li)
  for v in V[e]:
    if not(v in li):
      return solve(li+[v])
  print(len(li))
  print(*li)
  return

solve(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)

from collections import defaultdict
N, M = [int(_) for _ in input().split()]
V = defaultdict(list)
for i in range(M):
    A, B = [int(_) for _ in input().split()]
    V[A].append(B)
    V[B].append(A)

def solve(N, M, V):
    result = [1, V[1][0]]
    used = [False] * (N + 1)
    for x in result:
        used[x] = True

    def check_edge(i):
        for e in V[result[i]]:
            if not used[e]:
                if i == -1:
                    result.append(e)
                else:
                    result.insert(i, e)
                used[e] = True
                return True
        return False

    while True:
        if check_edge(0): continue
        if check_edge(-1): continue
        return result

result = solve(N, M, V)
print(len(result))
print(*result)
### BUGGY CODE ###

from collections import defaultdict

n = int(input())
s = list(input())
q = int(input())
ql = [input().split() for _ in range(q)]

w = 800
sl = []
dl = []
for i in range((n+w-1)//w):
    ss = s[i*w:min((i+1)*w,n)]
    dl.append(set(ss))
    sl.append(ss)
if len(dl)%2==1:
    dl.append(set())
dl2 = []
for i in range(len(dl)//2):
    dl2.append(dl[2*i] | dl[2*i+1])
for i in range(q):
    if ql[i][0]=="1":
        idx = int(ql[i][1])-1
        c = ql[i][2]

        ss = sl[idx//w]
        ss[idx%w] = c
        s[idx] = c
        sl[idx//w] = ss
        dl[idx//w] = set(ss)
        if (idx//w)%2==0:
            dl2[idx//w//2] = dl[idx//w] | dl[idx//w+1]
        else:
            dl2[idx//w//2] = dl[idx//w-1] | dl[idx//w]
    else:
        l = int(ql[i][1])-1
        r = int(ql[i][2])-1

        li = l//w
        ri = r//w
        if abs(li-ri)<2:
            print(len(set(s[l:r+1])))
        else:
            u = set(sl[li][l%w:])
            u = u | set(sl[ri][:r%w+1])
            if (li+1)%2==1:
                u = u | dl[li+1]
                li += 1
            if (ri-1)%2==0:
                u = u | dl[ri-1]
                ri -= 1
            for j in range(li+1,ri,2):
                u = u | dl2[j//2]
            print(len(u))


### FIXED CODE ###


class SegTree(object):
    """docstring for SegTree."""
    def __init__(self, l, _n):
        n = 1
        while n<_n:
            n *= 2
        self.n = n
        self.dat = [0 for _ in range(2*n)]
        for i in range(_n):
            self.dat[i+n-1] |= 1<<l[i]
        self.init(0)

    def init(self, i):
        if i>=self.n-1:
            return self.dat[i]
        self.dat[i] = self.init(self.left(i)) | self.init(self.right(i))
        return self.dat[i]

    def par(self, i):
        return (i-1)//2

    def left(self, i):
        return 2*i+1

    def right(self, i):
        return 2*i+2

    def update(self, i, x):
        i += self.n-1
        self.dat[i] = 1<<x
        while i>0:
            i = self.par(i)
            self.dat[i] = self.dat[self.left(i)] | self.dat[self.right(i)]

    def q(self,a,b,k,l,r):
        if r<=a or b<=l:
            return 0
        if a<=l and r<=b:
            return self.dat[k]
        return self.q(a,b,self.left(k),l,(l+r)//2) | self.q(a,b,self.right(k),(l+r)//2,r)

    def query(self,a,b):
        return self.q(a,b,0,0,self.n)

n = int(input())
s = [ord(c)-ord("a") for c in input()]
q = int(input())
ql = [input().split() for _ in range(q)]

seg = SegTree(s,n)

for i in range(q):
    if ql[i][0]=="1":
        seg.update(int(ql[i][1])-1, ord(ql[i][2])-ord("a"))
    else:
        r = seg.query(int(ql[i][1])-1, int(ql[i][2]))
        print(bin(r).count("1"))
### BUGGY CODE ###

n,C = map(int,input().split())
INF = float("INF")
ch = [[0]*(200001) for _ in range(C)]
m = 0
for _ in range(n):
    s,t,c = map(int,input().split())
    s = s*2-1
    t *= 2
    c -= 1
    ch[c][s] += 1
    ch[c][t] -= 1
    m = max(m,t)

cnt = [0]*(m+1)
for c in range(C):
    for i in range(1,m+1):
        ch[c][i] += ch[c][i-1]
        if ch[c][i-1] == 0 and ch[c][i] > 0: cnt[i] += 1
        if ch[c][i-1] > 0 and ch[c][i] == 0: cnt[i] -= 1

for i in range(1,m+1): cnt[i] += cnt[i-1]
print(max(cnt))

### FIXED CODE ###

n,C = map(int,input().split())
INF = float("INF")
ch = [[0]*(200001) for _ in range(C)]
m = 0
for _ in range(n):
    s,t,c = map(int,input().split())
    s = s*2-1
    t *= 2
    c -= 1
    ch[c][s] += 1
    ch[c][t] -= 1
    m = max(m,t)

cnt = [0]*(m+1)
for c in range(C):
    for i in range(1,m+1):
        ch[c][i] += ch[c][i-1]
        if ch[c][i-1] == 0 and ch[c][i] > 0: cnt[i] += 1
        if ch[c][i-1] > 0 and ch[c][i] == 0: cnt[i] -= 1

for i in range(1,m+1): cnt[i] += cnt[i-1]
print(max(cnt))
### BUGGY CODE ###

N = int(input())

for n in range(1, 3501):
    for w in range(1, 3501):
        t = 4 * n * w - N * w - N * n
        if t > 0:
            h = N * n * w / t
            if h.is_integer() and h > 0:
                print(int(h), n, w)
                exit()


### FIXED CODE ###

N = int(input())

for n in range(1, 3501):
    for w in range(n, 3501):
        t = 4 * n * w - N * w - N * n
        if t > 0:
            h = N * n * w / t
            if h.is_integer() and h > 0:
                print(int(h), n, w)
                exit()
### BUGGY CODE ###

# coding: utf-8
import itertools
import sys
sys.setrecursionlimit(100000)
input=lambda : sys.stdin.readline().rstrip('\n')

n=int(input())
d=[0]+list(itertools.accumulate(map(int,input().split())))
memo={}
def split_slime(l,r):
    if l+1==r:
        return 0
    if (l,r) in memo:
        return memo[(l,r)]
    mn=10**18
    for i in range(l+1,r):
        cost=(d[i]-d[l])+(d[r]-d[i])+split_slime(l,i)+split_slime(i,r)
        if mn>cost:
            mn=cost
    memo[(l,r)]=mn
    return memo[(l,r)]
print(split_slime(0,n))

### FIXED CODE ###

# coding: utf-8
import itertools
import sys
sys.setrecursionlimit(100000)
input=lambda : sys.stdin.readline().rstrip('\n')

n=int(input())
d=[0]+list(itertools.accumulate(map(int,input().split())))
memo=[[-1 for i in range(401)]for i in range(401)]
def split_slime(l,r):
    if l+1==r:
        return 0
    if memo[l][r]!=-1:
        return memo[l][r]
    mn=10**18
    for i in range(l+1,r):
        cost=(d[i]-d[l])+(d[r]-d[i])+split_slime(l,i)+split_slime(i,r)
        if mn>cost:
            mn=cost
    memo[l][r]=mn
    return memo[l][r]
print(split_slime(0,n))
### BUGGY CODE ###

import collections

n = int(input())
que = collections.deque()

for i in range(n):
    lineArr = input().split()
    ope = lineArr[0]

    if ope == 'insert':
        num = int(lineArr[1])
        que.appendleft(num)
    elif ope == 'delete':
        num = int(lineArr[1])
        try:
            que.remove(num)
        except ValueError:
            pass
    elif ope == 'deleteFirst':
        que.popleft()
    else:
        que.pop()

print(*que)



### FIXED CODE ###

import collections

n = int(input())
que = collections.deque()

for i in range(n):
    line = input()

    if line[0] == 'i':
        que.appendleft(int(line[7:]))
    elif line[6] == ' ':
        try:
            que.remove(int(line[7:]))
        except ValueError:
            pass
    elif line[6] == 'F':
        que.popleft()
    else:
        que.pop()

print(*que)
### BUGGY CODE ###

import numpy as np


def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x) - 1, input().split()))


def cumulative_sum_ref(d1_array):
    for i in range(1, len(d1_array)):
        d1_array[i] += d1_array[i-1]


def cumulative_sum_val(d1_array):
    tmp = d1_array.copy()
    for i in range(1, len(tmp)):
        tmp[i] += tmp[i-1]
    return tmp


# 累積和の計算方法が遅すぎるっぽい。
if __name__ != "__main__":
    N, M, Q = LI()
    LR = np.zeros((N+1, N+1), dtype='uint32')
    for i in range(M):
        l, r = LI()
        LR[l][r] += 1

    # 二次元累積和
    for i in range(1, N+1):
        for j in range(2, N+1):
            LR[i][j] += LR[i][j-1]
    for i in range(1, N+1):
        for j in range(2, N+1):
            LR[j][i] += LR[j-1][i]

    for _ in range(Q):
        p, q = LI()
        p -= 1
        result = LR[q][q] - LR[p][q] - LR[q][p] + LR[p][p]
        print(result)


if __name__ == "__main__":
    N, M, Q = LI()
    LR = np.zeros((N+1, N+1), dtype='uint32')
    for i in range(M):
        l, r = LI()
        LR[l][r] += 1

    # 二次元累積和
    for i in range(1, N+1):
        for j in range(1, N+1):
            LR[i][j] += LR[i][j-1]
            LR[i][j] += LR[i-1][j]
            LR[i][j] -= LR[i-1][j-1]

    for _ in range(Q):
        p, q = LI()
        p -= 1
        result = LR[q][q] - LR[p][q] - LR[q][p] + LR[p][p]
        print(result)


### FIXED CODE ###

def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x) - 1, input().split()))


if __name__ == "__main__":
    N, M, Q = LI()
    LR = [[0]*(N+1) for _ in range(N+1)]
    for i in range(M):
        l, r = LI()
        LR[l][r] += 1

    # 二次元累積和
    for i in range(1, N+1):
        for j in range(1, N+1):
            LR[i][j] += LR[i][j-1]
            LR[i][j] += LR[i-1][j]
            LR[i][j] -= LR[i-1][j-1]

    for _ in range(Q):
        p, q = LI()
        p -= 1
        result = LR[q][q] - LR[p][q] - LR[q][p] + LR[p][p]
        print(result)
### BUGGY CODE ###

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

n = int(input())
s = [list(input().split()[0]) for _ in range(n)]
cnt = defaultdict(int)
for i in range(n):
  s[i].sort()
  cnt["".join(s[i])] += 1
result = 0
for c in cnt:
  result += len(list(combinations([""] * cnt[c], 2)))
print(result)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = ["".join(sorted(input().split()[0])) for _ in range(n)]
cnt = {}
result = 0
for si in s:
    if si in cnt:
        result += cnt[si]
        cnt[si] += 1
    else:
        cnt[si] = 1
print(result)
### BUGGY CODE ###

import sys
N, M = map(int, sys.stdin.readline().split())
LR = [list(map(int,sys.stdin.readline().split())) for i in range(M)]
B = list(range(0, 10 ** 5 + 1))
for i in LR:
	A = list(range(i[0], i[1] + 1))
	B = set(A) & set(B)
print(len(B))

### FIXED CODE ###

import sys
N, M = map(int, sys.stdin.readline().split())
LR = sorted([list(map(int,sys.stdin.readline().split())) for i in range(M)])
L = 1
R = 10 ** 5
for i in LR:
    L = max(L, i[0])
    R = min(R, i[1])
if R - L >= 0:
    print(R - L + 1)
else:
    print(0)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

def main():
    n = int(input().rstrip())
    a = list(map(int, input().rstrip().split()))
    count = 0
    b = []
    for i in range(n):
      flag = True
      if not a[i] in b:
        for x in b:
          if a[i] % x == 0:
            flag = False
        if flag:
          for k in range(n):
            if i != k and a[i] % a[k] == 0:
              flag = False
              break
        if flag:
          count += 1
          b.append(a[i])
    print(count)
  
if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import Counter
import sys
n=int(input())
a=sorted(list(map(int,input().split())))
 
c=[1 for i in range(10**6+1)]
d = Counter(a)
s = list(set(a))
count = 0
if d[1] == 1:
  print(1)
  sys.exit()
elif d[1] >=2:
  print(0)
  sys.exit()
for x in s:
  t = x * 2
  while t <= 10 ** 6:
    c[t] = 0
    t += x
 
for x in a:
  if d[x] == 1 and c[x] == 1:
    count += 1
print(count)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
for j in range(m):
  a[0] //= 2
  a.sort(reverse=True)
print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort(reverse=True)

if n > 1:
    a.append(0)
    biggest = a[0]
    now = 0
    while m > 0:
        a[now] = a[now]//2
        m -= 1
        biggest = a[0]
        for i in range(n-1):
            if a[i+1] >= biggest and m > 0:
                a[i+1] = a[i+1]//2
                m -= 1
            else:
                a.sort(reverse=True)
                break
    else:
        quit

else:
  for j in range(m):
    a[0] //= 2

print(sum(a))
### BUGGY CODE ###

import math
n = int(input())
num = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            num += math.gcd(i, math.gcd(j,k))
print(num)

### FIXED CODE ###

import math
n = int(input())
num = 0
tmp = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        tmp = math.gcd(i,j) 
        for k in range(1,n+1):
            num += math.gcd(tmp, k)
            tmp == 0
print(num)
### BUGGY CODE ###

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

ai = []
aj = []
ans = 0

for i in range(n):
    ai.append(i + l[i])

for j in range(n):
    aj.append(j - l[j])

ai.sort()
aj.sort()

s = min(ai)
e = max(aj)

# print(ai)
# print(aj)
# print(s)
# print(e)

for x in range(n):
    ans = ans + aj.count(ai[x])
    if x >= e+1:
        break
    
print(ans)

### FIXED CODE ###

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

a=[]
b={}
ans=0

for i in range(n):
    a.append(i+l[i])
    b[i-l[i]] = b.get(i-l[i],0) + 1

for av in a:
    ans = ans + b.get(av,0)

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

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    s = S()

    m = {}
    m[0] = 0
    def f(i):
        if i in m:
            return m[i]

        c = 0
        ii = i
        while ii > 0:
            c += ii % 2
            ii //= 2

        t = i % c
        m[i] = f(t) + 1
        return m[i]

    c = len([_ for _ in s if _ == '1'])
    r = []
    for i in range(n):
        if s[i] == '1':
            r.append(f(int("".join(s[:i] + '0' + s[i+1:]), 2)))
        else:
            r.append(f(int("".join(s[:i] + '1' + s[i+1:]), 2)))

    return JA(r, "\n")


print(main())




### FIXED CODE ###

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    s = S()

    m = {}
    m[0] = 0
    def f(i):
        if i in m:
            return m[i]

        c = 0
        ii = i
        while ii > 0:
            c += ii % 2
            ii //= 2

        t = i % c
        m[i] = f(t) + 1
        return m[i]

    c = len([_ for _ in s if _ == '1'])
    t = int(s, 2)
    cm = (c+1) * c * (c-1)
    if c > 1:
        t %= cm

    r = []
    k = 1
    for i in range(n-1,-1,-1):
        if t == k:
            r.append(0)
        elif s[i] == '1':
            r.append(f((t - k) % (c-1)) + 1)
        else:
            r.append(f((t + k) % (c+1)) + 1)
        k *= 2
        if c > 1:
            k %= cm

    return JA(r[::-1], "\n")


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

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

counter = 0
for i in range(1, N):
  for j in range(N-1):
    if A[j] == i:
      counter += 1
  print(counter)
  counter = 0
print(0)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

l = Counter(A)
for i in range(1, N+1):
  print(l[i])