Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
H,W=map(int,input().split())
S=[[1 if c=='#' else 0 for c in input()] for i in range(H)]
from collections import deque
r=0
for i in range(H):
    for j in range(W):
        if S[i][j]==1:
            continue
        d=[[-1]*W for x in range(H)]
        q=deque([(i,j,0)])
        d[i][j]=0
        while q:
            x,y,d0=q.popleft()
            if x>0 and S[x-1][y]==0 and d[x-1][y]==-1:
                q.append((x-1,y,d0+1))
                d[x-1][y]=d0+1
            if y>0 and S[x][y-1]==0 and d[x][y-1]==-1:
                q.append((x,y-1,d0+1))
                d[x][y-1]=d0+1
            if x<H-1 and S[x+1][y]==0 and d[x+1][y]==-1:
                q.append((x+1,y,d0+1))
                d[x+1][y]=d0+1
            if y<W-1 and S[x][y+1]==0 and d[x][y+1]==-1:
                q.append((x,y+1,d0+1))
                d[x][y+1]=d0+1
        r=max(r,d0)
print(r)

Fixed submission:
N,K=map(int,input().split())
A=sorted(map(int,input().split()))
r=0
MOD=10**9+7
max_n=10**5
fac=[1]*(max_n+1)
inv=[1]*(max_n+1)
ifac=[1]*(max_n+1)
for n in range(2,max_n+1):
    fac[n]=(fac[n-1]*n)%MOD
    inv[n]=MOD-inv[MOD%n]*(MOD//n)%MOD
    ifac[n]=(ifac[n-1]*inv[n])%MOD
def comb(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    return (fac[n]*ifac[k]*ifac[n-k])%MOD
for i,a in enumerate(A):
    r=(r+(comb(i,K-1)-comb(N-1-i,K-1))*a)%MOD
print(r)
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=map(int,input().split())
m=10**9+7
r=1
C=[0,0,0]
for a in A:
    i=C.index(a)
    r=r*sum([1 if c==a else 0 for c in C])%m
    C[i]+=1
print(r)

Fixed submission:
N=int(input())
A=map(int,input().split())
m=10**9+7
r=1
C=[0,0,0]
for a in A:
    try:
        i=C.index(a)
        r=r*sum([1 if c==a else 0 for c in C])%m
        C[i]+=1
    except:
        print(0)
        exit()
print(r)

Buggy python submission (verdict: Runtime Error):
N=int(input())
A=list(map(int,input().split()))
m=10**9+7
r=1
C=[0,0,0]
for a in A:
    i=C.index(a)
    r=r*sum([1 if c==a else 0 for c in C])%m
    C[i]+=1
print(r)

Fixed submission:
N=int(input())
A=map(int,input().split())
m=10**9+7
r=1
C=[0,0,0]
for a in A:
    try:
        i=C.index(a)
        r=r*sum([1 if c==a else 0 for c in C])%m
        C[i]+=1
    except:
        print(0)
        exit()
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
A,F=[list(map(int,input().split())) for i in range(2)]
A.sort()
F.sort()
l,r=-1,10**18
while r-l>1:
    h=(l+r)//2
    k=0
    for i in range(N):
        k+=max(0,A[i]-h//F[-i-1])
        if k>K:
            k=-1
            break
    if k>=0:
        r=h
    else:
        l=h
print(r)

Fixed submission:
N,K=map(int,input().split())
A,F=[list(map(int,input().split())) for i in range(2)]
A.sort()
F.sort()
l,r=-1,10**18
while r-l>1:
    h=(l+r)//2
    k=0
    for i in range(N):
        k+=max(0,A[i]-h//F[-i-1])
        if k>K:
            k=-1
            break
    if k>=0:
        r=h
    else:
        l=h
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
P=list(map(int,input().split()))
class SegTree:
    def __init__(self,size):
        self.N=size
        self.v=[-1]*(2*self.N-1)
        self.w=[10**6]*(2*self.N-1)
    def update(self,i,x):
        i+=self.N-1
        self.v[i]=x
        self.w[i]=x
        while i>0:
            i=(i-1)//2
            self.v[i]=max(self.v[i*2+1],self.v[i*2+2])
            self.w[i]=min(self.w[i*2+1],self.w[i*2+2])
    def max(self,a,b,i=0,l=0,r=1e9):
        if r==1e9:
            r=self.N
        if r<=a or b<=l:
            return -1
        if a<=l and r<=b:
            return self.v[i]
        return max(self.max(a,b,i*2+1,l,(l+r)//2),self.max(a,b,i*2+2,(l+r)//2,r))
    def min(self,a,b,i=0,l=0,r=1e9):
        if r==1e9:
            r=self.N
        if r<=a or b<=l:
            return 10**6
        if a<=l and r<=b:
            return self.w[i]
        return min(self.min(a,b,i*2+1,l,(l+r)//2),self.min(a,b,i*2+2,(l+r)//2,r))
s=SegTree(2**18)
x,n=0,0
for i,p in enumerate(P):
    s.update(i,p)
    if P[i-1]<P[i]:
        x+=1
        if K-1<=i and x==K-1:
            n+=1
            x-=1
    else:
        x=0
r=1
n=max(0,n-1)
for i in range(N-K):
    m,M=s.min(i+1,K+i),s.max(i+1,K+i)
    if not (P[i]<m and M<P[K+i]):
        r+=1
print(max(1,r-n))

Fixed submission:
N,K=map(int,input().split())
P=list(map(int,input().split()))
from collections import deque
smin,smax=deque(),deque()
x,r,r2=0,0,0
for i,p in enumerate(P):
    while len(smin)>0 and P[smin[-1]]>p:
        smin.pop()
    smin.append(i)
    if smin[0]<=i-K:
        smin.popleft()
    while len(smax)>0 and P[smax[-1]]<p:
        smax.pop()
    smax.append(i)
    if smax[0]<=i-K:
        smax.popleft()
    if i>0 and P[i-1]<P[i]:
        x=min(x+1,K-1)
    else:
        x=0
    if i==K-1 or (i>=K and not (P[i-K]<P[smin[0]] and smax[0]==i)):
        if x!=K-1:
            r+=1
        else:
            r2=1
print(r+1 if r2 else r)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=[ord(c) for c in input()]
def zalgo(S):
    a=[0]*len(S)
    c=0
    for i in range(1,len(S)):
        if i+a[i-c]<c+a[c]:
            a[i]=a[i-c]
        else:
            j=max(0,c+a[c]-i)
            while i+j<len(S) and S[j]==S[i+j]:
                j+=1
            a[i]=min(i,j)
    a[0]=len(S)
    return a
r=0
for i in range(N):
    a=zalgo(S[i:])
    m=max(a[1:]) if len(a)>1 else 0
    r=max(r,m)
print(r)

Fixed submission:
N=int(input())
S=input()
l,u=0,N
while l+1<u:
    m=(l+u)//2
    s=set()
    for i in range(N-m*2+1):
        s.add(S[i:i+m])
        if S[i+m:i+m*2] in s:
            l=m
            break
    if l!=m:
        u=m
print(l)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=[ord(c) for c in input()]
def zalgo(S):
    a=[0]*len(S)
    c=0
    for i in range(1,len(S)):
        if i+a[i-c]<c+a[c]:
            a[i]=a[i-c]
        else:
            j=max(0,c+a[c]-i)
            while i+j<len(S) and S[j]==S[i+j]:
                j+=1
            a[i]=j
    a[0]=len(S)
    return a
r=0
for i in range(N):
    a=zalgo(S[i:])
    for j in range(N-i):
        r=max(r,min(a[j],j))
print(r)

Fixed submission:
N=int(input())
S=input()
l,u=0,N
while l+1<u:
    m=(l+u)//2
    s=set()
    for i in range(N-m*2+1):
        s.add(S[i:i+m])
        if S[i+m:i+m*2] in s:
            l=m
            break
    if l!=m:
        u=m
print(l)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=input()
def zalgo(S):
    a=[0]*len(S)
    c=0
    for i in range(1,len(S)):
        if i+a[i-c]<c+a[c]:
            a[i]=a[i-c]
        else:
            j=max(0,c+a[c]-i)
            while i+j<len(S) and S[j]==S[i+j]:
                j+=1
            a[i]=j
    a[0]=len(S)
    return a
r=0
for i in range(N):
    a=zalgo(S[i:])
    for j in range(N-i):
        r=max(r,min(a[j],j))
print(r)

Fixed submission:
N=int(input())
S=input()
l,u=0,N
while l+1<u:
    m=(l+u)//2
    s=set()
    for i in range(N-m*2+1):
        s.add(S[i:i+m])
        if S[i+m:i+m*2] in s:
            l=m
            break
    if l!=m:
        u=m
print(l)
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
AB=sorted([list(map(int,input().split())) for i in range(N)],key=lambda x: (-x[1],x[0]))
r=0
on=[-1]*M
import sys
sys.setrecursionlimit(10**5)
def put(i):
    r=0
    if i<0:
        return -1
    if on[i]<0:
        if i==0:
            if on[i]==-1:
                on[i]=-2
            else:
                r=-1
        elif on[i-1]==-1:
            on[i]=i-1
        else:
            on[i]=on[i-1]
    else:
        r=put(on[i])
    return r
for a,b in AB:
    x=put(M-a)
    if x!=-1:
        r+=b
print(r)

Fixed submission:
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
r=0
from heapq import heappop,heappush
q=[]
l=[[] for i in range(10**5)]
for a,b in AB:
    l[a-1].append(b)
for i in range(M):
    for e in l[i]:
        heappush(q,-e)
    if len(q)>0:
        r+=-heappop(q)
print(r)

Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
AB=sorted([list(map(int,input().split())) for i in range(N)],key=lambda x: (-x[1],x[0]))
r=0
on=[-1]*M
def put(i):
    r=0
    if i<0:
        return -1
    if on[i]<0:
        if i==0:
            if on[i]==-1:
                on[i]=-2
            else:
                r=-1
        elif on[i-1]==-1:
            on[i]=i-1
        else:
            on[i]=on[i-1]
    else:
        r=put(on[i])
    return r
for a,b in AB:
    x=put(M-a)
    if x!=-1:
        r+=b
print(r)

Fixed submission:
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
r=0
from heapq import heappop,heappush
q=[]
l=[[] for i in range(10**5)]
for a,b in AB:
    l[a-1].append(b)
for i in range(M):
    for e in l[i]:
        heappush(q,-e)
    if len(q)>0:
        r+=-heappop(q)
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
S=input()
N=len(S)
from collections import defaultdict
O=[defaultdict(int) for i in range(N+1)]
O[0][5]=1
mod=10**9+7
for i in range(N):
    for o in O[i].keys():
        if S[N-1-i]!='?':
            n=int(S[N-1-i])
            for j in range(10):
                x=13*j+o
                if x%10==n:
                    O[i+1][x//10]=O[i][o]
                    break
        else:
            for j in range(10):
                x=13*j+o
                O[i+1][x//10]=(O[i+1][x//10]+O[i][o])%mod
print(O[N][0])

Fixed submission:
S=input()
N=len(S)
from collections import defaultdict
O=[defaultdict(int) for i in range(N+1)]
O[0][5]=1
mod=10**9+7
for i in range(N):
    for o in O[i].keys():
        if S[N-1-i]!='?':
            n=int(S[N-1-i])
            for j in range(10):
                x=13*j+o
                if x%10==n:
                    O[i+1][x//10]=O[i][o]
                    break
        else:
            for j in range(10):
                x=13*j+o
                O[i+1][x//10]=(O[i+1][x//10]+O[i][o])%mod
print(O[N][0])

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
N=len(S)
from collections import defaultdict
O=defaultdict(int)
O[5]=1
mod=10**9+7
for i in range(N):
    On=defaultdict(int)
    for o in O.keys():
        if S[N-1-i]!='?':
            n=int(S[N-1-i])
            for j in range(10):
                x=13*j+o
                if x%10==n:
                    On[x//10]+=O[o]
        else:
            for j in range(10):
                x=13*j+o
                On[x//10]=(On[x//10]+O[o])%mod
    O=On
print(O[0])

Fixed submission:
S=input()
N=len(S)
from collections import defaultdict
O=[defaultdict(int) for i in range(N+1)]
O[0][5]=1
mod=10**9+7
for i in range(N):
    for o in O[i].keys():
        if S[N-1-i]!='?':
            n=int(S[N-1-i])
            for j in range(10):
                x=13*j+o
                if x%10==n:
                    O[i+1][x//10]=O[i][o]
                    break
        else:
            for j in range(10):
                x=13*j+o
                O[i+1][x//10]=(O[i+1][x//10]+O[i][o])%mod
print(O[N][0])
Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split())
A=[list(map(int,input().split())) for i in range(N-1)]
m=10**9+7
c=[[] for i in range(N)]
for i,j in A:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
import sys
sys.setrecursionlimit(10**6)
def bfs(p):
    r=K
    d=1
    n=[1]*N
    while len(p)>0:
        q=[]
        for e in p:
            n[e]=0
            x=max(K-min(2,d),0)
            for f in c[e]:
                if n[f]:
                    q.append(f)
                    r=(r*x)%m
                    x-=1
        p=q
        d+=1
    return r
print(bfs([A[0][0]-1]))

Fixed submission:
N,K=map(int,input().split())
A=[list(map(int,input().split())) for i in range(N-1)]
m=10**9+7
c=[[] for i in range(N)]
for i,j in A:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
import sys
sys.setrecursionlimit(10**6)
def bfs(p):
    r=K
    d=1
    n=[1]*N
    while len(p)>0:
        q=[]
        for e in p:
            n[e]=0
            x=max(K-min(2,d),0)
            for f in c[e]:
                if n[f]:
                    q.append(f)
                    r=(r*x)%m
                    x-=1
        p=q
        d+=1
    return r
print(bfs([A[0][0]-1]) if N>1 else K)

Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split())
A=[list(map(int,input().split())) for i in range(N-1)]
m=10**9+7
c=[[] for i in range(N)]
for i,j in A:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
def bfs(p):
    r=K
    d=1
    n=[1]*N
    while len(p)>0:
        q=[]
        for e in p:
            n[e]=0
            x=max(K-min(2,d),0)
            for f in c[e]:
                if n[f]:
                    q.append(f)
                    r=(r*x)%m
                    x-=1
        p=q
        d+=1
    return r
print(bfs([A[0][0]-1]))

Fixed submission:
N,K=map(int,input().split())
A=[list(map(int,input().split())) for i in range(N-1)]
m=10**9+7
c=[[] for i in range(N)]
for i,j in A:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
import sys
sys.setrecursionlimit(10**6)
def bfs(p):
    r=K
    d=1
    n=[1]*N
    while len(p)>0:
        q=[]
        for e in p:
            n[e]=0
            x=max(K-min(2,d),0)
            for f in c[e]:
                if n[f]:
                    q.append(f)
                    r=(r*x)%m
                    x-=1
        p=q
        d+=1
    return r
print(bfs([A[0][0]-1]) if N>1 else K)
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
S=list(map(int,input().split()))
T=list(map(int,input().split()))
dp=[[0]*(M+1) for i in range(N+1)]
mod=10**9+7
def Mod(n,mod):
    return n-mod if n>=mod else n
for n in range(1,N+1):
    for m in range(1,M+1):
        x=dp[n-1][m-1]+1 if S[n-1]==T[m-1] else 0
        dp[n][m]=Mod(dp[n-1][m]+dp[n][m-1]-dp[n-1][m-1]+x,mod)
print((dp[-1][-1]+1)%mod)

Fixed submission:
N,M=map(int,input().split())
S=list(map(int,input().split()))
T=list(map(int,input().split()))
dp=[[0]*(M+1) for i in range(N+1)]
mod=10**9+7
for n in range(1,N+1):
    for m in range(1,M+1):
        x=1 if S[n-1]==T[m-1] else -dp[n-1][m-1]
        y=dp[n-1][m]+dp[n][m-1]+x
        dp[n][m]=y if y<mod else y-mod
print((dp[-1][-1]+1)%mod)

Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
S=list(map(int,input().split()))
T=list(map(int,input().split()))
dp=[[0]*(M+1) for i in range(N+1)]
mod=10**9+7
def Mod(n,mod):
    return n-mod if n>=mod else n
for n in range(1,N+1):
    for m in range(1,M+1):
        x=dp[n-1][m-1]+1 if S[n-1]==T[m-1] else 0
        dp[n][m]=Mod(dp[n-1][m]+dp[n][m-1]-dp[n-1][m-1]+x,mod)
print((dp[-1][-1]+1)%mod)

Fixed submission:
N,M=map(int,input().split())
S=list(map(int,input().split()))
T=list(map(int,input().split()))
dp=[[0]*(M+1) for i in range(N+1)]
mod=10**9+7
for n in range(1,N+1):
    for m in range(1,M+1):
        x=1 if S[n-1]==T[m-1] else -dp[n-1][m-1]
        y=dp[n-1][m]+dp[n][m-1]+x
        dp[n][m]=y if y<mod else y-mod
print((dp[-1][-1]+1)%mod)
Buggy python submission (verdict: Runtime Error):
N,K+map(int, input().split())
print(N%K)

Fixed submission:
N,K=map(int,input().split())
[print(0) if K==1 else print(N-K)]
Buggy python submission (verdict: Runtime Error):
N=int(input())
B=sorted([list(map(int,input().split())) for i in range(N)])
d={}
for i in range(N):
    for j in range(i+1,N):
        x=(B[j][0]-B[i][0],B[j][1]-B[i][1])
        if x in d:
            d[x]+=1
        else:
            d[x]=1
print(N-max(d.values()))

Fixed submission:
N=int(input())
B=sorted([list(map(int,input().split())) for i in range(N)])
d={}
for i in range(N):
    for j in range(i+1,N):
        x=(B[j][0]-B[i][0],B[j][1]-B[i][1])
        if x in d:
            d[x]+=1
        else:
            d[x]=1
if N==1:
    print(1)
else:
    print(N-max(d.values()))
Buggy python submission (verdict: Time Limit Exceeded):
H,W=map(int, input().split())
S=[input() for i in range(H)]
l=[[0]*W for i in range(H)]
r=[[0]*W for i in range(H)]
t=[[0]*W for i in range(H)]
b=[[0]*W for i in range(H)]
for h in range(H):
    for w in range(W):
        if S[h][w]=='.':
            l[h][w]=l[h][w-1]+1
            t[h][w]=t[h-1][w]+1
        if S[h][W-w-1]=='.':
            r[h][W-w-1]=r[h][-w]+1
        if S[H-h-1][w]=='.':
            b[H-h-1][w]=b[-h][w]+1
ans=0
for h in range(H):
    for w in range(W):
        ans=max(ans,l[h][w]+r[h][w]+t[h][w]+b[h][w]-3)
print(ans)

Fixed submission:
H,W=map(int, input().split())
S=[input() for i in range(H)]
l=[[0]*W for i in range(H)]
r=[[0]*W for i in range(H)]
t=[[0]*W for i in range(H)]
b=[[0]*W for i in range(H)]
for h in range(H):
    for w in range(W):
        if S[h][w]=='.':
            l[h][w]=l[h][w-1]+1
            t[h][w]=t[h-1][w]+1
        if S[h][W-w-1]=='.':
            r[h][W-w-1]=r[h][-w]+1
        if S[H-h-1][w]=='.':
            b[H-h-1][w]=b[-h][w]+1
ans=0
for h in range(H):
    for w in range(W):
        ans=max(ans,l[h][w]+r[h][w]+t[h][w]+b[h][w]-3)
print(ans)
Buggy python submission (verdict: Runtime Error):
M,K=map(int,input().split())
x=list(range(K))+list(range(K+1,2**M))
print(*(x[::-1]+[K]+x+[K]) if K<2**M-1 else [-1])

Fixed submission:
M,K=map(int,input().split())
x=list(range(2**M))
print(*x[::-1]+x if K==0 else x[:K:-1]+x[K-1::-1]+[K]+x[:K]+x[K+1:]+[K] if K<2**M and M>1 else[-1])
Buggy python submission (verdict: Runtime Error):
h,w=map(int, input().split())
a=[input() for i in range(h)]

non=3000
import numpy as np
b=np.full((h,w),non,dtype=int)
q=[]
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append((i,j))
            b[i][j]=0
ans=-1
while len(q)>0:
    ans+=1
    q2=[]
    for i,j in q:
        if j>0 and b[i][j-1]==non:
            q2.append((i,j-1))
            b[i][j-1]=b[i][j]+1
        if j<w-1 and b[i][j+1]==non:
            q2.append((i,j+1))
            b[i][j+1]=b[i][j]+1
        if i>0 and b[i-1][j]==non:
            q2.append((i-1,j))
            b[i-1][j]=b[i][j]+1
        if i<h-1 and b[i+1][j]==non:
            q2.append((i+1,j))
            b[i+1][j]=b[i][j]+1
    q=q2
print(ans)

Fixed submission:
h,w=map(int, input().split())
a=[input() for i in range(h)]

from collections import deque
b=[[0]*w for i in range(h)]
q=deque()
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append((i,j))
            b[i][j]=1
ans=-1
while len(q)>0:
    ans+=1
    q2=deque()
    for i,j in q:
        if j>0 and b[i][j-1]==0:
            q2.append((i,j-1))
            b[i][j-1]=1
        if j<w-1 and b[i][j+1]==0:
            q2.append((i,j+1))
            b[i][j+1]=1
        if i>0 and b[i-1][j]==0:
            q2.append((i-1,j))
            b[i-1][j]=1
        if i<h-1 and b[i+1][j]==0:
            q2.append((i+1,j))
            b[i+1][j]=1
    q=q2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
h,w=map(int, input().split())
a=[input() for i in range(h)]

non=3000
import numpy as np
b=np.full((h,w),non,dtype=int)
q=[]
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append((i,j))
            b[i][j]=0
ans=-1
while len(q)>0:
    ans+=1
    q2=[]
    for i,j in q:
        if j>0 and b[i][j-1]==non:
            q2.append((i,j-1))
            b[i][j-1]=b[i][j]+1
        if j<w-1 and b[i][j+1]==non:
            q2.append((i,j+1))
            b[i][j+1]=b[i][j]+1
        if i>0 and b[i-1][j]==non:
            q2.append((i-1,j))
            b[i-1][j]=b[i][j]+1
        if i<h-1 and b[i+1][j]==non:
            q2.append((i+1,j))
            b[i+1][j]=b[i][j]+1
    q=q2
print(ans)

Fixed submission:
h,w=map(int, input().split())
a=[input() for i in range(h)]

from collections import deque
b=[[0]*w for i in range(h)]
q=deque()
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append((i,j))
            b[i][j]=1
ans=-1
while len(q)>0:
    ans+=1
    q2=deque()
    for i,j in q:
        if j>0 and b[i][j-1]==0:
            q2.append((i,j-1))
            b[i][j-1]=1
        if j<w-1 and b[i][j+1]==0:
            q2.append((i,j+1))
            b[i][j+1]=1
        if i>0 and b[i-1][j]==0:
            q2.append((i-1,j))
            b[i-1][j]=1
        if i<h-1 and b[i+1][j]==0:
            q2.append((i+1,j))
            b[i+1][j]=1
    q=q2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=[int(input()) for i in range(N)]
mod=998244353
def add(a,b):
    return (a+b)%mod
def sub(a,b):
    return (a-b)%mod
def mul(a,b):
    return ((a%mod)*(b%mod))%mod
def pow(x,y):
    if y==0:
        return 1
    elif y==1:
        return x%mod
    elif y%2==0:
        return pow(x,y//2)**2 % mod
    else:
        return pow(x,y//2)**2 * x % mod
def div(a,b):
    return mul(a,pow(b,mod-2))

sum_S=sum(S)
dp=[[0]*(sum_S+1) for i in range(N)]
dp2=[[0]*(sum_S//2+1) for i in range(N)]

dp[0][0]=2
dp[0][S[0]]=1
dp2[0][0]=1
dp2[0][S[0]]=1
for i in range(1,N):
    for j in range(sum_S+1):
        dp[i][j]=mul(dp[i-1][j],2)
        if j-S[i]>=0 and dp[i-1][j-S[i]]!=0:
            dp[i][j]=add(dp[i][j],dp[i-1][j-S[i]])

        if j<=sum_S//2:
            dp2[i][j]=dp2[i-1][j]
            if j-S[i]>=0 and dp2[i-1][j-S[i]]!=0:
                dp2[i][j]=add(dp2[i][j],dp2[i-1][j-S[i]])

if sum_S%2==0:
    print((pow(3,N)-sum(dp[N-1][sum_S//2:])*3+dp2[N-1][-1]*3)%mod)
else:
    print((pow(3,N)-sum(dp[N-1][sum_S//2+1:])*3)%mod)


Fixed submission:
N=int(input())
S=[int(input()) for i in range(N)]
mod=998244353
def add(a,b):
    return (a+b)%mod
def sub(a,b):
    return (a-b)%mod
def mul(a,b):
    return ((a%mod)*(b%mod))%mod
def pow(x,y):
    if y==0:
        return 1
    elif y==1:
        return x%mod
    elif y%2==0:
        return pow(x,y//2)**2 % mod
    else:
        return pow(x,y//2)**2 * x % mod
def div(a,b):
    return mul(a,pow(b,mod-2))

sum_S=sum(S)
dp=[[0]*(sum_S+1) for i in range(N)]
dp2=[[0]*(sum_S//2+1) for i in range(N)]

dp[0][0]=2
dp[0][S[0]]=1
dp2[0][0]=1
dp2[0][S[0]]=1
for i in range(1,N):
    for j in range(sum_S+1):
        dp[i][j]=mul(dp[i-1][j],2)
        if j-S[i]>=0 and dp[i-1][j-S[i]]!=0:
            dp[i][j]=add(dp[i][j],dp[i-1][j-S[i]])

        if j<=sum_S//2:
            dp2[i][j]=dp2[i-1][j]
            if j-S[i]>=0 and dp2[i-1][j-S[i]]!=0:
                dp2[i][j]=add(dp2[i][j],dp2[i-1][j-S[i]])

if sum_S%2==0:
    print((pow(3,N)-sum(dp[N-1][sum_S//2:])*3+dp2[N-1][-1]*3)%mod)
else:
    print((pow(3,N)-sum(dp[N-1][sum_S//2+1:])*3)%mod)