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

N,W = map(int,input().split())
ws, vs = [], []

for i in range(N):
    w,v = map(int,input().split())
    ws.append(w)
    vs.append(v)

# 重さの総和の値を固定して、その値の最大値を求める組み合わせを
# dp[i][sum_wN]とする
dp = [[0 for _ in range(W+1)] for _ in range(N)]

# i番目についてのやつ
ans = 0
for i in range(N):
    for j in range(W+1):
        # あるWについて
        # i番目をknapsacに加える場合
        if j - ws[i] >= 0:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-ws[i]] + vs[i])
        else:
            dp[i][j] = max(dp[i][j],dp[i-1][j])

print(max(dp[-1]))

### FIXED CODE ###


import numpy as np
N,W = map(int, input().split())
# np.maximum https://www.sejuku.net/blog/69175
# 第一引数と第二引数の大小関係を要素ごとに比較して、大きい方を格納した配列を返します。
dp = np.zeros(W+1, dtype=np.int64)
for _ in range(N):
    w,v = map(int,input().split())
    # w以下ならvを足したもの、w以上ならそのままの値で、最大値を求める
    # 出力はw以上の配列として返す(それ以下は重さwなので関与しない)
    # 足す場合が前者、足さない場合が後者。その重さでの最大valueが保存されている
    np.maximum(dp[:W-w+1]+v,dp[w:],out=dp[w:]) 

print(dp[-1])
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
dic = [''.join(sorted(i)) for i in s]
key = [i for i in set(dic)]
cnt = 0
cnt = [str(dic.count(i)-1) for i in key]
ad = [int(int(a) * (int(a)+1)/2) for a in cnt]
print(sum(ad))


### FIXED CODE ###

n = int(input())
s = {}
cnt = 0
for i in range(n):
    j = ''.join(sorted(input()))
    if j in s:
        s[j] += 1
    else:
        s[j] = 0
    cnt += s[j]
print(int(cnt))
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[float("inf")]*n
dp[0]=0
for i in range(1,n):
    for j in range(max(0,i-k),i):
        dp[i]=min(dp[i],dp[j]+abs(h[i]-h[j]))
print(dp[-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[float("inf")]*n
dp[0]=0
for i in range(1,n):
    for j in range(max(0,i-k),i):
        dp[i]=min(dp[i],dp[j]+abs(h[i]-h[j]))
print(dp[-1])
### BUGGY CODE ###

n = int(input())
A = [int(i) for i in input().split()]

tmp = 0
ans = 10 ** 10
for i in range(n - 1):
    tmp += A[i]
    ans = min(ans, abs(tmp -(sum(A) - tmp)))
print(ans)

### FIXED CODE ###

n = int(input())
A = [int(i) for i in input().split()]
sumA = sum(A)

tmp = 0
ans = 10 ** 10
for i in range(n - 1):
    tmp += A[i]
    ans = min(ans, abs(tmp -(sumA - tmp)))
print(ans)
### BUGGY CODE ###

P_Sum = 0
N_Sum = 0
Kazu = 0
while True:
    try:
        pri,num = map(int,input().split(","))
        P_Sum += num * pri
        N_Sum += num
        Kazu += 1
    except EOFError:
        print(P_Sum)
        print(round(N_Sum / Kazu))

### FIXED CODE ###

P_Sum = 0
N_Sum = 0
Kazu = 0
while True:
    try:
        pri,num = map(int,input().split(","))
        P_Sum += num * pri
        N_Sum += num
        Kazu += 1
    except(EOFError,ValueError):
        print(P_Sum)
        print(int((N_Sum / Kazu)+ 0.5))
        break
### BUGGY CODE ###

l, r = map(int, input().split())
if r-l >2019:
	l += 2019
s = 10**9
for i in range(l,r+1):
	for j in range(i+1,r+1):
		s = min(s,i*j%2019)
print (s)


### FIXED CODE ###

l, r = map(int, input().split())
a = 10**5
if r - l >= 2017:
	print (0)
	exit()
else:
	for i in range(l,r+1):
		for j in range(i+1,r+1):
			a = min(a,i*j%2019)
print (a)
### BUGGY CODE ###

n = int(input())
a = [0] * n
for i in range(n):
  a[i] = int(input())

ans = []
for i in range(n):
  count = a.count(a[i])
  if count %2 == 1 and a[i] not in ans :
    ans.append(a[i])

print(len(ans))

### FIXED CODE ###

N = int(input())
A = [0] * N
for i in range(N):
    A[i] = int(input())
A.sort()

#print(A)

check = [0]
for i in range(1, N):
    if A[i] != A[i-1]:
        check.append(i)
check.append(N)

l = []
for i in range(1, len(check)):
    tmp = check[i] - check[i-1]
    l.append(tmp)

#print(l)

ans = 0
for i in range(len(l)):
    if l[i] % 2 == 1:
        ans += 1

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

N, M = map(int, input().split())
X, Y, Z = [0] * M, [0] * M, [0] * M
for i in range(M):
	X[i], Y[i], Z[i] = map(int, input().split())
Groups = [[X[0], Y[0]]]
for i in range(1, M):
	flag= False
	for g in Groups:
		if X[i] in g or Y[i] in g:
			g.append(X[i])
			g.append(Y[i])
			flag = True
	if flag == False:
		Groups.append([X[i], Y[i]])
cnt = 0
for j in range(1, N + 1):
	flag = False
	for g in Groups:
		if j in g:
			flag = True
	if flag == False:
		cnt += 1
print(len(Groups) + cnt)


### FIXED CODE ###

class UnionFind:
	def __init__(self, n):
		self.par = [i for i in range(n)]  # 親
		self.rank = [1] * n  # 深さ
		self.size = [1] * n  # size[i]はiを根とするグループのサイズ

	def find(self, x):  # xの親を返す
		if self.par[x] == x:
			return x
		else:
			return self.find(self.par[x])

	def unite(self, x, y):  # x,yの属する集合をマージする
		x = self.find(x)
		y = self.find(y)
		if x != y:
			if self.rank[x] < self.rank[y]:
				self.par[x] = y
				self.size[y] += self.size[x]
			else:
				self.par[y] = x
				self.size[x] += self.size[y]
				if self.rank[x] == self.rank[y]:
					self.rank[x] += 1

N, M = map(int, input().split())
X, Y, Z = [0] * M, [0] * M, [0] * M
for i in range(M):
	X[i], Y[i], Z[i] = map(int, input().split())

uf = UnionFind(N)

for j in range(M):
	uf.unite(X[j] - 1, Y[j] - 1)

roots = set([])
for k in range(N):
	roots.add(uf.find(k))
print(len(roots))
### BUGGY CODE ###

import heapq
r, c, k = map(int, input().split())
itm = [[0]*(c+1) for _ in range(r+1)]
for i in range(k):
  ri, ci, vi = map(int, input().split())
  itm[ri][ci] = vi
dp = [[[0]*4 for c_ in range(c+1)] for r_ in range(r+1)]
for i in range(1, r+1):
  for j in range(1, c+1):
    nowv = itm[i][j]
    dp[i][j][0] = max(dp[i][j-1][0], max(dp[i-1][j]))
    if nowv == 0:
      dp[i][j][1] = dp[i][j-1][1]
      dp[i][j][2] = dp[i][j-1][2]
      dp[i][j][3] = dp[i][j-1][3]
    else:
      dp[i][j][1] = max(dp[i][j-1][1], dp[i][j][0] + nowv)
      dp[i][j][2] = max(dp[i][j-1][2], dp[i][j-1][1] + nowv)
      dp[i][j][3] = max(dp[i][j-1][3], dp[i][j-1][2] + nowv)
print(max(dp[r][c]))

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

r, c, k = map(int, input().split())
itm = [[0]*(c) for _ in range(r)]
for i in range(k):
    ri, ci, vi = map(int, input().split())
    itm[ri-1][ci-1] = vi

dp0 = [[0]*4 for c_ in range(3005)]
dp1 = [[0]*4 for c_ in range(3005)]

for i in range(r):
    for j in range(c):
        nowv = itm[i][j]
        dp0[j][3] = max(dp0[j][3], dp0[j][2] + nowv)
        dp0[j][2] = max(dp0[j][2], dp0[j][1] + nowv)
        dp0[j][1] = max(dp0[j][1], dp0[j][0] + nowv)

        dp0[j+1][0] = max(dp0[j+1][0], dp0[j][0])
        dp0[j+1][1] = max(dp0[j+1][1], dp0[j][1])
        dp0[j+1][2] = max(dp0[j+1][2], dp0[j][2])
        dp0[j+1][3] = max(dp0[j+1][3], dp0[j][3])

        dp1[j][0] = max(dp1[j][0], max(dp0[j]))
    dp0 = dp1.copy()

print(max(dp1[c-1]))
### BUGGY CODE ###

from math import sqrt
from collections import Counter

def factorize(n):
    rt = int(sqrt(n)+1)
    facts = []
    for i in range(2, rt+1):
        if n % i == 0:
            facts.append(i)
            while n % i == 0:
                n //= i
    if n != 1:
        facts.append(n)
    return facts

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

P = Counter()

for a in A:
    p = Counter(factorize(a))
    P += p

p_max = max(P.values()) if P.values()  else 1
if  p_max == 1:
    print('pairwise coprime')
elif  p_max <  n:
    print('setwise coprime')
else:
    print('not coprime')

### FIXED CODE ###

def arrayF(n): 
    F=[0]*(n+1) 
    i=2 
    while i*i<=n:
        if F[i] == 0: 
            k=i*i
            while k <= n:
                if F[k] == 0:
                    F[k] = i
                k += i
        i += 1 
    return F


def factorization(x, F): 
    primeFactors = []
    while F[x] > 0:
        primeFactors.append(F[x])
        x //= F[x] 
    if x != 1:
        primeFactors.append(x)
    return set(primeFactors)

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

amax = max(A)
F  = arrayF(amax)

P = [0] *  (amax+1)
for a in A:
    for p in factorization(a,  F):
        P[p] += 1
p_max = max(P)
if  p_max <= 1:
    print('pairwise coprime')
elif  p_max <  n:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

from fractions import gcd
from functools import reduce

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


n = int(input())

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

# 最大公倍数
target_num = lcm(*a)

b = []
for i in range(n):
    b.append(target_num//a[i])

print(sum(b) % (10**9+7))


### FIXED CODE ###

from fractions import gcd
from functools import reduce

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


n = int(input())

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

# 最大公倍数
target_num = lcm(*a)

ans = 0
for i in range(n):
    ans += target_num//a[i]
#b = [target_num//num for num in a]

print(ans % (10**9+7))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    lis = list(map(int, input().split()))
    ans = 0

    for i in range(n):
        for j in range(i, n):
            if lis[i] + lis[j] == j - i:
                ans += 1
    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter

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

L = []
R = []
for i, j in enumerate(lis):
    L.append(i+j)
for i, j in enumerate(lis):
    R.append(i-j)
    
ref = dict(Counter(R))
ans = 0
for i in L:
    ans += ref.get(i, 0)
print(ans)
### BUGGY CODE ###


from sys import stdin
import itertools

n = int(stdin.readline().rstrip())
ls = [int(x) for x in stdin.readline().rstrip().split()]

ans = 0
for v in itertools.combinations(ls, 3):
    a=int(v[0])
    b=int(v[1])
    c=int(v[2])
    if a<b+c:
        if b<c+a:
            if c<a+b:
                ans += 1

print(int(ans))


### FIXED CODE ###

from sys import stdin
from collections import defaultdict, deque, Counter
import sys
from bisect import bisect_left
import heapq
import math

sys.setrecursionlimit(1000000000)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

n = int(stdin.readline().rstrip())
l = list(map(int, stdin.readline().rstrip().split()))
#A, B, C = map(int, stdin.readline().rstrip().split())
#S = [list(stdin.buffer.readline().decode().rstrip()) for _ in range(h)]

l.sort()
ans = 0

for i in range(n):
    for j in range(i+1, n):
        t = l[i] + l[j]
        idx = bisect_left(l,t)
        ans += max(0,idx-j-1)

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

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

N = int(input())
s = input()

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

for i in range(2,N+1):
    for j in range(1,N-i+2):
        if s[i-2] == "<":
            for k in range(1,N-i-j+3):
                dp[i][j] = (dp[i][j] + dp[i-1][j+k]) % mod
        else:
            for k in range(1,j+1):
                dp[i][j] = (dp[i][j] + dp[i-1][k]) % mod

print(dp[N][1] % mod)

### FIXED CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

N = int(input())
s = input()

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

for i in range(2,N+1):
    a = [0 for i in range(N-i+3)]
    for k in range(1,N-i+3):
        a[k] = (a[k-1] + dp[i-1][k]) % mod

    for j in range(1,N-i+2):
        if s[i-2] == "<":
            dp[i][j] = (a[N-i+2] - a[j]) % mod
            # for k in range(1,N-i-j+3):
            #     dp[i][j] = (dp[i][j] + dp[i-1][j+k]) % mod
        else:
            dp[i][j] = (a[j] - a[0]) % mod
            # for k in range(1,j+1):
            #     dp[i][j] = (dp[i][j] + dp[i-1][k]) % mod

print(dp[N][1] % mod)
### BUGGY CODE ###

# E - Flatten
# https://atcoder.jp/contests/abc152/tasks/abc152_e

from math import *
from collections import defaultdict

MAX_Ai = 10**6
MAX_PRIME = ceil(sqrt(MAX_Ai))
MODE = 10**9+7

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


def get_prime():
    # prime table
    ptb = [True] * MAX_PRIME
    ptb[0] = ptb[1] = False

    for i in range(2, ceil(sqrt(MAX_PRIME)) + 1):
        for j in range(i*2, MAX_PRIME, i):
            ptb[j] = False

    P = [ i for i, v in enumerate(ptb) if v == True]

    return P

def prime_factorization(n, P):
    factor = defaultdict(int)
    for p in P:
        while n % p == 0:
            factor[p] += 1
            n //= p

    if n != 1:
        factor[n] += 1

    return factor

def main():
    P = get_prime()    

    A_fact = list()
    lcm = defaultdict()
    for a in A:
        a_fact = prime_factorization(a, P)
        A_fact.append(a_fact)
        for prime, power in a_fact.items():
            if prime not in lcm:
                lcm[prime] = power
            else:
                if lcm[prime] < power:
                    lcm[prime] = power

    ret = 0
    for a_fact in A_fact:
        b_fact = {key: lcm[key] - a_fact.get(key, 0) for key in lcm.keys()}
        tmp = 1
        for prime, power in b_fact.items():
            tmp *= prime**power
        ret += tmp

    print(ret%MODE)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import fractions 

N = int(input())
A = list(map(int, input().split()))
MODE = 10**9+7

def lcm(a, b):
    return a*b//fractions.gcd(a,b)

_lcm = 1
for a in A:
    _lcm = lcm(a, _lcm)

ret = 0
for a in A:
    ret += (_lcm // a)

print(ret%MODE)
### BUGGY CODE ###

import math

def comb(n,m):
    return math.factorial(n) // (math.factorial(n-m)*math.factorial(m))

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

a_max = 0

for ai in a:
    a_max = max(a_max, ai)

res_max = -1
m = -1

for ai in a:
    if ai == a_max:
        continue

    c = comb(a_max, ai)

    if c > res_max:
        res_max = c
        m = ai

print(a_max, m)


### FIXED CODE ###

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

a_max = 0

for ai in a:
    a_max = max(a_max, ai)

if a[0] != a_max:
    m = a[0]
else:
    m = a[1]

for ai in a:
    if ai == a_max or ai == m:
        continue

    if ai > m and ai < a_max - m:
        m = ai
    elif ai < m and ai > a_max - m:
        m = ai

print(a_max, m)
### BUGGY CODE ###

n, m = map(int, input().split())
a = []
for i in range(m):
  a.append(int(input()))
# 0: 1, 1: 1, 2: 2(1+1, 2), 3: 3(1+1+1, 1+2, 2+1)
# dp[i] = dp[i-1] + dp[i-2]
dp = [0]*(n+1)
dp[0] = 1
for i in range(n):
  if i not in a:
    dp[i+1] += dp[i]
    dp[i+1] %= 10**9+7
    if i+2 != n+1:
      dp[i+2] += dp[i]
      dp[i+2] %= 10**9+7
print(dp[n])

### FIXED CODE ###

n, m = map(int, input().split())
a = []
for i in range(m):
  a.append(int(input()))
# 0: 1, 1: 1, 2: 2(1+1, 2), 3: 3(1+1+1, 1+2, 2+1)
# dp[i] = dp[i-1] + dp[i-2]
dp = [0]*(n+1)
dp[0] = 1
for i in range(m):
  dp[a[i]] = -1
for i in range(n):
  if dp[i] == -1:
    continue
  if dp[i+1] != -1:
    dp[i+1] += dp[i]
    dp[i+1] %= 10**9+7
  if i+2 != n+1:
    if dp[i+2] != -1:
      dp[i+2] += dp[i]
      dp[i+2] %= 10**9+7
print(dp[n])
### BUGGY CODE ###

mi = lambda: map(int, input().split())
e = enumerate
n,k = mi()
a = list(mi())
g = [None]*n

d = dict()
for i,x in e(a):
  d[x] = i
for i,x in e(a):
  g[d[x]] = ((i+1)%n,int(d[x]>=i)+int(i+1==n))
  d[x] = i
db = [g]
for _ in range(30):
  old = db[-1]
  new = [None]*n
  for i in range(n):
    p,q = old[i]
    r,s = old[p]
    new[i] = (r,q+s)
  db.append(new)
cur = 0
st = 30
cs = 0
while st>=0:
  p,q = db[st][cur]
  if cs+q < k:
    cs += q
    cur = p
  else:
    st -= 1
q = list()
for x in a[cur:]:
  if x in q:
    t = x-1
    while t != x:
      t = q.pop()
  else:
    q.append(x)
print(' '.join(map(str,q)))

### FIXED CODE ###

mi = lambda: map(int, input().split())
e = enumerate
n,k = mi()
m = (n+k).bit_length()
a = list(mi())
g = [None]*n

d = dict()
for i,x in e(a):
  d[x] = i
for i,x in e(a):
  g[d[x]] = ((i+1)%n,int(d[x]>=i)+int(i+1==n))
  d[x] = i
db = [g]
for _ in range(m):
  old = db[-1]
  new = [None]*n
  for i in range(n):
    p,q = old[i]
    r,s = old[p]
    new[i] = (r,q+s)
  db.append(new)
cur = 0
st = m
cs = 0
while st>=0:
  p,q = db[st][cur]
  if cs+q < k:
    cs += q
    cur = p
  else:
    st -= 1
    
q = list()
while cur < n:
  if g[cur][1] == 0:
    cur = g[cur][0]
  elif g[cur] == (0,1):
    break
  else:
    q.append(a[cur])
    cur += 1
  
print(' '.join(map(str,q)))
### BUGGY CODE ###

n, y = map(int, input().split())
flag = False
for a in range(0, n+1):
    for b in range(0, n+1):
        for c in range(0, n+1):
            if(10000*a+5000*b+1000*c==y and a+b+c==n):
                print('{} {} {}'.format(a, b, c))
                flag = True
                break
        else:
            continue
        break
    else:
        continue
    break
    
if not flag:
    print('-1 -1 -1')

### FIXED CODE ###

n, y = map(int, input().split())
flag = False
a = 0
b = 0
c = 0

for a in range(0, n+1):
    for b in range(0, n+1-a):
        c = n - a - b
        if(10000*a+5000*b+1000*c==y):
            print('{} {} {}'.format(a, b, c))
            flag = True
            break
        else:
            continue
        break
    else:
        continue
    break
    
if not flag:
    print('-1 -1 -1')
### BUGGY CODE ###

# F

N = int(input())

list_plus = []
list_minus = []
for i in range(N):
    S = input()
    state = 0
    min_state = 0
    for s in S:
        if s == '(':
            state += 1
        else:
            state -= 1
        min_state = min(min_state, state)
    
    if state > 0:
        list_plus.append([min_state, state])
    else:
        
        list_minus.append([min_state - state, -state])

def compute(arr):
    total_state = 0
    for min_state, state in arr[::-1]:
        if total_state + min_state < 0:
            print('No')
            exit()
        total_state += state
    return total_state

list_plus.sort()
total_state_plus = compute(list_plus)
list_minus.sort()
total_state_minus = compute(list_minus)

print('Yes' if total_state_plus == total_state_minus else 'No')

### FIXED CODE ###

# F

N = int(input())

list_plus = []
list_minus = []
for i in range(N):
    S = input()
    state = 0
    min_state = 0
    for s in S:
        if s == '(':
            state += 1
        else:
            state -= 1
        min_state = min(min_state, state)
    
    if state > 0:
        list_plus.append((min_state, state))
    else:
        list_minus.append((min_state - state, -state))

def compute(arr):
    total_state = 0
    for min_state, state in arr[::-1]:
        if total_state + min_state < 0:
            print('No')
            exit()
        total_state += state
    return total_state

list_plus.sort()
total_state_plus = compute(list_plus)
list_minus.sort()
total_state_minus = compute(list_minus)

print('Yes' if total_state_plus == total_state_minus else 'No')
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))

Colors = []
Colors.append(A[0])

for i in range(1, N):
    if Colors[-1] >= A[i]:
        Colors.append(A[i])
    else:
        j = 0
        while True:
            if Colors[j] < A[i]:
                Colors[j] = A[i]
                break
            j += 1
print(len(Colors))



### FIXED CODE ###

from collections import deque
import bisect
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))

Colors = deque()
Colors.append(A[0])

for i in range(1, N):
    if Colors[0] >= A[i]:
        Colors.appendleft(A[i])
    else:
        idx = bisect.bisect_left(Colors, A[i])
        Colors[idx-1] = A[i]
print(len(Colors))
### BUGGY CODE ###

def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


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

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 0
    tmp = num ^ pow(2, n - (i + 1))
    ctmp = cnt - 2 * int(x[i]) + 1
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)


### FIXED CODE ###

def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


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

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = num % ctmp + pow(2, n - (i + 1), ctmp)
    elif x[i] == '1':
        ctmp = cnt - 1
        if ctmp == 0:
            print(0)
            continue
        tmp = num % ctmp - pow(2, n - (i + 1), ctmp)
    tmp %= ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)
### BUGGY CODE ###

N = int(input()) 
sub = list(map(int,input().split())) 
number = list(range(1, N+1, 1)) 
cnt = 0 
for i in range(int(len(number))):
    for j in range(int(len(sub))):
        if number[i] == sub[j]:
            cnt = cnt + 1
        
    print(cnt)
    cnt = 0

### FIXED CODE ###

N = int(input())
sub = list(map(int, input().split()))
ans = [0]*(N)
for i in sub:
    ans[i-1] += 1
for i in ans:
    print(i)
### BUGGY CODE ###

K = int(input())

import collections as clt
import math
import itertools as itt

v = []
for j in itt.product(range(1,K+1),repeat=3):
	v.append(list(j))
sum = 0

#print(v)

from functools import reduce

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

for j in v:
	sum += gcd_list(j)
print(sum)

### FIXED CODE ###

K = int(input())

import collections as clt
import math
import itertools as itt

sum = 0

#print(v)

from functools import reduce

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

for j in itt.product(range(1,K+1),repeat=3):
	sum += gcd_list(j)
print(sum)
### BUGGY CODE ###

def main():
    _ = input()
    a = sorted(list(map(int, input().split())), reverse=True)
    if a[-1] == 0:
        print(0)
        return
    x = 1
    m = 10 ** 18
    for i in a:
        if i > m:
            print(-1)
            return
        if i < 2:
            continue
        x *= i
    print(-1 if x > 10 ** 18 else x)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    _ = input()
    a = sorted(list(map(int, input().split())), reverse=True)
    if a[-1] == 0:
        print(0)
        return
    x = 1
    m = 10 ** 18
    for i in a:
        if i < 2:
            continue
        x *= i
        if x > m:
            print(-1)
            return
    print(-1 if x > 10 ** 18 else x)


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

def is_ok(arg):
    if tmp - l[arg] < 0:
        return True
    return False

def meguru_binary_search(ng, ok):
    while abs(ng - ok) > 1:
        mid = (ng + ok) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

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

l.sort(reverse=True)
l += [0]

ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        tmp = l[i] - l[j]
        c = meguru_binary_search(n, j)
        if c == j:
            break
        ans += c-j

print(ans)


### FIXED CODE ###

from bisect import bisect_left

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

l.sort()

ans = 0

for i in range(n):
    for j in range(i+1, n):
        tmp = bisect_left(l, l[i]+l[j]) - 1
        ans += tmp - j

print(ans)