Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
N,K = map(int,input().split())
A = [int(input()) for i in range(N)]

class SegTree:
    def __init__(self,arr,func,unit):
        self.func = func
        self.unit = unit
        n = 1
        while n < len(arr):
            n *= 2
        self.n = n
        nodes = [unit]*(2*n-1)
        nodes[n-1:n-1+len(arr)] = arr
        for i in range(n-2,-1,-1):
            nodes[i] = func(nodes[2*i+1],nodes[2*i+2])
        self.nodes = nodes

    def update(self,i,val):
        i += self.n-1
        self.nodes[i] = val
        while i >= 0:
            i = (i - 1) // 2
            self.nodes[i] = self.func(self.nodes[2*i+1], self.nodes[2*i+2])

    def query(self,l,r):
        l += self.n
        r += self.n
        s = self.unit
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(self.nodes[r-1], s)
            if l & 1:
                s = self.func(s, self.nodes[l-1])
                l += 1
            l >>= 1
            r >>= 1
        return s

segt = SegTree([0]*300001, lambda x,y:max(x,y), 0)
for a in A:
    l = max(0,a-K)
    r = min(300001,a+K+1)
    m = segt.query(l,r)
    segt.update(a,m+1)

print(segt.query(0,300001))

Fixed submission:
import sys
input = sys.stdin.readline
N,K = map(int,input().split())
A = [int(input()) for i in range(N)]

class SegTree:
    def __init__(self,arr,func,unit):
        self.func = func
        self.unit = unit
        n = 1
        while n < len(arr):
            n *= 2
        self.n = n
        nodes = [unit]*(2*n-1)
        nodes[n-1:n-1+len(arr)] = arr
        for i in range(n-2,-1,-1):
            nodes[i] = func(nodes[2*i+1],nodes[2*i+2])
        self.nodes = nodes

    def update(self,i,val):
        i += self.n-1
        self.nodes[i] = val
        while i >= 0:
            i = (i - 1) // 2
            self.nodes[i] = self.func(self.nodes[2*i+1], self.nodes[2*i+2])

    def query(self,l,r):
        l += self.n
        r += self.n
        s = self.unit
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(self.nodes[r-1], s)
            if l & 1:
                s = self.func(s, self.nodes[l-1])
                l += 1
            l >>= 1
            r >>= 1
        return s

segt = SegTree([0]*300001, lambda x,y:max(x,y), 0)
for a in A:
    l = max(0,a-K)
    r = min(300001,a+K+1)
    m = segt.query(l,r)
    segt.update(a,m+1)

print(segt.query(0,300001))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
N,K = map(int,input().split())
LR = [tuple(map(int,input().split())) for i in range(K)]
LR.sort()
MOD = 998244353

arr = []
for l,r in LR:
    for i in range(l,r+1):
        arr.append(i)

from functools import lru_cache
@lru_cache(maxsize=10**8)
def rec(n):
    if n==0: return 1
    ret = 0
    for a in arr:
        if n-a < 0: break
        ret += rec(n-a)
        ret %= MOD
    return ret

print(rec(N-1))

Fixed submission:
import sys
input = sys.stdin.readline
N,K = map(int,input().split())
LR = [tuple(map(int,input().split())) for i in range(K)]
MOD = 998244353

dp = [1]
cumdp = [0,1]
for i in range(1,N):
    tmp = 0
    for l,r in LR:
        if i-l+1 <= 0: continue
        tmp += cumdp[i-l+1] - cumdp[max(0,i-r)]
    tmp %= MOD
    dp.append(tmp)
    cumdp.append((cumdp[-1] + tmp) % MOD)
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
H,W = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
sy,sx = sy-1,sx-1
gy,gx = gy-1,gx-1
S = [input() for i in range(H)]

import heapq
INF = float('inf')
dist = [[INF]*W for i in range(H)]
dist[sy][sx] = 0
hq = [(0,sx,sy)]
heapq.heapify(hq)
while hq:
    d,x,y = heapq.heappop(hq)
    for dx in range(-2,3):
        for dy in range(-2,3):
            if dx == dy == 0: continue
            nx,ny = x+dx,y+dy
            if not 0 <= nx < W: continue
            if not 0 <= ny < H: continue
            if S[ny][nx] == '#': continue
            if abs(dx)+abs(dy) <= 1:
                if dist[ny][nx] <= dist[y][x]: continue
                dist[ny][nx] = dist[y][x]
                heapq.heappush(hq, (d,nx,ny))
            else:
                if dist[ny][nx] <= dist[y][x] + 1: continue
                dist[ny][nx] = dist[y][x] + 1
                heapq.heappush(hq, (d+1, nx,ny))
print(-1 if dist[gy][gx]==INF else dist[gy][gx])

Fixed submission:
H,W = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
sy,sx = sy-1,sx-1
gy,gx = gy-1,gx-1
S = [input() for i in range(H)]

import heapq
INF = float('inf')
dist = [[INF]*W for i in range(H)]
dist[sy][sx] = 0
hq = [(0,sx+sy*W)]
heapq.heapify(hq)
while hq:
    d,v = heapq.heappop(hq)
    y,x = divmod(v,W)
    for dx in range(-2,3):
        for dy in range(-2,3):
            if dx == dy == 0: continue
            nx,ny = x+dx,y+dy
            if not 0 <= nx < W: continue
            if not 0 <= ny < H: continue
            if S[ny][nx] == '#': continue
            if abs(dx)+abs(dy) <= 1:
                if dist[ny][nx] <= dist[y][x]: continue
                dist[ny][nx] = dist[y][x]
                heapq.heappush(hq, (d,nx+ny*W))
            else:
                if dist[ny][nx] <= dist[y][x] + 1: continue
                dist[ny][nx] = dist[y][x] + 1
                heapq.heappush(hq, (d+1, nx+ny*W))
print(-1 if dist[gy][gx]==INF else dist[gy][gx])
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
P = list(map(lambda x:int(x)-1,input().split()))
C = list(map(int,input().split()))

ans = -float('inf')
for i in range(N):
    visited = set()
    tmp = 0
    for k in range(K):
        if P[i] in visited: break
        tmp += C[P[i]]
        i = P[i]
        visited.add(i)
        ans = max(ans, tmp)
    if tmp < 0: continue
    l = len(visited)
    rem = K-l
    d,m = divmod(rem,l)
    if m==0 and d > 0:
        m = l
        d -= 1
    tmp *= (d+1)
    for k in range(m):
        tmp += C[P[i]]
        i = P[i]
        ans = max(ans, tmp)

print(ans)

Fixed submission:
N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))

ans = -float('inf')
for i in range(N):
    s = 0
    j = i
    for k in range(K):
        j = P[j]-1
        s += C[j]
        ans = max(ans, s)
        if j==i: break
    d,m = divmod(K, k+1)
    if m==0 and d>1:
        m = k+1
        d -= 1
    s *= d
    ans = max(ans, s)
    for k in range(m):
        j = P[j]-1
        s += C[j]
        ans = max(ans, s)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))

ans = -float('inf')
for i in range(N):
    s = 0
    for k in range(K):
        i = P[i]-1
        s += C[i]
        ans = max(ans, s)
print(ans)

Fixed submission:
N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))

ans = -float('inf')
for i in range(N):
    s = 0
    j = i
    for k in range(K):
        j = P[j]-1
        s += C[j]
        ans = max(ans, s)
        if j==i: break
    d,m = divmod(K, k+1)
    if m==0 and d>1:
        m = k+1
        d -= 1
    s *= d
    ans = max(ans, s)
    for k in range(m):
        j = P[j]-1
        s += C[j]
        ans = max(ans, s)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
R,C,K = map(int,input().split())
RCV = [tuple(map(int,input().split())) for i in range(K)]

goods = [dict() for _ in range(R)]
for r,c,v in RCV:
    r,c = r-1,c-1
    goods[r][c] = v

dp = [[[0]*4 for _ in range(C)] for _ in range(R)]
if 0 in goods[0]:
    dp[0][0][1] = goods[0][0]
for i in range(R):
    for j in range(C):
        if i:
            pre = max(dp[i-1][j])
            dp[i][j][0] = pre
            if j in goods[i]:
                dp[i][j][1] = pre + goods[i][j]
        if j:
            for k in range(4):
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
            if j in goods[i]:
                for k in reversed(range(3)):
                    dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j-1][k] + goods[i][j])

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

Fixed submission:
import sys
input = sys.stdin.readline
R,C,K = map(int,input().split())
RCV = [tuple(map(int,input().split())) for i in range(K)]

goods = [dict() for _ in range(R)]
for r,c,v in RCV:
    r,c = r-1,c-1
    goods[r][c] = v

dp0 = [[0]*4 for _ in range(C)]
dp1 = [[0]*4 for _ in range(C)]
if 0 in goods[0]:
    dp1[0][1] = goods[0][0]
for i in range(R):
    for j in range(C):
        if i:
            pre = max(dp0[j])
            dp1[j][0] = pre
            if j in goods[i]:
                dp1[j][1] = pre + goods[i][j]
        if j:
            for k in range(4):
                dp1[j][k] = max(dp1[j][k], dp1[j-1][k])
            if j in goods[i]:
                for k in reversed(range(3)):
                    dp1[j][k+1] = max(dp1[j][k+1], dp1[j-1][k] + goods[i][j])
    dp0 = dp1
    dp1 = [[0]*4 for _ in range(C)]
print(max(dp0[-1]))
Buggy python submission (verdict: Time Limit Exceeded):
from time import time
start_time = time()
D = int(input())
C = list(map(int,input().split()))
S = [list(map(int,input().split())) for i in range(D)]

INF = float('inf')
DF = 7000
last = [0] * 26
cur_ans = []
nexts = []
for i,s in enumerate(S):
    best_k = -1
    best_score = -INF
    scores = []
    for k,s in enumerate(s):
        score = s
        for j,c in enumerate(C):
            if j==k: continue
            score -= c * (i+1 - last[j])
        if score > best_score:
            best_score = score
            best_k = k
        scores.append((score,k))
    last[best_k] = i+1
    cur_ans.append(best_k + 1)
    for sc,k in scores:
        if k==best_k: continue
        if sc < best_score - DF: continue
        nexts.append((best_score-sc, i,k))
nexts.sort(key=lambda x:x[0])

def evaluate(ans):
    last = [0] * 26
    score = 0
    for i,(s,a) in enumerate(zip(S,ans)):
        score += s[a-1]
        last[a-1] = i+1
        for j,c in enumerate(C):
            score -= c * (i+1 - last[j])
    return score + 10**6

cur_score = evaluate(cur_ans)
selects = [-1] * D
for _,ni,nk in nexts:
    if selects[ni] >= 0: continue
    last = [0] * 26
    ans = []
    for i,s in enumerate(S):
        if selects[i] >= 0:
            last[selects[i]] = i+1
            ans.append(selects[i] + 1)
            continue
        if i==ni:
            last[nk] = i+1
            ans.append(nk + 1)
            continue
        best_k = -1
        best_score = -INF
        for k,s in enumerate(s):
            score = s
            for j,c in enumerate(C):
                if j==k: continue
                score -= c * (i+1 - last[j])
            if score > best_score:
                best_score = score
                best_k = k
        last[best_k] = i+1
        ans.append(best_k + 1)
    sc = evaluate(ans)
    if sc > cur_score:
        cur_score = sc
        cur_ans = ans
        selects[ni] = nk
    if time() - start_time > 1.99:
        break

print(*cur_ans, sep='\n')

Fixed submission:
for i in range(365):
    print(1)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
D = int(input())
C = list(map(int,input().split()))
S = [list(map(int,input().split())) for i in range(D)]
T = [int(input()) for i in range(D)]
M = int(input())
DQ = [tuple(map(int,input().split())) for i in range(M)]

score = 0
lasts = [[0] for i in range(26)]
for i,(s,a) in enumerate(zip(S,T)):
    score += s[a-1]
    lasts[a-1].append(i+1)
for j in range(26):
    lasts[j].append(D+1)

for j,(c,ls) in enumerate(zip(C,lasts)):
    for a,b in zip(ls,ls[1:]):
        score -= c * (b-a)*(b-a-1)//2

from bisect import insort
for d,q in DQ:
    p = T[d-1]
    T[d-1] = q
    score += (S[d-1][q-1] - S[d-1][p-1])
    for a,b in zip(lasts[p-1],lasts[p-1][1:]):
        score += C[p-1] * (b-a)*(b-a-1)//2
    for a,b in zip(lasts[q-1],lasts[q-1][1:]):
        score += C[q-1] * (b-a)*(b-a-1)//2
    i = lasts[p-1].index(d)
    del lasts[p-1][i]
    insort(lasts[q-1], d)
    for a,b in zip(lasts[p-1],lasts[p-1][1:]):
        score -= C[p-1] * (b-a)*(b-a-1)//2
    for a,b in zip(lasts[q-1],lasts[q-1][1:]):
        score -= C[q-1] * (b-a)*(b-a-1)//2
    print(score)

Fixed submission:
import sys
input = sys.stdin.readline
D = int(input())
C = list(map(int,input().split()))
S = [list(map(int,input().split())) for i in range(D)]
T = [int(input()) for i in range(D)]
M = int(input())
DQ = [tuple(map(int,input().split())) for i in range(M)]

score = 0
lasts = [[0] for i in range(26)]
for i,(s,a) in enumerate(zip(S,T)):
    score += s[a-1]
    lasts[a-1].append(i+1)
for j in range(26):
    lasts[j].append(D+1)

for j,(c,ls) in enumerate(zip(C,lasts)):
    for a,b in zip(ls,ls[1:]):
        score -= c * (b-a)*(b-a-1)//2

from bisect import bisect
for d,q in DQ:
    p = T[d-1]
    T[d-1] = q
    score += (S[d-1][q-1] - S[d-1][p-1])
    for a,b in zip(lasts[p-1],lasts[p-1][1:]):
        score += C[p-1] * (b-a)*(b-a-1)//2
    for a,b in zip(lasts[q-1],lasts[q-1][1:]):
        score += C[q-1] * (b-a)*(b-a-1)//2
    i = lasts[p-1].index(d)
    del lasts[p-1][i]
    i = bisect(lasts[q-1], d)
    lasts[q-1].insert(i,d)
    for a,b in zip(lasts[p-1],lasts[p-1][1:]):
        score -= C[p-1] * (b-a)*(b-a-1)//2
    for a,b in zip(lasts[q-1],lasts[q-1][1:]):
        score -= C[q-1] * (b-a)*(b-a-1)//2
    print(score)
Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())
S = input()
L = len(S)
MOD = 10**9+7

MAXN = L+K+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def comb(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

ans = 0
for i in range(K+1):
    ans += comb(L-1+K-i, L-1) * pow(25,K-i,MOD) * pow(26,i,MOD)
    ans %= MOD
print(ans)

Fixed submission:
K = int(input())
S = input()
L = len(S)
MOD = 10**9+7

MAXN = L+K+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def comb(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

ans = 0
for i in range(K+1):
    ans += comb(L-1+K-i, L-1) * pow(25,K-i,MOD) * pow(26,i,MOD)
    ans %= MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
from collections import Counter
ctr = Counter(A)

def is_ok(k):
    ctr[k] -= 1
    d = 1
    while d*d <= k:
        if k%d==0:
            if ctr[d] > 0:
                ctr[k] += 1
                return False
            if ctr[k//d] > 0:
                ctr[k] += 1
                return False
        d += 1
    ctr[k] += 1
    return True

ans = 0
for k,v in ctr.items():
    if v > 1: continue
    if is_ok(k):
        ans += 1
print(ans)

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
from collections import Counter
ctr = Counter(A)
B = [k for k,v in ctr.items() if v == 1]
B.sort()
D = {b:i for i,b in enumerate(B)}

ok = [1] * len(B)
MX = 10**6+1
for k in ctr.keys():
    for n in range(2*k,MX,k):
        if n in D:
            ok[D[n]] = 0
print(sum(ok))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
ans = 1
for a in A:
    ans *= a
print(-1 if ans > 10**18 else ans)

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
if 0 in A:
    print(0)
    exit()
ans = 1
for a in A:
    ans *= a
    if ans > 10**18:
        print(-1)
        exit()
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,S = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse=True)
MOD = 998244353

from collections import defaultdict
dp = defaultdict(lambda: 0)
dp[0] = 1
B = 10000
for a in A:
    for k,v in list(dp.items()):
        if k%B + a > S: continue
        dp[k+a+B] += v

ans = 0
for k,v in dp.items():
    if k%B!=S: continue
    i = k//B
    ans += pow(2,N-i,MOD) * v
print(ans%MOD)

Fixed submission:
N,S = map(int,input().split())
A = list(map(int,input().split()))
MOD = 998244353

dp = [[0]*(S+1) for i in range(N+1)]
dp[0][0] = 1

for i,a in enumerate(A):
    for j in range(S+1):
        dp[i+1][j] += dp[i][j]*2
        dp[i+1][j] %= MOD
        if j+a <= S:
            dp[i+1][j+a] += dp[i][j]
            dp[i+1][j+a] %= MOD
print(dp[-1][-1])

Buggy python submission (verdict: Time Limit Exceeded):
N,S = map(int,input().split())
A = list(map(int,input().split()))
MOD = 998244353

from collections import defaultdict
dp = defaultdict(lambda: 0)
dp[0] = 1
B = 10000
for a in A:
    for k,v in list(dp.items()):
        if k%B + a > S: continue
        dp[k+a+B] += v

ans = 0
for k,v in dp.items():
    if k%B!=S: continue
    i = k//B
    ans += pow(2,N-i,MOD) * v
print(ans%MOD)

Fixed submission:
N,S = map(int,input().split())
A = list(map(int,input().split()))
MOD = 998244353

dp = [[0]*(S+1) for i in range(N+1)]
dp[0][0] = 1

for i,a in enumerate(A):
    for j in range(S+1):
        dp[i+1][j] += dp[i][j]*2
        dp[i+1][j] %= MOD
        if j+a <= S:
            dp[i+1][j+a] += dp[i][j]
            dp[i+1][j+a] %= MOD
print(dp[-1][-1])

Buggy python submission (verdict: Time Limit Exceeded):
N,S = map(int,input().split())
A = list(map(int,input().split()))
MOD = 998244353

from collections import defaultdict
dp = defaultdict(lambda: 0)
dp[(0,0)] = 1
for a in A:
    for (i,j),v in list(dp.items()):
        if j+a > S: continue
        dp[(i+1,j+a)] += v

ans = 0
for (i,j),v in dp.items():
    if j!=S: continue
    ans += pow(2,N-i,MOD) * v
print(ans%MOD)

Fixed submission:
N,S = map(int,input().split())
A = list(map(int,input().split()))
MOD = 998244353

dp = [[0]*(S+1) for i in range(N+1)]
dp[0][0] = 1

for i,a in enumerate(A):
    for j in range(S+1):
        dp[i+1][j] += dp[i][j]*2
        dp[i+1][j] %= MOD
        if j+a <= S:
            dp[i+1][j+a] += dp[i][j]
            dp[i+1][j+a] %= MOD
print(dp[-1][-1])
Buggy python submission (verdict: Runtime Error):
T = input()
ans = ''
for i in range(len(T)):
    if T[i] != '?':
        ans += T[i]
        continue
    if ans += 'D'
print(ans)

Fixed submission:
T = input()
ans = ''
for i in range(len(T)):
    if T[i] != '?':
        ans += T[i]
        continue
    ans += 'D'
print(ans)
Buggy python submission (verdict: Runtime Error):
print('pphbhhphph'.index(int(input())%10)+'on')

Fixed submission:
N = int(input())
n = N%10
if n==3:
    print('bon')
elif n in (0,1,6,8):
    print('pon')
else:
    print('hon')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
B = sorted([(a,i) for i,a in enumerate(A)])

dp = [[0]*(N+1) for _ in range(N+1)]
for i in range(N):
    a,j = B.pop()
    for k in range(i+1):
        dp[k][i-k+1] = max(dp[k][i-k+1], dp[k][i-k] + a * abs(j-(N-1-(i-k))))
        dp[k+1][i-k] = max(dp[k+1][i-k], dp[k][i-k] + a * abs(j-k))

print(max(dp[i][N-i] for i in range(N+1)))

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
B = sorted([(a,i) for i,a in enumerate(A)])

dp = [[0]*(N+1) for _ in range(N+1)]
for i in range(N):
    a,j = B.pop()
    for k in range(i+1):
        dp[k][i-k+1] = max(dp[k][i-k+1], dp[k][i-k] + a * abs(j-(N-1-(i-k))))
        dp[k+1][i-k] = max(dp[k+1][i-k], dp[k][i-k] + a * abs(j-k))

print(max(dp[i][N-i] for i in range(N+1)))
Buggy python submission (verdict: Time Limit Exceeded):
H,W,K = map(int,input().split())
S = [input() for i in range(H)]

ans = H+W
for b in range(1<<(H-1)):
    tmp = bin(b).count('1')
    ks = [0]*H
    for col in zip(*S):
        j = 0
        for i,c in enumerate(col):
            if c=='1':
                ks[j] += 1
            if b&(1<<i):
                j = i+1
        if any(k > K for k in ks):
            tmp += 1
            ks = [0]*H
            j = 0
            for i,c in enumerate(col):
                if c=='1':
                    ks[j] += 1
                if b&(1<<i):
                    j = i+1
    ans = min(ans,tmp)
print(ans)

Fixed submission:
H,W,K = map(int,input().split())
S = [input() for i in range(H)]

ans = H+W
for b in range(1<<(H-1)):
    tmp = bin(b).count('1')
    ks = [0]*H
    valid = True
    for col in zip(*S):
        j = 0
        for i,c in enumerate(col):
            if c=='1':
                ks[j] += 1
            if b&(1<<i):
                j = i+1
        if any(k > K for k in ks):
            tmp += 1
            ks = [0]*H
            j = 0
            for i,c in enumerate(col):
                if c=='1':
                    ks[j] += 1
                if b&(1<<i):
                    j = i+1
            if any(k > K for k in ks):
                valid = False
                break
    if valid:
        ans = min(ans,tmp)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#TLE
K,Q = map(int,input().split())
D = list(map(int,input().split()))
NXM = [tuple(map(int,input().split())) for i in range(Q)]

for N,X,M in NXM:
    ds = [d%M for d in D]
    a,b = divmod(N-1,K)
    s = 0
    z = 0
    for i,d in enumerate(ds):
        if i==b:
            sb = s
            zb = z
        if d==0:
            z += 1
        s += d
    x = (X + s*a + sb)//M - X//M
    y = z*a + zb
    print(N-1-x-y)

Fixed submission:
K,Q = map(int,input().split())
D = list(map(int,input().split()))
NXM = [tuple(map(int,input().split())) for i in range(Q)]

for N,X,M in NXM:
    ds = [d%M for d in D]
    a,b = divmod(N-1,K)
    s = 0
    z = 0
    for i,d in enumerate(ds):
        if i==b:
            sb = s
            zb = z
        if d==0:
            z += 1
        s += d
    x = (X + s*a + sb)//M - X//M
    y = z*a + zb
    print(N-1-x-y)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

def calc(i,n):
    a = A[i]
    if a==0:
        return 0 if n<0 else N-i-1
    if a>0:
        ok = i
        ng = N
        while ng-ok > 1:
            m = (ok+ng)//2
            if m==i or a*A[m]<=n:
                ok = m
            else:
                ng = m
        return ok-i
    else:
        ok = N
        ng = i
        while ok-ng > 1:
            m = (ok+ng)//2
            if m==i or a*A[m]>n:
                ng = m
            else:
                ok = m
        return N-ok

def is_ok(m):
    k = 0
    for i in range(N-1):
        k += calc(i,m)
        if k >= K: return True
    return False

ng = -10**18-1
ok = 10**18+1
while ok-ng > 1:
    m = (ok+ng)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)

Fixed submission:
import sys
input = sys.stdin.readline
from bisect import bisect
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
pos = N - bisect(A,0)
zero = A.count(0)
neg = N - pos - zero

def is_ok(m):
    if m < 0:
        k = 0
        l = 1
        for i in range(neg):
            a = A[i]
            while a*A[l] > m:
                l += 1
                if l==N: break
            k += N-l
            if k >= K: return True
            if l==N: break
        return False
    else:
        k = diag = 0
        r = neg-1
        for i in range(neg):
            a = A[i]
            while a*A[r] <= m:
                r -= 1
                if r==-1: break
            k += r+1
            if r>=i: diag += 1
            if r==-1: break
        nz = neg+zero
        l = nz
        for i in range(N-1,nz-1,-1):
            a = A[i]
            while a*A[l] <= m:
                l += 1
                if l==N: break
            k += N-l
            if l<=i: diag += 1
            if l==N: break
        tmp = N*(N-1)//2 - (k-diag)//2
        return tmp >= K

ng = -10**18-1
ok = 10**18+1
while ok-ng > 1:
    m = (ok+ng)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)