Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!

D,G = map(int,input().split()) # D問題数,G目標点
lst = [list(map(int,input().split()))for i in range(D)]
ans = float('inf')
for i in range(1 << D): # 全探索
    tmp = 0
    count = 0
    bit = ""
    for j in range(len(lst)):
        bit+=str((i >> j)&1)
        if ((i >> j) & 1) == 1:
            tmp = tmp + lst[j][1] + ((j + 1) * 100 * lst[j][0])
            count+=lst[j][0]
    #print("tmp",tmp)
    if tmp < G or tmp >= G:
        #print(bit)
        for n,k in enumerate(list(bit)):
            if k == "0":
                for p in range(lst[len(bit) - n - 1][0]):
                    t = p * 100 * (n+1)
                    #print("p",p,t,tmp,G,count)
                    if t + tmp >= G:
                        ans = min(ans,p+count)
    
    #if tmp >= G :
    else:
        ans = min(ans,count)
    #print(ans,tmp,count)

print(int(ans))

Fixed submission:
# coding: utf-8
# Your code here!

D,G = map(int,input().split()) # D問題数,G目標点
lst = [list(map(int,input().split()))for i in range(D)]
ans = float('inf')
for i in range(1 << D): # 全探索
    tmp = 0
    count = 0
    bit = ""
    for j in range(len(lst)):
        bit+=str((i >> j)&1)
        if ((i >> j) & 1) == 1:
            tmp = tmp + lst[j][1] + ((j + 1) * 100 * lst[j][0])
            count+=lst[j][0]
    #print("tmp",tmp)
    if tmp < G : #or tmp >= G
        #print(bit)
        for n,k in enumerate(list(bit)):
            if k == "0":
                for p in range(lst[len(bit) - n - 1][0]):
                    t = p * 100 * (n+1)
                    #print("p",p,t,tmp,G,count)
                    if t + tmp >= G:
                        ans = min(ans,p+count)
    
    #if tmp >= G :
    else:
        ans = min(ans,count)
    #print(ans,tmp,count)
print(int(ans))
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
# Your code here!
import math
N = int(input())
lst = list(map(int,input().split()))
ans = float('inf')
for i in range(N-1):
    #print(sum(lst[:i+1]) , sum(lst[i+1:]))
    ans = min(ans,math.fabs(sum(lst[:i+1]) - sum(lst[i+1:])))
print(int(ans))

Fixed submission:
# coding: utf-8
# Your code here!
import math
N = int(input())
lst = list(map(int,input().split()))
x = lst[0]
y = sum(lst[1:])
ans = abs(y - x)
for i in range(1,N-1):
    x+=lst[i]
    y-=lst[i]
    ans = min(ans,abs(x-y))
print(ans)
Buggy python submission (verdict: Runtime Error):
c = map(int,input().split())
if c[0] < c[2] and c[2] < c[1]:
  print('Yes')
  exit()
if c[0] > c[2] and c[2] > c[1]:
  print('Yes')
  exit()
print('No')

Fixed submission:
#a.py
A,B,C = map(int,input().split())
if A < C and C < B:
  print('Yes')
  exit()
if B < C and C < A:
  print('Yes')
  exit()
print('No')
Buggy python submission (verdict: Runtime Error):
N, K = map(int,input().split())
h = [int(input()) for i in range(N)].sort()
# print(h)

MIN = 10**10
for i in range(N-K):
	if h[i+K-1] - h[i] <= MIN:
		MIN = h[i+K-1] - h[i]
#	print(i,h[i],h[i+K-1])
print(MIN)



Fixed submission:
N, K = map(int,input().split())
h = [0 for i in range(N)]
for i in range(N):
	h[i] = int(input())
h.sort()
# print(h)

MIN = 10**10
for i in range(N-K+1):
	if h[i+K-1] - h[i] <= MIN:
		MIN = h[i+K-1] - h[i]
# print(i,h[i],h[i+K-1])
print(MIN)
Buggy python submission (verdict: Runtime Error):
import collecions

N = int(input())
W = [input() for i in range(N)]
c = collecions.Counter(W)

for i in range(N-1):
    if W[i][-1] != W[i+1][1]:
        print("No")
        exit()
if len(c) != N:
    print("No")
    exit()
print("Yes")

Fixed submission:
import collections

N = int(input())
W = [input() for i in range(N)]
c = collections.Counter(W)

for i in range(N-1):
    if W[i][-1] != W[i+1][0]:
        print("No")
        exit()
if len(c) != N:
    print("No")
    exit()
print("Yes")
Buggy python submission (verdict: Runtime Error):
N, K = map(int,input().split())
x = list(map(int,input().split()))

MIN = float("inf")
for i in range(N-K+1):
	l = i
	r = i + K - 1
		cur1 = 2*abs(x[l]) + abs(x[r]-x[l])
		cur2 = abs(x[l]) + 2*abs(x[r]-x[l])
#		print([l,r,cur1,cur2])
		if cur1 < MIN:
			MIN = cur1
		if cur2 < MIN:
			MIN = cur2
print(MIN)





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

MIN = float("inf")
for i in range(N-K+1):
	l = i
	r = i + K - 1
	cur1 = abs(x[l]) + abs(x[r]-x[l])
	cur2 = abs(x[r]) + abs(x[r]-x[l])
#	print([l,r,cur1,cur2])
	if cur1 < MIN:
		MIN = cur1
	if cur2 < MIN:
		MIN = cur2
print(MIN)

Buggy python submission (verdict: Runtime Error):
N, K = map(int,input().split())
x = list(map(int,input().split()))

o = 0
if x[N-1] <= 0:
	print(x[N-K])
	exit()
if x[0] >= 0:
	print(x[K-1])
	exit()

MIN = float("inf")
for i in range(N-K+1):
	l = i
	r = i + K
		cur1 = 2*abs(x[l]) + abs(x[r]-x[l])
		cur2 = abs(x[l]) + 2*abs(x[r]-x[l])
#		print([l,r,cur1,cur2])
		if cur1 < MIN:
			MIN = cur1
		if cur2 < MIN:
			MIN = cur2
print(MIN)





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

MIN = float("inf")
for i in range(N-K+1):
	l = i
	r = i + K - 1
	cur1 = abs(x[l]) + abs(x[r]-x[l])
	cur2 = abs(x[r]) + abs(x[r]-x[l])
#	print([l,r,cur1,cur2])
	if cur1 < MIN:
		MIN = cur1
	if cur2 < MIN:
		MIN = cur2
print(MIN)

Buggy python submission (verdict: Runtime Error):
N, K = map(int,input().split())
x = list(map(int,input().split()))

o = 0
if x[N-1] <= 0:
	print(x[N-K])
	exit()
if x[0] >= 0:
	print(x[K-1])
	exit()
if 0 in x:
	i = x.index(0)
	del x[i]
	N,K = N-1,K=1

while x[o] < 0:
	o += 1
	if o == N-1:
		break

MIN = float("inf")
for i in range(-K-1,K+1,1):
	l = o - i+1
	r = o + K-i
	if not(l < 0 or l >= N or r < 0 or r >= N):
		cur1 = 2* abs(x[l]) + abs(x[r])
#		print([l,r,cur1,cur2])
		if cur1 < MIN:
			MIN = cur1
		if cur2 < MIN:
			MIN = cur2
print(MIN)





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

MIN = float("inf")
for i in range(N-K+1):
	l = i
	r = i + K - 1
	cur1 = abs(x[l]) + abs(x[r]-x[l])
	cur2 = abs(x[r]) + abs(x[r]-x[l])
#	print([l,r,cur1,cur2])
	if cur1 < MIN:
		MIN = cur1
	if cur2 < MIN:
		MIN = cur2
print(MIN)

Buggy python submission (verdict: Runtime Error):
#N, K = map(int,input().split())
#x = list(map(int,input().split()))

o = 0
if x[N-1] < 0:
	print(x[N-K])
	exit()
if x[0] > 0:
	print(x[K-1])
	exit()

while x[o] < 0:
	o += 1
	if o == N-1:
		break

MIN = float("inf")
for i in range(-K-1,K+1,1):
	l = o - i+1
	r = o + K-i
	if not(l < 0 or l >= N or r < 0 or r >= N):
		cur1 = 2* abs(x[l]) + abs(x[r])
		cur2 = abs(x[l]) + 2*abs(x[r])
#		print([l,r,cur1,cur2])
		if cur1 < MIN:
			MIN = cur1
		if cur2 < MIN:
			MIN = cur2
print(MIN)





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

MIN = float("inf")
for i in range(N-K+1):
	l = i
	r = i + K - 1
	cur1 = abs(x[l]) + abs(x[r]-x[l])
	cur2 = abs(x[r]) + abs(x[r]-x[l])
#	print([l,r,cur1,cur2])
	if cur1 < MIN:
		MIN = cur1
	if cur2 < MIN:
		MIN = cur2
print(MIN)
Buggy python submission (verdict: Runtime Error):
S = input()
K = int(input())
if K == 1:
	print(S[0])
	exit()
i = 0
while S[i] == "1":
	i += 1
print(S[i])


Fixed submission:
S = input()
K = int(input())
if K == 1:
	print(S[0])
	exit()
else:
	i = 0
	K -= 1
	while S[i] == "1" and K > 0:
		i += 1
		K -= 1
	print(S[i])

Buggy python submission (verdict: Runtime Error):
S = int(input())
K = int(input())
if K == 1:
	print(S[0])
	exit()
i = 0
while S[i] == "1":
	i += 1
print(S[i])


Fixed submission:
S = input()
K = int(input())
if K == 1:
	print(S[0])
	exit()
else:
	i = 0
	K -= 1
	while S[i] == "1" and K > 0:
		i += 1
		K -= 1
	print(S[i])
Buggy python submission (verdict: Runtime Error):
from collections import Counter
from itertools import accumulate
from functools import reduce

N, M = map(int, input().split())
A = [int(x) for x in input().split()]

c = Counter([0] + [x % M for x in accumulate(A)])
ans = reduce(add, [v*(v-1)//2 for v in c.values()])
print(ans)


Fixed submission:
from collections import Counter
c = Counter()

N, M = map(int,input().split())
a = list(map(int,input().split())) 
s = 0
c[s] += 1
for i in range(N):
  s = (s + a[i]) % M
  c[s] += 1
# print(c)
S=0
# t=0
for (i,k) in c.items():
  if k > 1:
    S += (k-1)*k//2
  # t += k
print(S)
# print(t)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
P = 10**9+7
d = [[0 for j in range(4)] for i in range(len(S)+1)]

d[len(S)][3] = 1
#d[len(S)][0--2] = 0
for i in range(len(S)-1,-1,-1):
	d[i][3] = (3 if S[i] == "?" else 1) * d[i+1][3]
	d[i][2] = (3 if S[i] == "?" else 1) * d[i+1][2]
	d[i][2] += (1 if S[i] == "C" or S[i] == "?" else 0) * d[i+1][3]
	d[i][1] = (3 if S[i] == "?" else 1) * d[i+1][1]
	d[i][1] += (1 if S[i] == "B" or S[i] == "?" else 0) * d[i+1][2]
	d[i][0] = (3 if S[i] == "?" else 1) * d[i+1][0]
	d[i][0] += (1 if S[i] == "A" or S[i] == "?" else 0) * d[i+1][1]
print(d[0][0] % P)


Fixed submission:
S = input()
P = 10**9+7
d = [[0 for j in range(4)] for i in range(len(S)+1)]

d[len(S)][3] = 1
#d[len(S)][0--2] = 0
for i in range(len(S)-1,-1,-1):
	d[i][3] = ((3 if S[i] == "?" else 1) * d[i+1][3])%P
	d[i][2] = ((3 if S[i] == "?" else 1) * d[i+1][2])%P
	d[i][2] += (1 if S[i] == "C" or S[i] == "?" else 0) * d[i+1][3]
	d[i][1] = ((3 if S[i] == "?" else 1) * d[i+1][1])%P
	d[i][1] += (1 if S[i] == "B" or S[i] == "?" else 0) * d[i+1][2]
	d[i][0] = ((3 if S[i] == "?" else 1) * d[i+1][0])%P
	d[i][0] += (1 if S[i] == "A" or S[i] == "?" else 0) * d[i+1][1]
print(d[0][0] % P)
Buggy python submission (verdict: Runtime Error):
S = input()
w = int(input())
t = ""
for i in range(len(S)//w + 1):
	t += S[w*i]
print(t)


Fixed submission:
S = input()
w = int(input())
t = ""
r = len(S)//w if len(S) % w == 0 else len(S)//w+1
for i in range(r):
	t += S[w*i]
print(t)
Buggy python submission (verdict: Runtime Error):
import itertools, math
N = int(input())
A = list(map(int,input().split()))

C = [A[i] - (i+1) for i in range(N)]

def SAD(C,b):
	S = 0
	for i in range(N):
		S += abs(C[i] - b)
	return S

MAX, MIN = max(C), min(C)

while MIN != MAX:
	d = (MAX-MIN)//3
	x1 = MIN + d
	x2 = MIN + 2*d
	s1 = SAD(C,x1)
	s2 = SAD(C,x2)
#	print((x1,s1,"vs",x2,s2))
	if s1 > s2:
		MIN = x1
	else:
		MAX = x2
print(s1)


Fixed submission:
import itertools, math
N = int(input())
A = list(map(int,input().split()))
C = [A[i] - (i+1) for i in range(N)]

def SAD(C,b):
	S = 0
	for i in range(N):
		S += abs(C[i] - b)
	return S

MAX, MIN = max(C)+1, min(C)

i = 0
while MAX - MIN > 1:
	mid = (MIN + MAX)//2
#	print((MIN,mid,MAX,":",SAD(C,mid) - SAD(C,mid-1)))
	if 	SAD(C,mid) - SAD(C,mid-1) < 0:
		MIN = mid
	else:
		MAX =mid
print(SAD(C,MIN))
Buggy python submission (verdict: Runtime Error):
N = input()
if N < 1000:
    print("ABC")
else:
    print("ABD")


Fixed submission:
N = int(input())
if N < 1000:
    print("ABC")
else:
    print("ABD")
Buggy python submission (verdict: Runtime Error):
N = int(input())
C = [0 for _ in range(N-1)]
S = [0 for _ in range(N-1)]
F = [0 for _ in range(N-1)]
for i in range(N-1):
	C[i],S[i],F[i] = map(int,input().split())

def f(i):
	s = 0
	while i < N-1:
		# find the fastest train at time s from i stattion.
		if s <= S[i]:
			s = S[i]+C[i]
		else:
			m = (s-S[i]) % F[i]
			if m == 0:
				s = s + C[i]
			else:
				s = s + (F-m) + C[i]
			# we use the fact that F[i] | S[i]
		i += 1
	return s

for i in range(N):
	print(f(i))


Fixed submission:
N = int(input())
C = [0 for _ in range(N-1)]
S = [0 for _ in range(N-1)]
F = [0 for _ in range(N-1)]
for i in range(N-1):
	C[i],S[i],F[i] = map(int,input().split())

def f(i):
	s = 0
	while i < N-1:
		# find the fastest train at time s from i stattion.
		if s <= S[i]:
			s = S[i]+C[i]
		else:
			m = (s-S[i]) % F[i]
			if m == 0:
				s = s + C[i]
			else:
				s = s + (F[i]-m) + C[i]
			# we use the fact that F[i] | S[i]
		i += 1
	return s

for i in range(N):
	print(f(i))
Buggy python submission (verdict: Time Limit Exceeded):
N, A, B = map(int,input().split())
h = [0 for i in range(N)]
for i in range(N):
	h[i] = int(input())
h = sorted(h)
import math
# N, A, B = 4, 5, 3
# h = [8,7,4,2]
# h = sorted(h,reverse=True)

def enough(T):
	tmp = 0
	for i in range(N):
		if h[i] >= B*T:
			tmp += math.ceil((h[i]-B*T)/(A-B))
	return True if tmp <= T else False

MAX = 10**9
MIN = 0
while MAX > MIN:
	if enough(MAX) == True and enough(MIN) == False and MAX - MIN == 1:
		break
	MID = (MAX+MIN)//2
	if enough(MID) == True:
		if enough(MID-1) == True:
			MAX = MID-1
		else:
			MAX = MID
	else:
		if enough(MID+1) == False:
			MIN = MID+1
		else:
			MIN = MID
print(MAX)



Fixed submission:
N, A, B = map(int,input().split())
h = [0 for i in range(N)]
for i in range(N):
	h[i] = int(input())
h = sorted(h)
import math
# N, A, B = 4, 5, 3
# h = [8,7,4,2]
# h = sorted(h,reverse=True)

def enough(T):
	tmp = 0
	for i in range(N):
		if h[i] >= B*T:
			tmp += math.ceil((h[i]-B*T)/(A-B))
	return True if tmp <= T else False

MAX = 10**9
MIN = 0
MID = (MAX+MIN)//2
while MAX > MIN+1:
	if enough(MID) == True:
		MAX = MID
	else:
		MIN = MID
	MID = (MAX+MIN)//2
print(MAX)
Buggy python submission (verdict: Runtime Error):
A = int(input())
B = int(input())

if A > B:
	print("GREATER")
elif A = B:
	print("EQUAL")
else A < B:
	print("LESS")


Fixed submission:
A = int(input())
B = int(input())
if A > B:
	print("GREATER")
elif A == B:
	print("EQUAL")
else:
	print("LESS")
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int,input().split()))

def find(a):
	f = "+" if a[0] < 0 else "-"
	s = a[0]
	c = 0
	#print((s,f,c))
	for i in range(1,n):
		if f == "+" and s + a[i] > 0:
			f = "-"
			s = s + a[i]
	#		print((s,f,c))
		elif f == "+":
			c = c + abs(s + a[i])+1
			f = "-"
			s = 1
	#		print((s,f,c))
		elif f == "-" and s + a[i] < 0:
			f = "+"
			s = s + a[i]
	#		print((s,f,c))
		else:
			c = c + abs(s+a[i])+1
			f = "+"
			s = -1
	return c

if a[0] = 0:
	a[0] = -1
	cmin = find(a)
	a[0] = 1
	cmax = find(a)
	c = min(cmin,cmax)
else:
	c = find(a)
print(c)



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

def find(a,flag):
	c = 0
	s = 0
	for i in range(n):
		if flag and s + a[i] > 0:
			flag = False
			s = s + a[i]
		elif flag:
			c = c + abs(s + a[i])+1
			flag = False
			s = 1
		elif not flag and s + a[i] < 0:
			flag = True
			s = s + a[i]
	#		print((s,f,c))
		else:
			c = c + abs(s+a[i])+1
			flag = True
			s = -1
	return c

cplus = find(a,True)
cmin = find(a,False)
print(min(cplus,cmin))
Buggy python submission (verdict: Runtime Error):
K, S = map(int(), input().split())

s = 0
for X in range(K+1):
	for Y in range(K+1):
		Z = S - (X+Y)
		if 0 <= Z and Z <= K:
			s += 1
print(s)


Fixed submission:
K, S = map(int, input().split())

s = 0
for X in range(K+1):
	for Y in range(K+1):
		Z = S - (X+Y)
		if 0 <= Z and Z <= K:
			s += 1
print(s)
Buggy python submission (verdict: Time Limit Exceeded):
H, W, A, B = map(int,input().split())
P = 10**9+7
#H, W, A, B = map(int,"100000 100000 44444 55555".split())

factlist = [1] * (H+W)
t = 1
for i in range(H+W-1):
	t = (t * (i+1)) % P
	factlist[i+1] = t

def fact(i):
	return factlist[i]

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def comb(i,j):
	return (fact(i+j) * modinv(fact(i),P) * modinv(fact(j),P)) % P

s = 0
i = 0
while H-A-i-1 >= 0 and B+i <= W and A+i <= H and W-B-i-1 >= 0:
#	print((H-A-i,B+i+1))
	s = (s + comb(H-A-i-1,B+i) * comb(A+i,W-B-i-1)) % P
	i += 1	
print(s)



Fixed submission:
H, W, A, B = map(int,input().split())
P = 10**9+7
# H, W, A, B = map(int,"2 3 1 1".split())

M = H+W-1
factlist = [1] * (H+W)
factinvlist = [1] * (H+W)
t = 1
for i in range(M):
	t = (t * (i+1)) % P
	factlist[i+1] = t
t = pow(factlist[M],P-2,P)
factinvlist[M] = t
for i in range(M):
	t = (t * (M-i)) % P
	factinvlist[M-i-1] = t

def comb(i,j):
	return (factlist[i+j] * factinvlist[i] * factinvlist[j]) % P

s = 0
i = 0
while H-A-i-1 >= 0 and B+i <= W and A+i <= H and W-B-i-1 >= 0:
#	print((H-A-i,B+i+1))
	s = (s + comb(H-A-i-1,B+i) * comb(A+i,W-B-i-1)) % P
	i += 1	
print(s)

Buggy python submission (verdict: Time Limit Exceeded):
# E.py#
H, W, A, B = map(int,input().split())
P = 10**9+7
# H, W, A, B = map(int,"2 3 1 1".split())

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def fact(i):
	t = 1
	while i > 0:
		t = (t * i) % P
		i -= 1
	return t

def comb(i,j):
	return (fact(i+j) * modinv(fact(i),P) * modinv(fact(j),P)) % P

s = 0
i = 0
while H-A-i > 0 and B+i+1 <= W and A+i <= H and W-B-i >= 0:
#	print((H-A-i,B+i+1))
	s = (s + comb(H-A-i-1,B+i+1-1) * comb(A+i,W-B-i-1)) % P
	i += 1	
print(s)



Fixed submission:
H, W, A, B = map(int,input().split())
P = 10**9+7
# H, W, A, B = map(int,"2 3 1 1".split())

M = H+W-1
factlist = [1] * (H+W)
factinvlist = [1] * (H+W)
t = 1
for i in range(M):
	t = (t * (i+1)) % P
	factlist[i+1] = t
t = pow(factlist[M],P-2,P)
factinvlist[M] = t
for i in range(M):
	t = (t * (M-i)) % P
	factinvlist[M-i-1] = t

def comb(i,j):
	return (factlist[i+j] * factinvlist[i] * factinvlist[j]) % P

s = 0
i = 0
while H-A-i-1 >= 0 and B+i <= W and A+i <= H and W-B-i-1 >= 0:
#	print((H-A-i,B+i+1))
	s = (s + comb(H-A-i-1,B+i) * comb(A+i,W-B-i-1)) % P
	i += 1	
print(s)
Buggy python submission (verdict: Runtime Error):
#include <iostream>
#include <array>

using namespace std;

int main(){
    int N, M, k, val, sum = 0, ans;

    array<int, 100> p;
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> p[i];
        sum += p[i];
    }

    cin >> M;
    for(int i = 0; i < M; i++){
        cin >> k >> val;
        cout << sum + val - p[k - 1] << '\n';
    }
    
}


Fixed submission:
N = int(input())
Nl = list(map(int, input().split()))
s = sum(Nl)

M = int(input())
for i in range(M):
    Ml = list(map(int, input().split()))
    print(s + Ml[1] - Nl[Ml[0] - 1])
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
a.sort()
print(a[len(a)-1]-a[0])

Fixed submission:
a,b,c=map(int,input().split())
if((a*100+b*10+c)%4==0):
	print("YES")
else:print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
 
dp = [[0]*13 for j in range(len(S)+1)]
mod = 10**9+7
 
dp[0][0] = 1
k = 1
L0 = list(range(10))

for s in S:
  if ('?' == s):
    L = L0
  else:
    L = [int(s)]
 
  for l in L:
    for i in range(13):
      tmp = (i * 10) + l
      m = tmp % 13
      dp[k][m] = ((dp[k][m] + dp[k-1][i]) % mod)
  k += 1
print(dp[k-1][5])


Fixed submission:
S = input()
 
dp = [[0]*13 for j in range(len(S)+1)]
mod = 10**9+7
 
dp[0][0] = 1
k = 1
L0 = list(range(10))

for s in S:
  if ('?' == s):
    L = L0
  else:
    L = [int(s)]
 
  for l in L:
    for i in range(13):
      tmp = (i * 10) + l
      m = tmp % 13
      dp[k][m] = ((dp[k][m] + dp[k-1][i]) % mod)
  k += 1
print(dp[k-1][5])

Buggy python submission (verdict: Runtime Error):
S = input()
 
dp = [[0]*13 for j in range(len(S)+1)]
mod = 10**9+7
 
dp[0][0] = 1
k = 1
L0 = list(range(10))

for s in S:
  if ('?' == s):
    L = L0
  else:
    L = [int(s)]
 
  for l in L:
    for i in range(13):
      tmp = (i * 10) + l
      m = tmp % 13
      dp[k][m] = ((dp[k][m][0] + dp[k-1][i][0]) % mod)
  k += 1
print(dp[k-1][5])


Fixed submission:
S = input()
 
dp = [[0]*13 for j in range(len(S)+1)]
mod = 10**9+7
 
dp[0][0] = 1
k = 1
L0 = list(range(10))

for s in S:
  if ('?' == s):
    L = L0
  else:
    L = [int(s)]
 
  for l in L:
    for i in range(13):
      tmp = (i * 10) + l
      m = tmp % 13
      dp[k][m] = ((dp[k][m] + dp[k-1][i]) % mod)
  k += 1
print(dp[k-1][5])

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
 
dp = [[(0,0)]*13 for j in range(len(S)+1)]
mod = 10**9+7
 
dp[0][0] = (1,1)
k = 1
L0 = list(range(10))

for s in S:
  if ('?' == s):
    L = L0
  else:
    L = [int(s)]
 
  for l in L:
    for i in range(13):
      if (dp[k-1][i][1] == 1):
        tmp = (i * 10) + l
        m = tmp % 13
        dp[k][m] = ((dp[k][m][0] + dp[k-1][i][0]) % mod, 1)
  k += 1
print(dp[k-1][5][0])


Fixed submission:
S = input()
 
dp = [[0]*13 for j in range(len(S)+1)]
mod = 10**9+7
 
dp[0][0] = 1
k = 1
L0 = list(range(10))

for s in S:
  if ('?' == s):
    L = L0
  else:
    L = [int(s)]
 
  for l in L:
    for i in range(13):
      tmp = (i * 10) + l
      m = tmp % 13
      dp[k][m] = ((dp[k][m] + dp[k-1][i]) % mod)
  k += 1
print(dp[k-1][5])

Buggy python submission (verdict: Time Limit Exceeded):
S = input()

dp = [[(0,0)]*13 for j in range(len(S)+1)]
mod = 10**9+7

dp[0][0] = (1,1)
k = 1

for s in S:
  if ('?' == s):
    L = list(range(10))
  else:
    L = [int(s)]

  for l in L:
    for i in range(13):
      if (dp[k-1][i][1] == 1):
        tmp = (i * 10) + l
        m = tmp % 13
        c = (tmp // 13)
        dp[k][m] = ((dp[k][m][0] + dp[k-1][i][0]) % mod, 1)
  k += 1
print(dp[k-1][5][0])


Fixed submission:
S = input()
 
dp = [[0]*13 for j in range(len(S)+1)]
mod = 10**9+7
 
dp[0][0] = 1
k = 1
L0 = list(range(10))

for s in S:
  if ('?' == s):
    L = L0
  else:
    L = [int(s)]
 
  for l in L:
    for i in range(13):
      tmp = (i * 10) + l
      m = tmp % 13
      dp[k][m] = ((dp[k][m] + dp[k-1][i]) % mod)
  k += 1
print(dp[k-1][5])
Buggy python submission (verdict: Time Limit Exceeded):
H,W = map(int, input().split())
S = [list(input()) for _ in range(H)]

MH = [[0] * W for _ in range(H)]
MW = [[0] * W for _ in range(H)]

ans = 0
for h in range(H):
  for w in range(W):
    if ('#' != S[h][w]):
      if ((0 < h) & ('#' != S[h-1][w])):
        mh = MH[h-1][w]
      else:
        mh = 0
        for h2 in range(h,H):
          if ('#' == S[h2][w]):
            break
          mh += 1
      MH[h][w] = mh
      if ((0 < w) & ('#' != S[h][w-1])):
        mw = MW[h][w-1]
      else:
        mw = 0
        for w2 in range(w,W):
          if ('#' == S[h][w2]):
            break
          mw += 1
      MW[h][w] = mw
      a = (mh + mw) - 1
      if (ans < a):
        ans = a
      
print(ans)


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

MH = [[0] * W for _ in range(H)]
MW = [[0] * W for _ in range(H)]

ans = 0
for h in range(H):
  for w in range(W):
    if ('#' != S[h][w]):
      if ((0 < h) & ('#' != S[h-1][w])):
        mh = MH[h-1][w]
      else:
        mh = 0
        for h2 in range(h,H):
          if ('#' == S[h2][w]):
            break
          mh += 1
      MH[h][w] = mh
      if ((0 < w) & ('#' != S[h][w-1])):
        mw = MW[h][w-1]
      else:
        mw = 0
        for w2 in range(w,W):
          if ('#' == S[h][w2]):
            break
          mw += 1
      MW[h][w] = mw
      a = (mh + mw) - 1
      if (ans < a):
        ans = a
      
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math
L,A,B,M = map(int, input().split())

d = 0
for i in reversed(range(L)):
  if (d == 0):
    keta = 0
  else:
    keta = int(math.log10(d))+1
  d = (d + 10**keta * (A + B*i))

print(d % M)


Fixed submission:
import sys
sys.setrecursionlimit(1000000)
import numpy as np
input = sys.stdin.readline

L,A,B,M = map(int, input().split())

C = []
for i in range(19):
  C.append(min(max(0,(10**i - A - 1) //B + 1), L))

def R_mul(A, B, M):
  return np.mod((np.dot(A,B)), M)

def R_pow(R, n, M):
  if n == 1:
    return R
  
  R2 = R_mul(R, R, M)
  R2 = R_pow(R2, n//2, M)
  
  if n % 2 == 0:
    return R2
  else:
    return R_mul(R2, R, M)

                 
ans = 0
R = np.ones((3,3))
s = np.array([0, A%M, 1])

for d in range(1,19):
  r = C[d] - C[d-1]
  if (0 == r):
    continue
  R0 = np.array([[pow(10,d,M),1,0],[0,1,(B%M)],[0,0,1]])
  R = R_pow(R0, r, M)
  s = R_mul(R, s, M)
  #print(d, R, s)
  if (C[d] > L):
    break

print(s[0])
Buggy python submission (verdict: Runtime Error):
10
1 8 10 5 8 12 34 100 11 3

Fixed submission:
N = int(input())
*L, = map(int, input().split())

L_sum = sum(L)

res = True
for l in L:
    if ((L_sum - l) <= l):
        res = False

if (res):
    print('Yes')
else:
    print('No')