Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
H=[]
for i in range(N):
  H.append(int(input()))
H.sort()
ans=H[K-1]-H[0]
for i in range(N-K+1):
  A=H[i:i+K]
  if ans>A[K-1]-A[0]:
    ans=A[K-1]-A[0]
print(ans)

Fixed submission:
N,K=map(int,input().split())
H=[]
for i in range(N):
  H.append(int(input()))
H.sort()
print(min(H[i+K-1]-H[i] for i in range(N-K+1)))

Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split())
H=[]
for i in range(N):
  H.append(int(input()))
H.sort()
ans=H[K-1]-H[0]
for i in range(N-K+1):
  if H[K+i]-H[i]>0:
    ans=ans+H[K+i]-H[i]
print(ans)

Fixed submission:
N,K=map(int,input().split())
H=[]
for i in range(N):
  H.append(int(input()))
H.sort()
print(min(H[i+K-1]-H[i] for i in range(N-K+1)))

Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
H=[]
for i in range(N):
  H.append(int(input()))
H.sort()
ans=[]
for i in range(N-K+1):
  A=H[i:i+K]
  ans.append(A[K-1]-A[0])
print(min(ans))



Fixed submission:
N,K=map(int,input().split())
H=[]
for i in range(N):
  H.append(int(input()))
H.sort()
print(min(H[i+K-1]-H[i] for i in range(N-K+1)))
Buggy python submission (verdict: Time Limit Exceeded):
N,M,Q=map(int,input().split())
L,R=[],[]
for i in range(M):
  l,r=map(int,input().split())
  L.append(l)
  R.append(r)
Pl,Ql=[],[]
for i in range(Q):
  pq=list(map(int,input().split()))
  Pl.append(pq[0])
  Ql.append(pq[1])
c=[[0 for i in range(N+1)] for i in range(N+1)]
for i in range(M):
  c[L[i]][R[i]]+=1
for i in range(1,N+1):
  for j in range(1,N+1):
    if i>j:
      c[i][j]=0
    c[i][j]+=c[i][j-1]
ans=[0]*Q
for i in range(Q):
  for j in range(Pl[i],Ql[i]+1):
    ans[i]+=c[j][Ql[i]]-c[j][Pl[i]-1]
for i in range(Q):
  print(ans[i])

Fixed submission:
N,M,Q=map(int,input().split())
L,R=[],[]
for i in range(M):
  l,r=map(int,input().split())
  L.append(l)
  R.append(r)
Pl,Ql=[],[]
for i in range(Q):
  pq=list(map(int,input().split()))
  Pl.append(pq[0])
  Ql.append(pq[1])
c=[[0 for i in range(N+1)] for i in range(N+1)]
for i in range(M):
  c[L[i]][R[i]]+=1
for i in range(1,N+1):
  for j in range(1,N+1):
    c[i][j]+=c[i][j-1]
for i in range(1,N+1):
  for j in range(1,N+1):
    c[i][j]+=c[i-1][j]
for i in range(Q):
  ans=c[Ql[i]][Ql[i]]-c[Pl[i]-1][Ql[i]]-c[Ql[i]][Pl[i]-1]+c[Pl[i]-1][Pl[i]-1]
  print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,M,Q=map(int,input().split())
lr=[]
for i in range(M):
  lr.append(list(map(int,input().split())))
pq=[]
for i in range(Q):
  pq.append(list(map(int,input().split())))
ans=[0]*Q
for i in range(Q):
  for j in range(M):
    if pq[i][0]<=lr[j][0] and lr[j][1]<=pq[i][1]:
      ans[i]+=1
for i in range(Q):
  print(ans[i])

Fixed submission:
N,M,Q=map(int,input().split())
L,R=[],[]
for i in range(M):
  l,r=map(int,input().split())
  L.append(l)
  R.append(r)
Pl,Ql=[],[]
for i in range(Q):
  pq=list(map(int,input().split()))
  Pl.append(pq[0])
  Ql.append(pq[1])
c=[[0 for i in range(N+1)] for i in range(N+1)]
for i in range(M):
  c[L[i]][R[i]]+=1
for i in range(1,N+1):
  for j in range(1,N+1):
    c[i][j]+=c[i][j-1]
for i in range(1,N+1):
  for j in range(1,N+1):
    c[i][j]+=c[i-1][j]
for i in range(Q):
  ans=c[Ql[i]][Ql[i]]-c[Pl[i]-1][Ql[i]]-c[Ql[i]][Pl[i]-1]+c[Pl[i]-1][Pl[i]-1]
  print(ans)
Buggy python submission (verdict: Runtime Error):
s=input()
S=list(s)
cc=0
for i in range(2,len(S)-1):
  if S[i]=='C':
    cc=cc+1
S.remove('C')
S.remove(S[0])
count=[]
if s[0]=='A':
  count.append(1)
if cc==1:
  count.append(2)
if ''.join(S).islower():
  count.append(3)

if count==[1,2,3]:
  print('AC')
else:
  print('WA')

Fixed submission:
s=input()
S=list(s)
cc=0
for i in range(2,len(S)-1):
  if S[i]=='C':
    cc=cc+1
if cc>=1:
  S.remove('C')
S.remove(S[0])
count=[]
if s[0]=='A':
  count.append(1)
if cc==1:
  count.append(2)
if ''.join(S).islower():
  count.append(3)

if count==[1,2,3]:
  print('AC')
else:
  print('WA')

Buggy python submission (verdict: Runtime Error):
s=input()
S=list(s)
cc=0
for i in range(2,len(S)-1):
  if S[i]=='C':
    cc=cc+1
    S.remove(S[i])
S.remove(S[0])
count=[]
if s[0]=='A':
  count.append(1)
if cc==1:
  count.append(2)
if ''.join(S).islower():
  count.append(3)

if count==[1,2,3]:
  print('AC')
else:
  print('WA')

Fixed submission:
s=input()
S=list(s)
cc=0
for i in range(2,len(S)-1):
  if S[i]=='C':
    cc=cc+1
if cc>=1:
  S.remove('C')
S.remove(S[0])
count=[]
if s[0]=='A':
  count.append(1)
if cc==1:
  count.append(2)
if ''.join(S).islower():
  count.append(3)

if count==[1,2,3]:
  print('AC')
else:
  print('WA')
Buggy python submission (verdict: Runtime Error):
S = input()
l = len(S)
num = 0
for i in range(n):
  if S[i] == '+':
    num = num +1
  else :
    num = num -1
print(num)

Fixed submission:
S = input()
l = len(S)
num = 0
for i in range(l):
  if S[i] == '+':
    num = num +1
  else :
    num = num -1
print(num)
Buggy python submission (verdict: Runtime Error):
n,k =int(x) for x in input().split()
s = list(int(y) for y in input().split())
def min(a):
  min = 1000000
  for i in range(len(a)):
    if min > a[i]:
      min = a[i]
      index = i
  return index
c = min(s)
num = (c-1)//k + (len(s)-c)//k +2
print(num)


      


Fixed submission:
nk=list(map(int, input().split()))
a=list(map(int, input().split()))
n=nk[0]
k=nk[1]
def min(A):
  min=1000000
  for x in range(len(A)):
    if A[x]<=min:
      min=A[x]
  return min
m=0
for i in range(n):
  if a[i]==1:
    m=i
l=[]
if n<=k:
  l.append(1)
else:
  for j in range(k):
    if j<k-1:
      l.append(100000)
    elif j>=k-1 and j%(k-1)==0 and (n-j-1)%(k-1)==0:
      l.append(j//(k-1)+(n-j-1)//(k-1))
    elif j>=k-1 and j%(k-1)!=0 and (n-j-1)%(k-1)!=0:
      l.append(j//(k-1)+1+(n-j-1)//(k-1)+1)
    elif j>=k-1 and j%(k-1)!=0 and (n-j-1)%(k-1)==0:
      l.append(j//(k-1)+1+(n-j-1)//(k-1))
    elif j>=k-1 and j%(k-1)==0 and (n-j-1)%(k-1)!=0:
      l.append(j//(k-1)+(n-j-1)//(k-1)+1)
print(min(l))
Buggy python submission (verdict: Runtime Error):
l =list(map(int,input().split()))
if l[0]+l[1]+[2]==17 and l[0]*l[1]*l[2]== 175:
  print('Yes')
else:
  print('No')

Fixed submission:
a = list(int(x) for x in input().split())
if a == [5,5,7] or a == [5,7,5] or a == [7,5,5]:
  print('YES')
else:
  print('NO')

Buggy python submission (verdict: Runtime Error):
a,b,c =int(x) for in input().split()
if a+b+c==17 and a*b*c==175:
  print('Yes')
else:
  print('No')

Fixed submission:
a = list(int(x) for x in input().split())
if a == [5,5,7] or a == [5,7,5] or a == [7,5,5]:
  print('YES')
else:
  print('NO')
Buggy python submission (verdict: Runtime Error):
N, X, M = map(int, input().split())
if X == 0:
    print(0)
    exit()
tx = X % M
tl = []
ts = set()
ttl = []
for i in range(N):
    tl.append(tx)
    ts.add(tx)
    tx = pow(tx, 2, M)
    if tx in ts:
        ttl = tl[tl.index(tx):]
        break
ans = sum(tl)
d, m = divmod(N-len(tl), len(ttl))
ans += sum(ttl)*d+sum(ttl[:m])
print(ans)


Fixed submission:
N, X, M = map(int, input().split())
if X == 0:
    print(0)
    exit()
tx = X % M
tl = []
ts = set()
ttl = []
for i in range(N):
    tl.append(tx)
    ts.add(tx)
    tx = pow(tx, 2, M)
    if tx in ts:
        ttl = tl[tl.index(tx):]
        break
ans = sum(tl)
if len(ttl)>0:
    d, m = divmod(N-len(tl), len(ttl))
    ans += sum(ttl)*d+sum(ttl[:m])
print(ans)

Buggy python submission (verdict: Runtime Error):
N, X, M = map(int, input().split())
if X == 0:
    print(0)
tx = X % M
tl = []
ts = set()
ttl = []
for i in range(N):
    tl.append(tx)
    ts.add(tx)
    tx = pow(tx, 2, M)
    if tx in ts:
        ttl = tl[tl.index(tx):]
        break
ans = sum(tl)
d, m = divmod(N-len(tl), len(ttl))
ans += sum(ttl)*d+sum(ttl[:m])
print(ans)


Fixed submission:
N, X, M = map(int, input().split())
if X == 0:
    print(0)
    exit()
tx = X % M
tl = []
ts = set()
ttl = []
for i in range(N):
    tl.append(tx)
    ts.add(tx)
    tx = pow(tx, 2, M)
    if tx in ts:
        ttl = tl[tl.index(tx):]
        break
ans = sum(tl)
if len(ttl)>0:
    d, m = divmod(N-len(tl), len(ttl))
    ans += sum(ttl)*d+sum(ttl[:m])
print(ans)

Buggy python submission (verdict: Runtime Error):
N, X, M = map(int, input().split())
tx = X % M
tl = []
ts = set()
ttl = []
for i in range(N):
    tl.append(tx)
    ts.add(tx)
    tx = pow(tx, 2, M)
    if tx in ts:
        ttl = tl[tl.index(tx):]
        break
ans = sum(tl)
d, m = divmod(N-len(tl), len(ttl))
ans += sum(ttl)*d+sum(ttl[:m])
print(ans)


Fixed submission:
N, X, M = map(int, input().split())
if X == 0:
    print(0)
    exit()
tx = X % M
tl = []
ts = set()
ttl = []
for i in range(N):
    tl.append(tx)
    ts.add(tx)
    tx = pow(tx, 2, M)
    if tx in ts:
        ttl = tl[tl.index(tx):]
        break
ans = sum(tl)
if len(ttl)>0:
    d, m = divmod(N-len(tl), len(ttl))
    ans += sum(ttl)*d+sum(ttl[:m])
print(ans)

Buggy python submission (verdict: Runtime Error):
N, X, M = map(int, input().split())
tx = X % M
tl = []
ttl = []
for i in range(N):
    tl.append(tx)
    tx = pow(tx, 2, M)
    if tx in tl:
        ttl = tl[tl.index(tx):]
        break
ans = sum(tl)
d, m = divmod(N-len(tl), len(ttl))
ans += sum(ttl)*d+sum(ttl[:m])
print(ans)


Fixed submission:
N, X, M = map(int, input().split())
if X == 0:
    print(0)
    exit()
tx = X % M
tl = []
ts = set()
ttl = []
for i in range(N):
    tl.append(tx)
    ts.add(tx)
    tx = pow(tx, 2, M)
    if tx in ts:
        ttl = tl[tl.index(tx):]
        break
ans = sum(tl)
if len(ttl)>0:
    d, m = divmod(N-len(tl), len(ttl))
    ans += sum(ttl)*d+sum(ttl[:m])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
xy=[tuple(map(int,input().split())) for _ in range(N)]
ans=0
for i in range(N):
    for j in range(i+1,N):
        ans=max(ans,abs(xy[i][0]-xy[j][0])+abs(xy[i][1]-xy[j][1]))
print(ans)

Fixed submission:
N=int(input())
xy=[tuple(map(int,input().split())) for _ in range(N)]
ans=0
zmi=10**10
zma=-10**10
wmi=10**10
wma=-10**10
for x,y in xy:
    zmi=min(zmi,x+y)
    zma=max(zma,x+y)
    wmi=min(wmi,x-y)
    wma=max(wma,x-y)
print(max(zma-zmi,wma-wmi))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
ans = 0
MOD = 10**9+7
for i in range(N):
    for j in range(i+1, N):
        ans += A[i]*A[j] % MOD
        ans %= MOD
print(ans)


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
s = sum(A)
ans = 0
MOD = 10**9+7
for i in range(N):
    s -= A[i]
    ans += s*A[i] % MOD
    ans %= MOD
print(ans)
Buggy python submission (verdict: Runtime Error):
import heapq
import math
N,K=map(int,input().split())
A=list(map(int,input().split()))
hq=[]
for i in A:
    heapq.heappush(hq,-i)
while K>0:
    t1=heapq.heappop(hq)
    t2=heapq.heappop(hq)
    if t1==t2 or K<3:
        heapq.heappush(hq,t1/2)
        heapq.heappush(hq,t1/2)
        heapq.heappush(hq,t2)
        K-=1
    else:
        heapq.heappush(hq,t1/3)
        heapq.heappush(hq,t1/3)
        heapq.heappush(hq,t1/3)
        heapq.heappush(hq,t2)
        K-=2
print(math.ceil(-heapq.heappop(hq)))

Fixed submission:
N,K=map(int,input().split())
A=list(map(int,input().split()))
low=0
high=max(A)
while high-low>1:
    mid=(low+high)//2
    cnt=0
    for i in A:
        cnt+=(i-1)//mid
    if cnt>K:
        low=mid
    else:
        high=mid
print(high)

Buggy python submission (verdict: Runtime Error):
import heapq
N,K=map(int,input().split())
A=list(map(int,input().split()))
hq=[]
for i in A:
    heapq.heappush(hq,-i)
while K>0:
    t1=heapq.heappop(hq)
    t2=heapq.heappop(hq)
    if t1==t2 or K<3:
        heapq.heappush(hq,t1/2)
        heapq.heappush(hq,t1/2)
        heapq.heappush(hq,t2)
        K-=1
    else:
        heapq.heappush(hq,t1/3)
        heapq.heappush(hq,t1/3)
        heapq.heappush(hq,t1/3)
        heapq.heappush(hq,t2)
        K-=2
print(int(-(heapq.heappop(hq)//1)))

Fixed submission:
N,K=map(int,input().split())
A=list(map(int,input().split()))
low=0
high=max(A)
while high-low>1:
    mid=(low+high)//2
    cnt=0
    for i in A:
        cnt+=(i-1)//mid
    if cnt>K:
        low=mid
    else:
        high=mid
print(high)
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
A=list(map(int,input().split()))
t=1
for i in range(K):
    t*=A[i]
for i in range(K,N):
    p=t
    t//=A[i-K]
    t*=A[i]
    if p<t:
        print('Yes')
    else:
        print('No')

Fixed submission:
N,K=map(int,input().split())
A=list(map(int,input().split()))
for i in range(K,N):
    if A[i-K]<A[i]:
        print('Yes')
    else:
        print('No')
Buggy python submission (verdict: Runtime Error):
def f(n):
    if n in memo:
        return memo[n]
    c=list(str(bin(n)))[2:].count('1')
    r=n%c
    if r>0:
        memo[n]=f(r)+1
    else:
        memo[n]=1
    return memo[n]

memo={0:0}
N=int(input())
X=list(input())
XC=X.count('1')
XN=int('0b'+''.join(X),2)
for i in range(N):
    if X[i]=='1':
        tx=(XN%(XC-1)-pow(2,N-i-1,XC-1))
        if tx<0:
            tx+=XC-1
        tx%=XC-1
    else:
        tx=(XN%(XC+1)+pow(2,N-i-1,XC+1))%(XC+1)
    print(f(tx)+1)

Fixed submission:
def f(n):
    if n in memo:
        return memo[n]
    c=list(str(bin(n)))[2:].count('1')
    r=n%c
    if r>0:
        memo[n]=f(r)+1
    else:
        memo[n]=1
    return memo[n]

memo={0:0}
N=int(input())
X=list(input())
XC=X.count('1')
XN=int('0b'+''.join(X),2)
for i in range(N):
    if X[i]=='1':
        if XC==1:
            print(0)
            continue
        tx=(XN%(XC-1)-pow(2,N-i-1,XC-1))
        if tx<0:
            tx+=XC-1
        tx%=XC-1
    else:
        tx=(XN%(XC+1)+pow(2,N-i-1,XC+1))%(XC+1)
    print(f(tx)+1)

Buggy python submission (verdict: Runtime Error):
def f(n):
    if n in memo:
        return memo[n]
    c=list(str(bin(n)))[2:].count('1')
    r=n%c
    if r>0:
        memo[n]=f(r)+1
    else:
        memo[n]=1
    return memo[n]

memo={0:0}
N=int(input())
X=list(input())
XC=X.count('1')
XN=int('0b'+''.join(X),2)
for i in range(N):
    if X[i]=='1':
        tx=(XN%(XC-1)-pow(2,N-i-1,XC-1))%(XC-1)
        if tx<0:
            tx+=XC-1
    else:
        tx=(XN%(XC+1)+pow(2,N-i-1,XC+1))%(XC+1)
    print(f(tx)+1)

Fixed submission:
def f(n):
    if n in memo:
        return memo[n]
    c=list(str(bin(n)))[2:].count('1')
    r=n%c
    if r>0:
        memo[n]=f(r)+1
    else:
        memo[n]=1
    return memo[n]

memo={0:0}
N=int(input())
X=list(input())
XC=X.count('1')
XN=int('0b'+''.join(X),2)
for i in range(N):
    if X[i]=='1':
        if XC==1:
            print(0)
            continue
        tx=(XN%(XC-1)-pow(2,N-i-1,XC-1))
        if tx<0:
            tx+=XC-1
        tx%=XC-1
    else:
        tx=(XN%(XC+1)+pow(2,N-i-1,XC+1))%(XC+1)
    print(f(tx)+1)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
ans=0
for _ in range(N-1):
    u,v=map(int,input().split())
    u,v=min(u-1,v-1),max(u-1,v-1)
    ans-=(u+1)*(N-v)
for i in range(N):
    for j in range(i,N):
        ans+=j-i+1
print(ans)

Fixed submission:
N=int(input())
ans=0
for _ in range(N-1):
    u,v=map(int,input().split())
    u,v=min(u-1,v-1),max(u-1,v-1)
    ans-=(u+1)*(N-v)
for i in range(1,N+1):
    ans+=i*(i+1)//2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
ans=0
for _ in range(N-1):
    u,v=map(int,input().split())
    u,v=min(u-1,v-1),max(u-1,v-1)
    ans-=(u+1)*(N-v)
for i in range(N):
    for j in range(i,N):
        ans+=j-i+1
print(ans)

Fixed submission:
N=int(input())
ans=0
for _ in range(N-1):
    u,v=map(int,input().split())
    u,v=min(u-1,v-1),max(u-1,v-1)
    ans-=(u+1)*(N-v)
for i in range(1,N+1):
    ans+=i*(i+1)//2
print(ans)
Buggy python submission (verdict: Runtime Error):
v

Fixed submission:
D=int(input())
c=list(map(int,input().split()))
s=[list(map(int,input().split())) for _ in range(D)]
for i in range(D):
    print(s[i].index(max(s[i]))+1)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
N=int(input())
A=sorted(list(map(int,input().split())))
c=Counter(A)
ans=0
for i in range(N):
    if c[A[i]]>1:
        continue
    for j in range(N):
        if A[i]/2<A[j]:
            ans+=1
            break
        if A[i]%A[j]==0:
            break
    else:
        ans+=1
print(ans)

Fixed submission:
from collections import Counter
N=int(input())
A=sorted(list(map(int,input().split())))
c=Counter(A)
if 1 in A:
    if c[1]==1:
        print(1)
    else:
        print(0)
    exit()
n=max(A)
ans=[0]*(n+1)
for k,v in c.items():
    if v==1:
        ans[k]=1
for i in c.keys():
    t=i*2
    while t<=n:
        ans[t]=0
        t+=i
print(sum(ans))

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))
ans=0
for i in range(N):
    for j in range(N):
        if i==j:
            continue
        if A[i]%A[j]==0:
            break
    else:
        ans+=1
print(ans)

Fixed submission:
from collections import Counter
N=int(input())
A=sorted(list(map(int,input().split())))
c=Counter(A)
if 1 in A:
    if c[1]==1:
        print(1)
    else:
        print(0)
    exit()
n=max(A)
ans=[0]*(n+1)
for k,v in c.items():
    if v==1:
        ans[k]=1
for i in c.keys():
    t=i*2
    while t<=n:
        ans[t]=0
        t+=i
print(sum(ans))
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
A=list(map(int,input().split()))
a=A[:]
for _ in range(K):
    t=[0]*(N+1)
    for i in range(N):
        ti=a[i]
        t[max(0,i-ti)]+=1
        t[min(N,i+ti+1)]-=1
    a=[]
    for i in range(N):
        a.append(t[i])
        if i>0:
            a[i]+=a[i-1]
    if min(a)==N:
        break
print(*a)

Fixed submission:
N,K=map(int,input().split())
A=list(map(int,input().split()))
a=A[:]
for _ in range(K):
    t=[0]*(N+1)
    for i in range(N):
        ti=a[i]
        t[max(0,i-ti)]+=1
        t[min(N,i+ti+1)]-=1
    a=[]
    for i in range(N):
        a.append(t[i])
        if i>0:
            a[i]+=a[i-1]
    if min(a)==N:
        break
print(*a)

Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
A=list(map(int,input().split()))
a=A[:]
for _ in range(K):
    t=[0]*(N+1)
    for i in range(N):
        ti=a[i]
        t[max(0,i-ti)]+=1
        t[min(N,i+ti+1)]-=1
    a=[]
    for i in range(N):
        a.append(t[i])
        if i>0:
            a[i]+=a[i-1]
print(*a)

Fixed submission:
N,K=map(int,input().split())
A=list(map(int,input().split()))
a=A[:]
for _ in range(K):
    t=[0]*(N+1)
    for i in range(N):
        ti=a[i]
        t[max(0,i-ti)]+=1
        t[min(N,i+ti+1)]-=1
    a=[]
    for i in range(N):
        a.append(t[i])
        if i>0:
            a[i]+=a[i-1]
    if min(a)==N:
        break
print(*a)
Buggy python submission (verdict: Time Limit Exceeded):
N,S=map(int,input().split())
A=list(map(int,input().split()))
MOD=998244353
dp=[[0 for _ in range(S+1)] for _ in range(N+1)]
dp[0][0]=1
for i in range(N):
    for j in range(S+1):
        dp[i+1][j]+=dp[i][j]*2
        dp[i+1][j]%=MOD
        if j+A[i]<=S:
            dp[i+1][j+A[i]]+=dp[i][j]
            dp[i+1][j+A[i]]%=MOD
print(dp[-1][-1])

Fixed submission:
N,S=map(int,input().split())
A=list(map(int,input().split()))
MOD=998244353
dp=[[0 for _ in range(S+1)] for _ in range(N+1)]
dp[0][0]=1
for i in range(N):
    for j in range(S+1):
        dp[i+1][j]+=dp[i][j]*2
        dp[i+1][j]%=MOD
        if j+A[i]<=S:
            dp[i+1][j+A[i]]+=dp[i][j]
            dp[i+1][j+A[i]]%=MOD
print(dp[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))
ans=0
t=[]
for i in range(N):
    ans+=t.count(A[i]-i)
    t.append(-A[i]-i)
print(ans)

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
ans=0
t=dict()
for i in range(N):
    if A[i]-i in t:
        ans+=t[A[i]-i]
    t.setdefault(-A[i]-i,0)
    t[-A[i]-i]+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))
ans=0
t=[]
for i in range(N):
    for j in t:
        if A[i]==j+i:
            ans+=1
    t.append(-A[i]-i)
print(ans)

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
ans=0
t=dict()
for i in range(N):
    if A[i]-i in t:
        ans+=t[A[i]-i]
    t.setdefault(-A[i]-i,0)
    t[-A[i]-i]+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))
ans=0
t=[]
for i in range(N):
    for j in t:
        if A[i]==j+i:
            ans+=1
    t.append(-A[i]-i)
print(ans)

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
ans=0
t=dict()
for i in range(N):
    if A[i]-i in t:
        ans+=t[A[i]-i]
    t.setdefault(-A[i]-i,0)
    t[-A[i]-i]+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))
ans=0
for i in range(N-1):
    for j in range(i+1,N):
        if j-i==A[i]+A[j]:
            ans+=1
print(ans)

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
ans=0
t=dict()
for i in range(N):
    if A[i]-i in t:
        ans+=t[A[i]-i]
    t.setdefault(-A[i]-i,0)
    t[-A[i]-i]+=1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
N,M,Q=map(int,input().split())
ABCD=[list(map(int,input().split())) for _ in range(Q)]
tl=[]
for i in range(1,M+1):
    tl.append([i])
for i in range(N):
    t=[]
    for l in tl:
        for j in range(1,M+1):
            if l[-1]<=j:
                t.append(l+[j])
    tl=t[:]
ans=0
for l in tl:
    t=0
    for a,b,c,d in ABCD:
        if l[b-1]-l[a-1]==c:
            t+=d
    ans=max(ans,t)
print(ans)

Fixed submission:
import itertools
N,M,Q=map(int,input().split())
ABCD=[list(map(int,input().split())) for _ in range(Q)]
tl=[]
for i in range(1,M+1):
    tl.append([i])
for i in range(N):
    t=[]
    for l in tl:
        for j in range(1,M+1):
            if l[-1]<=j:
                t.append(l+[j])
    tl=t[:]
ans=0
for l in tl:
    t=0
    for a,b,c,d in ABCD:
        if l[b-1]-l[a-1]==c:
            t+=d
    ans=max(ans,t)
print(ans)