Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
S=input()
Q=int(input())
reverse=False
for _ in range(Q):
    inp=input()
    if inp[0]=="1":
        reverse= not reverse
    elif inp[0]=="2":
        if (inp[2]=="1" and not reverse) or (inp[2]=="2" and reverse):
            S=inp[4]+S
        else:
            S=S+inp[4]
if reverse:
    S=S[::-1]
print(S)

Fixed submission:
S=input()
Q=int(input())
reverse=False
front=""
rear=""
for _ in range(Q):
    inp=input()
    if inp[0]=="1":
        reverse= not reverse
    elif inp[0]=="2":
        if (inp[2]=="1" and not reverse) or (inp[2]=="2" and reverse):
            front=inp[4]+front
        else:
            rear=rear+inp[4]
ans=front+S+rear
if reverse:
    ans=ans[::-1]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
Q=int(input())
reverse=False
for _ in range(Q):
    inp=input()
    if inp[0]=="1":
        reverse= not reverse
    elif inp[0]=="2":
        if (inp[2]=="1" and not reverse) or (inp[2]=="2" and reverse):
            S=inp[4]+S
        else:
            S=S+inp[4]
if reverse:
    S=S[::-1]
print(S)

Fixed submission:
S=input()
Q=int(input())
reverse=False
front=""
rear=""
for _ in range(Q):
    inp=input()
    if inp[0]=="1":
        reverse= not reverse
    elif inp[0]=="2":
        if (inp[2]=="1" and not reverse) or (inp[2]=="2" and reverse):
            front=inp[4]+front
        else:
            rear=rear+inp[4]
ans=front+S+rear
if reverse:
    ans=ans[::-1]
print(ans)
Buggy python submission (verdict: Runtime Error):
N, M=map(int, input().split())
ans=["-1"]*M
f=0
for i in range(M):
  s, c=map(int, input().split())
  if s==1 and c==0:
    f=1
  if ans[s-1]!=str(c) and ans[s-1]!="-1":
    f=1
  ans[s-1]=str(c)

if f==1:
  print(-1)
else:
  if ans[0]=="-1": ans[0]=="1"
  a="".join(ans)
  b=a.replace("-1", "0")
  print(b)
   

Fixed submission:
N, M=map(int, input().split())
ans=["-1"]*N
f=0
for i in range(M):
  s, c=map(int, input().split())
  if s==1 and c==0 and N!=1:
    f=1
  if ans[s-1]!=str(c) and ans[s-1]!="-1":
    f=1
  ans[s-1]=str(c)

if f==1:
  print(-1)
else:
  if ans[0]=="-1" and N!=1:
    ans[0]="1"
  elif M==0 and N==1:
    ans[0]="0"
  a="".join(ans)
  b=a.replace("-1", "0")
  print(b)

Buggy python submission (verdict: Runtime Error):
N, M=map(int, input().split())
ans=["-1"]*M
f=0
for i in range(M):
  s, c=map(int, input().split())
  if s==1 and c==0:
    f=1
  if ans[s-1]!=str(c) and ans[s-1]!="-1":
    f=1
  ans[s-1]=str(c)

if f==1:
  print(-1)
else:
  a="".join(ans)
  b=a.replace("-1", "1")
  print(b)
   

Fixed submission:
N, M=map(int, input().split())
ans=["-1"]*N
f=0
for i in range(M):
  s, c=map(int, input().split())
  if s==1 and c==0 and N!=1:
    f=1
  if ans[s-1]!=str(c) and ans[s-1]!="-1":
    f=1
  ans[s-1]=str(c)

if f==1:
  print(-1)
else:
  if ans[0]=="-1" and N!=1:
    ans[0]="1"
  elif M==0 and N==1:
    ans[0]="0"
  a="".join(ans)
  b=a.replace("-1", "0")
  print(b)

Buggy python submission (verdict: Runtime Error):
N, M=map(int, input().split())
ans=["1"]*M
tmp=[]
f=0
for i in range(M):
  s, c=map(input().split())
  if [s, c] in tmp or (s==1 and c==0):
    f=1
  tmp.append([s,c])
  ans[s-1]=str(c)

if f==1:
  print(-1)
else:
  print("".join(ans))
   

Fixed submission:
N, M=map(int, input().split())
ans=["-1"]*N
f=0
for i in range(M):
  s, c=map(int, input().split())
  if s==1 and c==0 and N!=1:
    f=1
  if ans[s-1]!=str(c) and ans[s-1]!="-1":
    f=1
  ans[s-1]=str(c)

if f==1:
  print(-1)
else:
  if ans[0]=="-1" and N!=1:
    ans[0]="1"
  elif M==0 and N==1:
    ans[0]="0"
  a="".join(ans)
  b=a.replace("-1", "0")
  print(b)
Buggy python submission (verdict: Runtime Error):
N=int(input())
X=list(map(int, input().spliet()))
k1=(max(X)+min(X))//2
k2=k1+1
ans1=0
ans2=0
for x in X:
  ans1+=(k1-x)**2
  ans2+=(k2-x)**2

print(min(ans1, ans2))

Fixed submission:
N=int(input())
X=list(map(int, input().split()))
g=sum(X)/N
if g-int(g)>=0.5:
  g=int(g)+1
else:
  g=int(g)   
ans=0
for x in X:
  ans+=(x-g)**2

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

M=0
for i in range(N-K+1):
  M=max(M, sum(p[i:K+i]))

ans=M/2+K/2
print(ans)

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

M=[sum(p[:K])]
for i in range(1,N-K+1):
  tmp=M[-1]-p[i-1]+p[i+K-1]
  M.append(tmp)

ans=max(M)/2+K/2
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))

tmpma=n
ans=0
for val in a:
  if val<=tmpmin:
    ans+=1
    tmpmin=val
print(ans)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
 
tmpmin=n
ans=0
for val in a:
  if val<=tmpmin:
    ans+=1
    tmpmin=val
print(ans)
Buggy python submission (verdict: Runtime Error):
N, M=map(int, input().split())
solved=[False]*N
ac=0
wa=0
for _ in range(M):
  p, s=input().split()
  p=int(p)-1
  if solved[p]:
    continue
  if s=="AC":
    solved[p]=True
    ac+=1
  else:
    wa+=1
print(as, wa)  

Fixed submission:
N, M=map(int, input().split())
solved=[False]*N
wal=[0]*N
ac=0
wa=0
for _ in range(M):
  p, s=input().split()
  p=int(p)-1
  if solved[p]:
    continue
  if s=="AC":
    solved[p]=True
    ac+=1
    wa+=wal[p]
  else:
    wal[p]+=1
print(ac, wa)
Buggy python submission (verdict: Runtime Error):
n=int(input())

def is_prime(n):
    if n < 2:
        return False
    else:
        for i in range(2, n):
            if i * i > n:
                break
            elif n % i == 0:
                return False
        return True

for i in range(i,i+30):
  if is_prime(i):
    print(i)

Fixed submission:
n=int(input())
 
def is_prime(n):
    if n < 2:
      return False
    else:
      for i in range(2, n):
        if i * i > n:
            break
        elif n % i == 0:
            return False
    return True

for i in range(n,n+400):
  if is_prime(i):
    print(i)
    break
Buggy python submission (verdict: Runtime Error):
h, w=map(int, input().split())
# 偶数と奇数で場合分け
if h%2==0:
  # 1列でh/2個のマスできるからあとは横何個あるかだけ
  print(int(h*w/2))
else:
  set1=h
  if w%2==0:
    print(int(set1*w/2))
  else:
    rm=w//2
    print(int(set1*rm+h//2+1))

Fixed submission:
n=int(input())
a=int(n/1.08)
aa=a-1
aaa=a+1
b=int(a*1.08)
bb=int(aa*1.08)
bbb=int(aaa*1.08)
A=[a,aa,aaa]
B=[b,bb,bbb]
f=0
for i in range(3):
  if B[i]==n:
    f=1
    ans=A[i]
    break
if f==0:
  print(":(")
else:
  print(ans)
Buggy python submission (verdict: Runtime Error):
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

N=int(input())
div=make_divisors(N)

from math import sqrt

tmpmin=10*10
for i in range(len(div)):
  if tmpmin>abs(sqrt(N)-div[i]):
    tmpmin=abs(sqrt(N)-div[i])
    minidx=i

a=div[minidx]
b=N//a

print(a-1+b-1)


Fixed submission:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

N=int(input())
div=make_divisors(N)

from math import sqrt

tmpmin=10**16
for i in range(len(div)):
  if tmpmin>abs(sqrt(N)-div[i]):
    tmpmin=abs(sqrt(N)-div[i])
    minidx=i

a=div[minidx]
b=N//a

print(a-1+b-1)
Buggy python submission (verdict: Runtime Error):
a, b, x=map(int, input().split())
import math
if 2*x/(a*b)>=a:
  ans=a/(2*b-2*x/(a**2))
else:
  ans=2*x/(a*b**2)
print(90-math.degrees(math.atan(ans)))

Fixed submission:
a, b, x=map(int, input().split())
if a*a*b==x:
  print(0)
  exit()
import math
if 2*x/(a*b)>=a:
  ans=a/(2*b-2*x/(a**2))
else:
  ans=2*x/(a*b**2)
print(90-math.degrees(math.atan(ans)))

Buggy python submission (verdict: Runtime Error):
a, b, x=map(int, input().split())
import math
if 2*x/(a*b)>=a:
  ans=a/(2*b-2*x/(a**2))
else:
  ans=2*x/(a*b**2)

print(math.degrees(math.atan(ans)))

Fixed submission:
a, b, x=map(int, input().split())
if a*a*b==x:
  print(0)
  exit()
import math
if 2*x/(a*b)>=a:
  ans=a/(2*b-2*x/(a**2))
else:
  ans=2*x/(a*b**2)
print(90-math.degrees(math.atan(ans)))
Buggy python submission (verdict: Time Limit Exceeded):
import bisect as bs
N=int(input())
y=list(map(int, input().split()))
y.sort()
ans=0
for i in range(N-2):
  for j in range(i+1, N-1):
    tmp=y[i]+y[j]
    ans+=bs.bisect_left(y[(j+1):],tmp)
    
print(ans)



Fixed submission:
import bisect as bs
N=int(input())
y=list(map(int, input().split()))
y.sort()
ans=0
for i in range(N-2):
  for j in range(i+1, N-1):
    tmp=y[i]+y[j]
    ans+=bs.bisect_left(y[(j+1):],tmp)
    
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
y=list(map(int, input().split()))
y.sort()
ans=0
for i in range(N-2):
  for j in range(i+1, N-1):
    tmp=y[i]+y[j]
    for k in range(j+1, N):
      if y[k]<tmp:
        ans+=1
      else:
        break
print(ans)

Fixed submission:
import bisect as bs
N=int(input())
y=list(map(int, input().split()))
y.sort()
ans=0
for i in range(N-2):
  for j in range(i+1, N-1):
    tmp=y[i]+y[j]
    ans+=bs.bisect_left(y[(j+1):],tmp)
    
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
y=list(map(int, input().split()))
from itertools import combinations
C=list(combinations(range(N), 3))

def cond(a, b, c):
  c1=a+b>c
  c2=b+c>a
  c3=c+a>b
  if c1 and c2 and c3:
    return True
  else:
    return False

ans=0
for c in C:
  if cond(y[c[0]], y[c[1]], y[c[2]]):
    ans+=1

print(ans)
  

Fixed submission:
import bisect as bs
N=int(input())
y=list(map(int, input().split()))
y.sort()
ans=0
for i in range(N-2):
  for j in range(i+1, N-1):
    tmp=y[i]+y[j]
    ans+=bs.bisect_left(y[(j+1):],tmp)
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = list(map(int, input().split()))
dic={}
for i in range(N):
    dic[i]=a.index(i+1)+1
print(*list(dic.values()), sep=" ")

Fixed submission:
N = int(input())
a = list(map(int, input().split()))
ans=[0]*N
for i in range(N):
    ans[a[i]-1]=i+1
print(*ans,sep=" ")

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = list(map(int, input().split()))
ans=[]
for i in range(N):
    ind=a.index(min(a))
    ans.append(ind+1)
    a[ind]=100090
print(*ans, sep=" ")

Fixed submission:
N = int(input())
a = list(map(int, input().split()))
ans=[0]*N
for i in range(N):
    ans[a[i]-1]=i+1
print(*ans,sep=" ")
Buggy python submission (verdict: Runtime Error):
a = list(map(int, input().split()))
def fac(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

la=fac(a[0])
lb=fac(a[1])


print(len(set(la) & set(lb)+1))

Fixed submission:
b = list(map(int, input().split()))
def fac(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

la=fac(b[0])
lb=fac(b[1])


print(len(set(la) & set(lb))+1)

Buggy python submission (verdict: Runtime Error):
a = list(map(int, input().split()))
def fac(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            while temp%i==0:
                temp //= i
            arr.append(i)

    if temp!=1:
        arr.append(temp)

    if arr==[]:
        arr.append(n)

    return arr

la=fac(a[0])
lb=fac(a[1])


print(len(la & lb)+1)

Fixed submission:
b = list(map(int, input().split()))
def fac(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

la=fac(b[0])
lb=fac(b[1])


print(len(set(la) & set(lb))+1)
Buggy python submission (verdict: Time Limit Exceeded):
x = list(map(int, input().split()))
a = [int(input()) for i in range(x[2])]
for i in range(x[0]):
    p=x[1]-x[2]+a.count(i+1)
    if p>0:
        print("Yes")
    else:
        print("No")

Fixed submission:
x = list(map(int, input().split()))
a = [int(input()) for i in range(x[2])]
p = [x[1]-x[2]]*x[0]
for i in range(x[2]):
    p[a[i]-1]+=1
for i in range(len(p)):
    if p[i]>0:
        print("Yes")
    else:
        print("No")
Buggy python submission (verdict: Runtime Error):
import math
n = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort(reverse=True)
M=n[1]
def kyoukai(lis,m):
    s=0
    for i in range(n[0]):
        s+=math.log2(lis[i])
        if s>=m*2:
            boundary=i+1
            break
    return boundary
d=kyoukai(a,M)
k=0
while k!=1:
    for i in range(d):
        a[i]=int(a[i]/2)
    if M-d>0:
        M-=d
        d=kyoukai(a,M)
    else:
        break
print(sum(a))

Fixed submission:
import heapq

N, M= map(int, input().split())
A = list(map(int, input().split()))
a=[-1*i for i in A]
heapq.heapify(a)
for i in range(M):
    m=int(heapq.heappop(a)/2)
    heapq.heappush(a, m)

print(-1*sum(a))

Buggy python submission (verdict: Runtime Error):
n = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort(reverse=True)
M=n[1]
def kyoukai(lis,m):
    s=0
    for i in range(n):
        s+=math.log2(lis[i])
        if s>=n[1]*2:
            boundary=i+1
            break
    return boundary
d=kyoukai(a,M)
for i in range(d):
    a[i]=int(a[i]/2)
    if M-d>0:
        M-=d
        d=kyoukai(a,M)
    else:
        break
print(sum(a))
        

Fixed submission:
import heapq

N, M= map(int, input().split())
A = list(map(int, input().split()))
a=[-1*i for i in A]
heapq.heapify(a)
for i in range(M):
    m=int(heapq.heappop(a)/2)
    heapq.heappush(a, m)

print(-1*sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
n = list(map(int, input().split()))
a = list(map(int, input().split()))
for i in range(n[1]):
    a[a.index(max(a))]=int(max(a)/2)
print(sum(a))

Fixed submission:
import heapq

N, M= map(int, input().split())
A = list(map(int, input().split()))
a=[-1*i for i in A]
heapq.heapify(a)
for i in range(M):
    m=int(heapq.heappop(a)/2)
    heapq.heappush(a, m)

print(-1*sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
n = list(map(int, input().split()))
a = list(map(int, input().split()))
for i in range(n[1]):
    ma=max(a)
    a.remove(ma)
    a.append(int(ma/2))
print(sum(a))

Fixed submission:
import heapq

N, M= map(int, input().split())
A = list(map(int, input().split()))
a=[-1*i for i in A]
heapq.heapify(a)
for i in range(M):
    m=int(heapq.heappop(a)/2)
    heapq.heappush(a, m)

print(-1*sum(a))
Buggy python submission (verdict: Runtime Error):
N, K=map(int, input().split())
A=list(map(int, input().split()))
base=0
for i in range(N-1):
  for j in range(i+1:N):
    if A[i]>A[j]:
      base+=1
rep=K*(K+1)//2
ans=base*rep
print(ans)

Fixed submission:
N, K=map(int, input().split())
a=list(map(int, input().split()))
A=a*2
base=0
matagu=0
for i in range(N):
  for j in range(i+1,2*N):
    if A[i]>A[j]:
      if j>=N:
        matagu+=1
      else:
        base+=1
baserep=K
matagurep=K*(K-1)//2
waru=10**9+7
ans=(base*baserep+matagu*matagurep)%waru
print(ans)
Buggy python submission (verdict: Runtime Error):
N, X=map(int, input().split())
ans=[]
for _ in range(X-N+1, X+N):
  ans.append(_)
print(" ".join(ans))

Fixed submission:
N, X=map(int, input().split())
ans=[]
for _ in range(X-N+1, X+N):
  ans.append(str(_))
print(" ".join(ans))
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
ls=len(s)
now=[1]*ls
chlist=[]
while(1):
  tmp=[0]*ls
  for i in range(ls):
    if s[i]=="R":
      tmp[i+1]+=now[i]
    else:
      tmp[i-1]+=now[i]
  now=tmp
  if now in chlist:
    st=chlist.index(now)
    break
  else:
    chlist.append(now)
ch=chlist[st:]
idx=(10*100-st)%len(ch)-1
ans=[str(i) for i in ch[idx]]
print(" ".join(ans))

Fixed submission:
s=input()
ls=len(s)
ans=[0]*ls
s+="R"
rst=lst=lend=0
for i in range(1,ls):
  if s[i]=="L" and lst==0:
    lst=i
  if lst==0:
    continue
  if s[i+1]=="R":
    lend=i
  if lend==0:
    continue
  ans[lst-1]=(lst-1-rst)//2+1+(lend-lst+1)//2
  ans[lst]=(lst-1-rst+1)//2+(lend-lst)//2+1
  rst=lend+1
  lst=lend=0

an=[str(i) for i in ans]
print(" ".join(an))

Buggy python submission (verdict: Runtime Error):

  s=input()
ls=len(s)
now=[1]*ls
chlist=[]
while(1):
  tmp=[0]*ls
  for i in range(ls):
    if s[i]=="R":
      tmp[i+1]+=now[i]
    else:
      tmp[i-1]+=now[i]
  now=tmp
  if now in chlist:
    st=chlist.index(now)
    break
  else:
    chlist.append(now)
ch=chlist[st:]
idx=(10*100-st)%len(ch)-1
ans=[str(i) for i in ch[idx]]
print(" ".join(ans))

Fixed submission:
s=input()
ls=len(s)
ans=[0]*ls
s+="R"
rst=lst=lend=0
for i in range(1,ls):
  if s[i]=="L" and lst==0:
    lst=i
  if lst==0:
    continue
  if s[i+1]=="R":
    lend=i
  if lend==0:
    continue
  ans[lst-1]=(lst-1-rst)//2+1+(lend-lst+1)//2
  ans[lst]=(lst-1-rst+1)//2+(lend-lst)//2+1
  rst=lend+1
  lst=lend=0

an=[str(i) for i in ans]
print(" ".join(an))
Buggy python submission (verdict: Runtime Error):
N = int(input())
a=[]
for i in range(N):
  a.append(int(input()))

base=max(a)
maxkosu=a.count(base)
if maxkosu>1:
  for i in range(N):
    print(base)
else:
  maxidx=a.index(base)
  reigai=max(max(a[:maxidx]), max(a[maxidx+1:]))
  for i in range(N):
    if i==maxidx:
      print(reigai)
    else:
      print(base)
  

Fixed submission:
N = int(input())
a=[]
for i in range(N):
  a.append(int(input()))

base=max(a)
maxkosu=a.count(base)
if maxkosu>1:
  for i in range(N):
    print(base)
else:
  maxidx=a.index(base)
  a[maxidx]=-1
  reigai=max(a)
  for i in range(N):
    if i==maxidx:
      print(reigai)
    else:
      print(base)
Buggy python submission (verdict: Runtime Error):
import math
def ncr(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

d = list(map(int, input().split()))
print(d[0]-d[1]+1)
for i in range(2, d[1]+1): #2~k
    print(ncr(d[0]-d[1]+1, i)*ncr(d[1]-1, i-1)%1000000007)

Fixed submission:
import math
def ncr(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

d = list(map(int, input().split()))
print(d[0]-d[1]+1)
for i in range(2, d[1]+1): #2~k
    if (d[0]-d[1]+1)<i:
        print(0)
    else:
        print(ncr(d[0]-d[1]+1, i)*ncr(d[1]-1, i-1)%1000000007)
Buggy python submission (verdict: Runtime Error):
a = list(map(int, input().split()))
L = list(map(int, input().split()))
d = 0
ans = 0
while d<=a[1]:
    d += L[ans]
    ans += 1
print(ans)

Fixed submission:
a = list(map(int, input().split()))
L = list(map(int, input().split()))
d = 0
ans = 0
i=1
while i==1:
    d += L[ans]
    if d>a[1]:
        break
    ans += 1
    if ans==a[0]:
        break

print(ans+1)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
mae = 0
sub = []
flag = False

for _ in range(M):
  broken = int(input())
  if mae == broken: # 不可能
    flag = True
  if flag:
    continue
  if mae+1 == broken:
    mae = broken + 1
    continue
  sub.append(broken-1-mae)
  mae = broken + 1
# 無理な時
if flag:
  print(0)
  exit()
# forの中で最後まで行ってない分の追加
if mae != N:
  sub.append(N-mae)

from operator import mul
from functools import reduce

# nCrの関数
def C(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom
# 壊れてるやつの間の上り方の場合の数
def count(n):
  ans = 1
  for i in range(n//2):
    ans += C(n-i-1, i+1)
  return ans

ans = 1
waru = 10**9+7
for s in sub:
  ans *= count(s)%waru
print(ans%waru)

Fixed submission:
N, M = map(int, input().split())
A = [True]*N
for _ in range(M):
  a = int(input())
  A[a-1] = False # 壊れてるところはfalse

waru = 10**9 + 7
dp = [0]*(N+1)

dp[0], dp[1] = 1, 1 # 初期条件
if not A[0]: # 1段目が壊れてたら
  dp[1] = 0

for i in range(2,N+1):
  # 壊れてるところはdp=0にする
  if not A[i-1]:
    dp[i] = 0
  else:
    dp[i] = (dp[i-1] + dp[i-2])%waru
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
mae = 0
sub = []
flag = False

for _ in range(M):
  broken = int(input())
  if mae == broken: # 不可能
    flag = True
  if flag:
    continue
  if mae+1 == broken:
    mae = broken + 1
    continue
  sub.append(broken-1-mae)
  mae = broken + 1
# 無理な時
if flag:
  print(0)
  exit()
# forの中で最後まで行ってない分の追加
if mae != N:
  sub.append(N-mae)

from operator import mul
from functools import reduce

# nCrの関数
def C(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom
# 壊れてるやつの間の上り方の場合の数
def count(n):
  ans = 1
  for i in range(n//2):
    ans += C(n-i-1, i+1)
  return ans

ans = 1
for s in sub:
  ans *= count(s)
print(ans%(10**9+7))

Fixed submission:
N, M = map(int, input().split())
A = [True]*N
for _ in range(M):
  a = int(input())
  A[a-1] = False # 壊れてるところはfalse

waru = 10**9 + 7
dp = [0]*(N+1)

dp[0], dp[1] = 1, 1 # 初期条件
if not A[0]: # 1段目が壊れてたら
  dp[1] = 0

for i in range(2,N+1):
  # 壊れてるところはdp=0にする
  if not A[i-1]:
    dp[i] = 0
  else:
    dp[i] = (dp[i-1] + dp[i-2])%waru
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, M=map(int, input().split())
a=list(map(int, input().split()))
a.sort()

import bisect

for i in range(M):
  b, c=map(int, input().split())
  t=min(b, bisect.bisect(a,c)) # c以下の要素数
  a[:t]=[c]*t
  a.sort()
print(sum(a))
  

Fixed submission:
n, m =map(int,input().split())
A = list(map(int,input().split()))
BC = [tuple(map(int,input().split()))for i in range(m)]

A.sort()
# 書き換え得点がでかい順に並べる
BC.sort(key= lambda x : -x[1])

i = 0
f=0
for b, c in BC:
    for j in range(b):
      # 見てるとこがはみ出してないかつ、cより小さい
      if i+j<n and A[i+j]<c:
        A[i+j]=c
      else: # もう走査しても意味ないからぶれーく
        break
    i+=b
print(sum(A))
Buggy python submission (verdict: Runtime Error):
N = int(input())
a = list(map(int,input().split()))
err = 8
ma1 = [1]
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y) 
for i in range(1,N):
    f = gcd(a[0],a[i])
    for j in range(1,N):
        if a[j]%f != 0:
            err = err + 1
        if err == 10:
            break
    if err < 10:
        ma1.append(f)
arr = 8
ma2 = [1]

tmp = a[N-1]
a[N-1]=a[0]
a[0]=tmp


for i in range(1,N):
    f = gcd(a[0],a[i])
    for j in range(1,N):
        if a[j]%f != 0:
            arr = arr + 1
        if arr == 10:
            break
    if arr < 10:
        ma2.append(f)



if max(ma2) > max(ma1):
    print(max(ma2))
else:
    print(max(ma1))

Fixed submission:
a = list(map(int, input().split()))
num = int(a[2]/a[0])
print(a[1]*num)
Buggy python submission (verdict: Runtime Error):
N, Q=map(int, input().split())
S=input()
count=0
ac=[0]
for i in range(N-1):
  if S[i]=="A" and S[i+1]=="C":
    count+=1
  ac.append(count)
for _ in range(Q):
  l, r=map(int, input().split())
  l-=1, r-=1
  print(ac[r]-ac[l])

Fixed submission:
N, Q=map(int, input().split())
S=input()
count=0
ac=[0]
for i in range(N-1):
  if S[i]=="A" and S[i+1]=="C":
    count+=1
  ac.append(count)
for _ in range(Q):
  l, r=map(int, input().split())
  l-=1
  r-=1
  print(ac[r]-ac[l])

Buggy python submission (verdict: Time Limit Exceeded):
N, Q=map(int, input().split())
S=input()
for _ in range(Q):
  l, r=map(int, input().split())
  print(S[l-1:r].count("AC"))

Fixed submission:
N, Q=map(int, input().split())
S=input()
count=0
ac=[0]
for i in range(N-1):
  if S[i]=="A" and S[i+1]=="C":
    count+=1
  ac.append(count)
for _ in range(Q):
  l, r=map(int, input().split())
  l-=1
  r-=1
  print(ac[r]-ac[l])