Harryxun/stf_run huggingface dataset:
import numpy as np
N = int(input())
a = np.array([int(input()) for _ in range(N)])
m = 998244353
S = a.sum()

# 最初のt個の整数を塗り分け, Rの整数の和がrであるような場合の数
DP_A = np.zeros((N+1, S+1), dtype=np.int64)
# 最初のt個の整数を塗り分け, Rの整数の和がrで, Bの和が0であるような場合の数
DP_B = np.zeros((N+1, S+1), dtype=np.int64)

DP_A[0, 0] = 1
DP_B[0, 0] = 1

for t in range(N):
    for r in range(S + 1):
        # t + 1番目の整数をRにしない -> G or Bにする
        DP_A[t+1, r] = DP_A[t, r] * 2 % m
        # t + 1番目の整数をRにする -> r-a(t+1)だった場合の数を追加
        if r - a[t] >= 0:
            DP_A[t+1, r] += DP_A[t, r - a[t]] % m
        # t+1 番目の整数をRにしない -> Gを加える
        DP_B[t+1, r] = DP_B[t, r] % m
        # t + 1番目の整数をRにする -> r-a(t+1)だった場合の数を追加
        if r - a[t] >= 0:
            DP_B[t+1, r] += DP_B[t, r - a[t]] % m


res1 = DP_A[N, int(np.ceil(S/2)):].sum()
res2 = DP_B[N, int(np.ceil(S/2))] if S % 2 == 0 else 0
res = (3 ** N - res1 * 3 + res2 * 3) % m
print(res)

### FIXED CODE ###

import numpy as np
N = int(input())
a = np.array([int(input()) for _ in range(N)])
m = 998244353
S = a.sum()

# 最初のt個の整数を塗り分け, Rの整数の和がrであるような場合の数
DP_A = np.zeros((N+1, S+1), dtype=np.int64)
# 最初のt個の整数を塗り分け, Rの整数の和がrで, Bの和が0であるような場合の数
DP_B = np.zeros((N+1, S+1), dtype=np.int64)

DP_A[0, 0] = 1
DP_B[0, 0] = 1

# for t in range(N):
#     for r in range(S + 1):
#         # t + 1番目の整数をRにしない -> G or Bにする
#         DP_A[t+1, r] = DP_A[t, r] * 2 % m
#         # t + 1番目の整数をRにする -> r-a(t+1)だった場合の数を追加
#         if r - a[t] >= 0:
#             DP_A[t+1, r] += DP_A[t, r - a[t]] % m
#         # t+1 番目の整数をRにしない -> Gを加える
#         DP_B[t+1, r] = DP_B[t, r] % m
#         # t + 1番目の整数をRにする -> r-a(t+1)だった場合の数を追加
#         if r - a[t] >= 0:
#             DP_B[t+1, r] += DP_B[t, r - a[t]] % m

for t in range(N):
    DP_A[t+1, :] = (DP_A[t, :]) * 2 % m
    DP_A[t+1, a[t]:] += DP_A[t, :-a[t]] % m
    DP_B[t+1, :] = (DP_B[t, :]) % m
    DP_B[t+1, a[t]:] += DP_B[t, :-a[t]] % m

res1 = DP_A[N, int(np.ceil(S/2)):].sum()
res2 = DP_B[N, int(np.ceil(S/2))] if S % 2 == 0 else 0
res = (3 ** N - res1 * 3 + res2 * 3) % m
print(res)
import numpy as np
# -*- coding: utf-8 -*-
A, B, C, K = map(int, input().split())
bef_X = np.array([A, B, C])
aft_X = np.linalg.matrix_power(W, K) @ bef_X

ans = aft_X[0] - aft_X[1]

print("{0}".format(ans if ans <= 10**18 else 'unfair'))

### FIXED CODE ###

import numpy as np
# -*- coding: utf-8 -*-
A, B, C, K = map(int, input().split())
W = np.array([[0,1,1], [1,0,1], [1,1,0]])
bef_X = np.array([A, B, C])
aft_X = np.dot(np.linalg.matrix_power(W, K),  bef_X)

ans = aft_X[0] - aft_X[1]

print("{0}".format(ans if ans <= 10**18 else 'unfair'))
H,N=map(int,input().split())
A=[input() for i in range(N)]
B=[]
for i in range(N):
  a=int(A[i])
  B.append(a)
if sum(B)>=H:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

H,N=map(int,input().split())
A=input().split()
B=[]
for i in range(N):
  a=int(A[i])
  B.append(a)
if sum(B)>=H:
  print("Yes")
else:
  print("No")
def main():
    r, c, k = map(int, input().split())
    d = [[0]*c for _ in [0]*r]
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[t1-1][t2-1] = t3
    dp = [[0]*4 for _ in [0]*c]
    dp[0][1] = d[0][0]
    for x in range(r-1):
        d2 = d[x]
        dp2 = [[0]*4 for _ in [0]*c]
        for y in range(c-1):
            d3 = d2[y+1]
            dp3 = dp[y+1]
            dp4 = dp[y]
            for z in range(3):
                dp3[z+1] = max(dp3[z+1], dp4[z]+d3)
            for z in range(4):
                dp3[z] = max(dp3[z], dp4[z])
        d2 = d[x+1]
        for y in range(c):
            dp3 = dp2[y]
            M = max(dp[y])
            dp3[1] = max(dp3[1], M+d2[y])
            dp3[0] = max(dp3[0], M)
        dp = dp2
    for y in range(c-1):
        d3 = d2[y+1]
        dp2 = dp[y+1]
        dp3 = dp[y]
        for z in range(3):
            dp2[z+1] = max(dp2[z+1], dp3[z]+d3)
        for z in range(4):
            dp2[z] = max(dp2[z], dp3[z])
    print(max(dp[c-1]))


main()


### FIXED CODE ###

def main():
    r, c, k = map(int, input().split())
    d = [[0]*c for _ in [0]*r]
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[t1-1][t2-1] = t3
    dp = [[0]*4 for _ in [0]*c]
    dp[0][1] = d[0][0]
    for x in range(r):
        dp2 = [[0]*4 for _ in [0]*c]
        for y in range(c):
            for z in range(4):
                if y != c-1:
                    if z != 3:
                        dp[y+1][z+1] = max(dp[y+1]
                                           [z+1], dp[y][z]+d[x][y+1])
                    dp[y+1][z] = max(dp[y+1][z], dp[y][z])
            if x != r-1:
                dp2[y][1] = max(dp2[y][1],
                                max(dp[y])+d[x+1][y])
                dp2[y][0] = max(dp2[y][0], max(dp[y]))
        if x != r-1:
            dp = dp2
    print(max(dp[c-1]))


main()
import math
        n,a,b=map(int,input().split(""))
        kouho=[]
        for i in range(0,n+1)
        	i=str(i)
        	keta=list(map(int,i))
        	wa=sum(keta)
            if a<=wa<=b:
              kouho.append(int(i))
        print(sum(kouho))
         

### FIXED CODE ###

n,a,b=map(int,input().split(" "))
kouho=[]
for i in range(1,n+1):
  i=str(i)
  keta=list(map(int,i))
  wa=sum(keta)
  if a<=wa<=b:
    kouho.append(int(i))
print(sum(kouho))
import bisect


def bisect_search(f, val=0, l=0, r=10**6):

    #is_increase=(f(r)-f(l))>=0

    eps = 10**(-5)
    while True:

        c = (l+r)//2
        print(l, c, r)
        input()
        if f(c) == val and f(c-1) != val:
            return c
        #if f(c)-val < eps:
        #    return c

        if f(c) > val:
            r = c

        else:
            l = c

        if l == r:
            return False



def next(ch,k):
    global N,dcs
    k_=k%N
    #print(ch,ch_,k)
    #print(dcs[ch][ch_]+1)
    #print(dcs[ch])
    #print(dcs[ch][ch_]+1)
    #print(N)
    val = dcs[ch][k_-1]+1
    if k_==0:
        val=1

    A=bisect.bisect_left(dcs[ch],val,k_,k_+N)
    B = N*((k//N))
    #print(A,B,k//N,k,N)

    return A+B#+A//N


import numpy as np

s=input()
t=input()

td=list(set(t))

N=len(s)
d={}

import sys

R = set(list(s))
L = set(list(t))

if not(L <= R):
    print(-1)
    sys.exit(2)

for std in td:
    d[std] =[0]*(2*N)



for i in range(len(s)*2):
    #nd[s[i]]

    for std in td:            
        if s[i%N]==std:
            d[std][i]=1



dcs={}
for std in td:
    dcs[std]=np.cumsum(d[std])


last=-1
for ts in t:
    #print(last)
    last=next(ts,last+1)


print(last+1)


#print(dcs)


### FIXED CODE ###

import bisect


def bisect_search(f, val=0, l=0, r=10**6):

    #is_increase=(f(r)-f(l))>=0

    eps = 10**(-5)
    while True:

        c = (l+r)//2
        print(l, c, r)
        input()
        if f(c) == val and f(c-1) != val:
            return c
        #if f(c)-val < eps:
        #    return c

        if f(c) > val:
            r = c

        else:
            l = c

        if l == r:
            return False



def next(ch,k):
    global N,dcs
    k_=k%N
    #print(ch,ch_,k)
    #print(dcs[ch][ch_]+1)
    #print(dcs[ch])
    #print(dcs[ch][ch_]+1)
    #print(N)
    val = dcs[ch][k_-1]+1
    if k_==0:
        val=1

    A=bisect.bisect_left(dcs[ch],val,k_,min(k_+N,2*N-1))
    B = N*((k//N))
    #print(A,B,k//N,k,N)

    return A+B#+A//N


import numpy as np

s=input()
t=input()

td=list(set(t))

N=len(s)
d={}

import sys

R = set(list(s))
L = set(list(t))

if not(L <= R):
    print(-1)
    sys.exit()

for std in td:
    d[std] =[0]*(2*N)



for i in range(len(s)*2):
    #nd[s[i]]

    for std in td:            
        if s[i%N]==std:
            d[std][i]=1



dcs={}
for std in td:
    dcs[std]=np.cumsum(d[std])


last=-1
for ts in t:
    #print(last)
    last=next(ts,last+1)


print(last+1)


#print(dcs)
# vim: fileencoding=utf-8


def main():
    N = int(input())
    for n in range(1, N + 1):
        ans = 0
        if n <= 5:
            print(ans)
            continue

        zMax = int((N + 1) / 6) + 1
        print(f"{n}")
        for x in range(1, int((N + 1) / 6) + 1):
            tx = x ** 2
            if tx + x + 3 >= n or x >= zMax:
                break
            for y in range(x, int((N + 1) / 6) + 1):
                ty = tx + y ** 2 + x * y
                if ty + y + x + 1 >= n or y >= zMax:
                    break
                for z in range(y, int((N + 1) / 6) + 1):
                    print(f"x :{x} y :{y} z :{z}")
                    t = ty + z ** 2 + y * z + z * x
                    if t == n:
                        print(f"ans x :{x} y :{y} z :{z}")
                        if x == y and x == z:
                            ans += 1
                        elif x == y or y == z:
                            ans += 3
                        else:
                            ans += 6
                        if z <= zMax:
                            zMax = z
                        break
                    if t >= n:
                        break
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# vim: fileencoding=utf-8


def main():
    N = int(input())
    ans = [0] * N
    for x in range(1, 101):
        for y in range(1, 101):
            for z in range(1, 101):
                t = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x - 1
                if t >= len(ans):
                    break
                ans[t] += 1

    print(*ans)


if __name__ == "__main__":
    main()
A,B=map(int,input())
if A+B>=10:
  print("error")
else :
  print(A+B)

### FIXED CODE ###

A,B=map(int,input().split())
if A+B>=10:
  print("error")
else :
  print(A+B)
import bisect

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

cnt = 1
while cnt <= M:
    x = bisect.bisect(A, A[-1]/2)
    for i in range(x + 1):
        A[-i -1] /= 2
        cnt += 1
        if cnt > M:
            break

print(sum(map(int, A)))

### FIXED CODE ###

import bisect

N, M = list(map(int, input().split()))
A = list(map(lambda x: int(x) * -1, input().split()))
A.sort()

cnt = 1
while cnt <= M:
    x = bisect.bisect(A, A[0]/2)
    for i in range(x):
        A[i] /= 2
        cnt += 1
        if cnt > M:
            break
    if x != 0 or x != len(A):
        A.sort()
print(sum(map(lambda x: int(-x), A)))
a = input()
print("Yes" if a == a.reverse() else "No")

### FIXED CODE ###

a = input()
print("Yes" if a == a[::-1] else "No")
S = input()
bad = 0
for num in range(2):
  if S[num] == S[num + 1]:
    print("Bad")
    break
    bad = 1
if bad == 0:
  print(Good)

### FIXED CODE ###

S = input()
judge = "Good"
for num in range(3):
  if int(S[num]) == int(S[num + 1]):
    judge = "Bad"
    break
print(judge)
import bisect

n = int(input())
a = sorted(list(map(int, input().split())))
i = bisect.bisect_left(a,0)
if i % 2 == 0:
    ans = abs(sum(a[:i]))+sum(a[i:])
else:
    if i == n:
        ans = abs(sum(a[:i])+a[i])
    else:
        ans = abs(sum(a[:i-1]))+abs(a[i]+a[i-1])+sum(a[i+1:])
print(ans)


### FIXED CODE ###

import bisect

n = int(input())
a = sorted(list(map(int, input().split())))
i = bisect.bisect_left(a,0)
if i % 2 == 0:
    ans = abs(sum(a[:i]))+sum(a[i:])
else:
    if i == n:
        ans = abs(sum(a[:i-1]))+a[i-1]
    else:
        ans = abs(sum(a[:i-1]))+abs(a[i]+a[i-1])+sum(a[i+1:])
print(ans)
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

dish_list = [a, b, c, d, e]
min_val = 100
for i, x in enumerate(dish_list):
    if x%10 == 0:
        continue
    val = x % 10
    if val < min_val:
        min_val = val
        idx = i

ans = 0
for i, dish in enumerate(dish_list):
    if i == idx:
        continue

    wait_order =  10 - dish_list[i]%10 if dish_list[i]%10 != 0 else 0

    ans += dish_list[i] + wait_order

print(ans + dish_list[idx])

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

dish_list = [a, b, c, d, e]
min_val = 100
idx = 0
for i, x in enumerate(dish_list):
    if x%10 == 0:
        continue
    val = x % 10
    if val < min_val:
        min_val = val
        idx = i

ans = 0
for i, dish in enumerate(dish_list):
    if i == idx:
        continue

    wait_order =  10 - dish_list[i]%10 if dish_list[i]%10 != 0 else 0

    ans += dish_list[i] + wait_order

print(ans + dish_list[idx])
n = int(input())
x＝list(map(int, input().split()))
for i in range(n):
  if x[i]>x[i+1]:
    x[i]==x[i]-1
for j in range(n):
  if x[j]>x[j+1]:
    print("No")
    exit()
print("Yes")

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
m = 0
for i in range(n):
  m = max(m,a[i])
  if a[i] < m-1:
    print("No")
    exit()
print("Yes")
n = input()
x = list(map(int,input().split()))
count = 0
for i in range(1,n):
  if all(x[j]>x[i]) for for j in range(0,i-1):
    count+=1
print(count)

### FIXED CODE ###

n = int(input())
x = list(map(int,input().split()))
count = 1
m = x[0]

for i in range(1,n):
  if m >=x[i]:
    count+=1
    m = x[i]
  
print(count)
N = int(input())
K = int(input())
l = []
for k in range(K):
    a = int(input())
    for i in range(a):
        l.append(int(input()))
print(l)
for j in range(N):
    if not j+1 in l:
        print(j+1)

### FIXED CODE ###

N,K=map(int,input().split())
l = []
for k in range(K):
    a = int(input())
    lis=list(map(int,input().split()))
    l.extend(lis)
c=0
for j in range(N):
    if not j+1 in l:
        c+=1
print(c)
N = input()
Nint = int(input())
fN = 0

for i in range(len(N)):
    fN += int(N[i])

if Nint % fN == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = input()
Nint = int(N)
fN = 0

for i in range(len(N)):
    fN += int(N[i])

if Nint % fN == 0:
    print("Yes")
else:
    print("No")
s=input()
t=input()
s_array=[]
t_array=[]
for i in range(len(s)):
  s_array.append(s[i])
for i in range(len(t)):
  t_array.append(t[i])

s_array=sorted(s_array)

t_array=sorted(t_array,reverse=True)
for i in range(min([len(s_array),len(t_array)])):
  if s_array[i]<t_array[i]:
    print('Yes')
    exit()
  elif s_array[i]>t_array[i]:
    print('No')
    exit()
if len(s_array)<len(t_array):
  print('Yes')
  exit()
print('No')

### FIXED CODE ###

a,b=map(int, input().split())
if (a+b)/2>(a+b)//2:
  print((a+b)//2+1)
elif (a+b)/2==(a+b)//2:
  print((a+b)//2)
S = list(input())
SL = len(S)
L = len(S)
i = 1
while len(S)>=2 and i<len(S):
  if int(S[i]) != int(S[i-1]):
    S.pop(i-1)
    S.pop(i-1)
    i-=1
  else:
    i+=1

print(L-len(S))

### FIXED CODE ###

S = list(input())
SL = len(S)
L = len(S)
i = 1
while len(S)>1 and i<len(S):
  if int(S[i]) != int(S[i-1]):
    S.pop(i-1)
    S.pop(i-1)
    i-=1
  else:
    i+=1
  if i==0:
    i+=1
print(L-len(S))
import math
inp = [input() for i in range(2)]
N = int(inp[0])
A = list(map(int, inp[1].split()))
# B = 0
d = {}
for k in A:
    # a = A.count(k)
    # B += (a - 1) / 2
    if k in d.keys():
        d[i] += 1

# for k in range(N):
#     c = A.count(A[k]) - 1
#     counter = B - c
#     print(int(counter))

p = {}
for k in d.keys():
    cnt = d[k]
    p[k] = cnt * (cnt-1) / 2

total = sum(p.values())

for item in A:
    print(int(total - d[item] + 1))

### FIXED CODE ###

import math
inp = [input() for i in range(2)]
N = int(inp[0])
A = list(map(int, inp[1].split()))
# B = 0
d = {}
for k in A:
    # a = A.count(k)
    # B += (a - 1) / 2
    if k in d.keys():
        d[k] += 1
    else:
        d[k] = 1

# for k in range(N):
#     c = A.count(A[k]) - 1
#     counter = B - c
#     print(int(counter))

p = {}
for k in d.keys():
    cnt = d[k]
    p[k] = cnt * (cnt-1) / 2

total = sum(p.values())

for item in A:
    print(int(total - d[item] + 1))
# coding: utf-8
# Your code here!
N=int(input())
A=[0]+list(map(int,input().split()))+[-1]

org_A=A[1:N]

judge=True
for item in org_A:
    if item!=0:
        judge=False
        break
if judge:
    print(N*(N+1)//2)
    exit()

ans=0

wa10=A[1]
wa2=A[1]
front=1
end=0
count=0
while front!=N or end!=N-1:
    #print(front,end)
    #print(wa10,wa2)
    temp=front-end-1
    if wa10==wa2:
        ans+=temp
        front+=1
        wa10+=A[front]
        wa2^=A[front]

    else:
        end+=1
        count=0
        wa10-=A[end]
        wa2^=A[end]
    #print(ans)
    #print("----------------")
print(ans+N)

### FIXED CODE ###

# coding: utf-8
# Your code here!
N=int(input())
A=[0]+list(map(int,input().split()))+[-1]

"""
org_A=A[1:N]

judge=True
for item in org_A:
    if item!=0:
        judge=False
        break
if judge:
    print(N*(N+1)//2)
    exit()
"""

ans=0

wa10=A[1]
wa2=A[1]
front=1
end=0
count=0
while front!=N+1 or end!=N:
    #print(front,end)
    #print(wa10,wa2)
    temp=front-end-1
    if wa10==wa2 and front!=N+1:
        ans+=temp
        front+=1
        wa10+=A[front]
        wa2^=A[front]

    else:
        end+=1
        count=0
        wa10-=A[end]
        wa2^=A[end]
    #print(ans)
    #print("----------------")
print(ans+N)
import fractions

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

used={}
unused={}

def gcd(x,y):
    if x==-1 or y==-1:
        return max(x,y)
    return fractions.gcd(x,y)

def rec(i,x,f):
    if i+1==N:
        return x
    
    if f==1 and used.get(x,-2)>-2:
        return used[x]
    if f==0 and unused.get(x,-2)>-2:
        return unused[x]
    
    if f==0:
        unused[x]=rec(i+1,gcd(x,A[i+1]),0)
        used[x]=rec(i+1,x,1)
        return max(unused[x],used[x])
    else:
        used[x]=rec(i+1,gcd(x,A[i+1]),1)
        return used[x]


print(rec(-1,-1,0))


### FIXED CODE ###

import fractions

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

L=[0]*(N+1)
R=[0]*(N+1)

def gcd(x,y):
    if x==0 or y==0:
        return max(x,y)
    return fractions.gcd(x,y)

for i in range(N):
    j=N-i

    L[i+1]=gcd(L[i],A[i])
    R[j-1]=gcd(R[j],A[j-1])
ans=0

for i in range(N):
    ans=max(ans,gcd(L[i],R[i+1]))

print(ans)
k , n = (int(x) for x in input().split())
a = [int(i) for i in input().split()]
b = []

for i in range(n-1):
    b.append(a[i+1] - a[i])
    
b.append(a[0] + k -a[n-1])

ans=0

b.sort()

for i in range(len(b)-1):
    ans = b[i] + ans
    
    
print(ans)
        

### FIXED CODE ###

s = input()

if s[2] == s[3]:
    
    if s[4] == s[5]:
        print('Yes')
    else:
        print('No')

else:
    print('No')
def main():
    # input
    N, T = map(int, input().split())
    a, b = [], []
    a0_b = []
    for i in range(N):
        a_in, b_in = map(int, input().split())
        if a_in == 0:
            a0_b.append(b_in)
        else:
            a.append(a_in)
            b.append(b_in)
    L = len(a)

    # sort
    ab_ratio = [a[i] / (b[i] + 1) for i in range(L)]
    key = sorted(range(L), key=lambda x: -ab_ratio[x])
    a = [a[i] for i in key]
    b = [b[i] for i in key]
    a0_b.sort()

    # --- case a >= 1 --- #
    # dp[for i shops][passed j shops] := min time
    # j:29 for T < 10^9
    J_MAX = 29
    dp = [[float('inf') for _ in range(J_MAX)] for _ in range(L + 1)]
    dp[0][0] = 0
    for i in range(L):
        for j in range(J_MAX):
            if j > 0:
                dt = 1 + a[i] * (dp[i][j - 1] + 1) + b[i]
                if dp[i][j - 1] + dt <= T:
                    dp[i + 1][j] = min(dp[i][j], dp[i][j - 1] + dt)
                else:
                    dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = dp[i][j]

    # --- case a = 0 --- #
    ans = 0
    for i in range(J_MAX):
        if dp[N][i] == float('inf'):
            break
        else:
            time_cnt = dp[N][i]
            shop_cnt = i
            for t_b in a0_b:
                if time_cnt + t_b <= T:
                    time_cnt += t_b
                    shop_cnt += 1
            if ans < shop_cnt:
                ans = shop_cnt

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    # input
    N, T = map(int, input().split())
    a, b = [], []
    a0_b = []
    for i in range(N):
        a_in, b_in = map(int, input().split())
        if a_in == 0:
            a0_b.append(b_in)
        else:
            a.append(a_in)
            b.append(b_in)
    L = len(a)

    # sort
    ab_ratio = [a[i] / (b[i] + 1) for i in range(L)]
    key = sorted(range(L), key=lambda x: -ab_ratio[x])
    a = [a[i] for i in key]
    b = [b[i] for i in key]
    a0_b.sort()

    # --- case a >= 1 --- #
    # dp[for i shops][passed j shops] := min time
    # j:29 for T < 10^9
    J_MAX = min(L + 1, 29)
    dp = [[float('inf') for _ in range(J_MAX)] for _ in range(L + 1)]
    dp[0][0] = 0
    for i in range(L):
        for j in range(J_MAX):
            if j > 0:
                dt = 1 + a[i] * (dp[i][j - 1] + 1) + b[i]
                if dp[i][j - 1] + dt <= T:
                    dp[i + 1][j] = min(dp[i][j], dp[i][j - 1] + dt)
                else:
                    dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = dp[i][j]

    # --- case a = 0 --- #
    ans = 0
    for i in range(J_MAX):
        if dp[L][i] == float('inf'):
            break
        else:
            time_cnt = dp[L][i]
            shop_cnt = i
            for t_b in a0_b:
                if time_cnt + 1 + t_b <= T:
                    time_cnt += 1 + t_b
                    shop_cnt += 1
            if ans < shop_cnt:
                ans = shop_cnt

    print(ans)


if __name__ == '__main__':
    main()
def main():
    buf = sys.stdin.buffer
    R,C = map(int,buf.readline().split())
    # \nが含まれるから列要素の数が+1
    black = (np.frombuffer(buf.read(R*(C+1)),dtype='S1') == b'#')
    sharps = np.where(black==True)[0]

    coord_x = np.array([[j for i in range(C)] for j in range(R)])
    coord_y = np.array([[i for i in range(C)] for j in range(R)])

    sharps = sharps[sharps%(C+1)!=C]

    sharps_x = sharps//(C+1)
    sharps_y = sharps%(C+1)
    for i,(one_sharp_x,one_sharp_y) in enumerate(zip(sharps_x,sharps_y)):
        #one_sharp_x = one//(C+1)
        #one_sharp_y = one%(C+1)
        if i == 0:
            result_np = abs(coord_x-one_sharp_x) + abs(coord_y-one_sharp_y)
        else:
            result_np = np.minimum(result_np,abs(coord_x-one_sharp_x) + abs(coord_y-one_sharp_y))

    print(max(result_np.flatten()))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np
import sys
# https://atcoder.jp/contests/agc033/submissions/6021787
buf = sys.stdin.buffer
H,W = map(int,buf.readline().split())
# +1周分だけ
black = np.zeros((H+2,W+2),dtype=np.bool)
# \nがあることに注意
black[1:-1,1:] = (np.frombuffer(buf.read(H*(W+1)),dtype='S1') == b'#').reshape(H,W+1)

INF = 10 ** 4
dist = np.zeros((H,W),dtype=np.int16)
# .のところは０それ以外はINFで初期化
dist[~black[1:-1,1:-1]] = INF
# 右、左、下、上と展開させていく感じ
for n in range(1,H):
    np.minimum(dist[n-1]+1,dist[n],out=dist[n])
for n in range(H-2,-1,-1):
    np.minimum(dist[n+1]+1,dist[n],out=dist[n])
for n in range(1,W):
    np.minimum(dist[:,n-1]+1,dist[:,n],out=dist[:,n])
for n in range(W-2,-1,-1):
    np.minimum(dist[:,n+1]+1,dist[:,n],out=dist[:,n])

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

ans = N
j = 1
s = A[0] + A[1] if N > 0 else A[0]
x = A[0] | A[1] if N > 0 else A[0]
for i, a in enumerate(A):
    x = a
    s = a
    if j == i:
        j += 1
    if j == N:
        break
    for k in range(j-i):
        x = x | A[1 + i + k]
        s += A[1 + i + k]
    while True:
        if j == N:
            break
        if s == x:
            ans += j-i
            j += 1
            if j == N:
                break
            s += A[j]
            x = x | A[j]
        else:
            break

print(ans)


### FIXED CODE ###

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

ans = N
if N == 1:
    print(1)
    sys.exit()
j = 1
s = A[0] + A[1]
x = A[0] ^ A[1]
for i, a in enumerate(A):
    if j == i:
        j += 1
        if j == N:
            break
        x = x ^ A[j]
        s += A[j]

    while True:
        if j == N:
            break
        if s == x:
            ans += j-i
            j += 1
            if j == N:
                break
            s += A[j]
            x = x ^ A[j]
        else:
            s -= a
            x = x ^ a
            break
    if j == N:
        break

print(ans)