Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10 ** 6 + 3

#TLE
def solve():
    x, d, n = map(int, input().split())
    ans = 1
    for i in range(n):
        ans *= (x+i*d)
        ans %= mod
    print(ans)
    return


def main():
    Q = int(input())
    for i in range(Q):
        solve()


if __name__ == "__main__":
    main()

Fixed submission:
mod = 10 ** 6 + 3


class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def com(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def pom(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod

    def powe(self, K):
        return self.power[K]

    def rev_powe(self, K):
        return self.rev[K]


combi = Combi(mod-1, mod)


def rev(X):
    return pow(X, mod-2, mod)


def count_div(L, R, D):
    return not bool(R//D - (L-1)//D)


def solve():
    x, d, n = map(int, input().split())
    if d % (mod) == 0:
        print(pow(x,n,mod))
        return
    elif d % (mod) != 0:
        y = rev(d)*x
        if count_div(y, y+n-1, mod):
            y = y % mod
            ans = pow(d, n, mod)*combi.powe(y+n-1) * combi.rev_powe(y)*y
            print(ans % mod)
            return
        else:
            ans = 0
            print(ans % mod)
            return


def main():
    Q = int(input())
    for i in range(Q):
        solve()


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
# equeue

from collections import deque
import heapq


def main():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    res = 0
    for pull in range(K+1):
        push = K - pull
        if push < 0:
            continue
        for left_push in range(push+1):
            tmp_que = deque(V)
            tmp_heap = []
            heapq.heapify(tmp_heap)
            right_push = push - left_push
            for _ in range(left_push):
                heapq.heappush(tmp_heap, tmp_que.popleft())
            for _ in range(right_push):
                heapq.heappush(tmp_heap, tmp_que.pop())

            tmp_res = sum(tmp_que)
            for i in range(min(push, pull)):
                x = heapq.heappop(tmp_heap)
                if x >= 0:
                    heapq.heappush(tmp_heap, x)
                    break

            res = max(res, sum(tmp_heap))
    print(res)
    return


if __name__ == "__main__":
    main()

Fixed submission:
n,k=map(int,input().split())
lists=list(map(int,input().split()))
ans=0
nums=min(n,k)
for j in range(1,nums+1):
    #スライドするときの数 j=0,1,2,3,4......numsまでとることができる
    #n<kの時max n　かつかくjに対して取り除けるのはk-j回めまでである
    #n>=kの時max k かつ　かくｊに対して取り除けるのはk-j回までである
    for m in range(j+1):
        sublist=lists[:m]+lists[n+m-j:]
        sublist=sorted(sublist)
        sublist.append(0)
        del_some=0
        while del_some<k-j and min(sublist)<0:
            del sublist[0]
            del_some+=1
        p=sum(sublist)
        ans=max(ans,p)
print(ans)
Buggy python submission (verdict: Runtime Error):
n,m=list(map(int, input().split() ))
Firstlis=[]
Secondlis=[]
for i in range(m):
  s=list(map(int,inout().split()))
S1=s[0]
S2=s[1]
Firstlis.append(S1)
Secondlis.append(S2)
Min=max(Firstlis)
Max=min(Secondlis)
print(Max-Min)


  


Fixed submission:
n,m=list(map(int, input().split() ))
Firstlis=[]
Secondlis=[]
for i in range(m):
  s=list(map(int,input().split()))
  S1=s[0]
  S2=s[1]
  Firstlis.append(S1)
  Secondlis.append(S2)
Min=max(Firstlis)
Max=min(Secondlis)
if Max>=Min:
    print(Max-Min+1)
else:
    print(0)

Buggy python submission (verdict: Runtime Error):
n,m=list(map(int, input().split() ))
ists=[]
for i in range(m):
  s=list(map(int,inout().split()))
  ists.append(s)
ans=0
justified=True
for j in range(n):
  for k in range(m):
    if ists[k][0]<=j<=ists[k][1]:
      continue
    else:
      justified=False
      break
  if justified:
    ans+=1
    justified=True

print(ans)
  


Fixed submission:
n,m=list(map(int, input().split() ))
Firstlis=[]
Secondlis=[]
for i in range(m):
  s=list(map(int,input().split()))
  S1=s[0]
  S2=s[1]
  Firstlis.append(S1)
  Secondlis.append(S2)
Min=max(Firstlis)
Max=min(Secondlis)
if Max>=Min:
    print(Max-Min+1)
else:
    print(0)

Buggy python submission (verdict: Runtime Error):
n,m=list(map(int,input().split()))
ists=[]
for i in range(m):
  s=list(map(int,inout().split()))
  ists.append(s)
ans=0
justified=True
for j in range(n):
  for k in range(m):
    if ists[k][0]<=j<=ists[k][1]:
      continue
    else:
      justified=False
      break
  if justified:
    ans+=1
print(ans)
  

Fixed submission:
n,m=list(map(int, input().split() ))
Firstlis=[]
Secondlis=[]
for i in range(m):
  s=list(map(int,input().split()))
  S1=s[0]
  S2=s[1]
  Firstlis.append(S1)
  Secondlis.append(S2)
Min=max(Firstlis)
Max=min(Secondlis)
if Max>=Min:
    print(Max-Min+1)
else:
    print(0)
Buggy python submission (verdict: Runtime Error):

##mod,nについての制約は自分でいかに記入する

def find_power(n,mod):
    # 0!からn!までのびっくりを出してくれる関数(ただし、modで割った値に対してである）
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist
 #あるかずxのn乗をmodで割ったあまりを返す関数pow_cal(x,n,mod)
def pow_cal(x,n,mod):
    if n==0:
         return 1
    elif n==1:
         return x%mod
    elif n>=2:
        if n%2==0:
             return (pow_cal(x,n//2,mod)**2)%mod
        else:
             return (x*pow_cal(x,n//2,mod)**2)%mod

def find_inv_power(n,mod):
    #0!からn!までの逆元を素数modで割ったあまりリストを作る関数
    c=1
    uselist=[0 for i in range(n+1)]
    for i in range(1,n+1):
        c*=i
        c%=mod
    first=pow_cal(c,mod-2,mod)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(mod)
    return uselist
    
A=find_power(4*10**5,mod)
B=find_inv_power(4*10**5,mod)

def combi(n,r,mod):
    if n<r:
        return 0
    elif n>=r:
        return (A[n]*B[r]*B[n-r])%(mod)

    
M,N,K=map(int,input().split())
ans=M*N*(M+N)*(M*N-1)//6
mod=10**9+7
print(ans*combi(M*N-2,K-2,mod)%mod)

Fixed submission:
##mod,nについての制約は自分でいかに記入する
mod=10**9+7
def find_power(n,mod):
    # 0!からn!までのびっくりを出してくれる関数(ただし、modで割った値に対してである）
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist
 #あるかずxのn乗をmodで割ったあまりを返す関数pow_cal(x,n,mod)
def pow_cal(x,n,mod):
    if n==0:
         return 1
    elif n==1:
         return x%mod
    elif n>=2:
        if n%2==0:
             return (pow_cal(x,n//2,mod)**2)%mod
        else:
             return (x*pow_cal(x,n//2,mod)**2)%mod

def find_inv_power(n,mod):
    #0!からn!までの逆元を素数modで割ったあまりリストを作る関数
    c=1
    uselist=[0 for i in range(n+1)]
    for i in range(1,n+1):
        c*=i
        c%=mod
    first=pow_cal(c,mod-2,mod)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(mod)
    return uselist
    
A=find_power(4*10**5,mod)
B=find_inv_power(4*10**5,mod)

def combi(n,r,mod):
    if n<r:
        return 0
    elif n>=r:
        return (A[n]*B[r]*B[n-r])%(mod)

    
M,N,K=map(int,input().split())
ans=M*N*(M+N)*(M*N-1)//6

print(ans*combi(M*N-2,K-2,mod)%mod)
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(80000)

n=int(input())
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b,c=map(int,input().split())
        kilist[a-1].append((b,c))
        kilist[b-1].append((a,c))
def search(i):
        searchedlist[i-1]=1
        visitedlist[i-1]=1
        flag=0
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag+=1
                anslist[j[0]-1]=anslist[i-1]+j[1]
        else:
            pass

        if flag>0:    
            for k in kilist[i-1]:
                if searchedlist[k[0]-1]==-1:
                    search(k[0])
search(2)
for i in anslist:
    print(i%2)


Fixed submission:
n,k=map(int,input().split())
s=list(input())
s[k-1]=s[k-1].lower()
print("".join(s))

Buggy python submission (verdict: Runtime Error):
#d-even relation
#ふかさ優先探索の実装
#再起関数の実装を行う
n=int(input())
visitedlist=[-1 for  i in range(n)]
lists=[tuple(map(int,input().split())) for i in range(n-1)]
kilist=[[] for i in range(n)]
for i in lists:
    kilist[i[0]-1].append(i[1:])
    kilist[i[1]-1].append(i[0:3:2])
visitedlist[0]=1
anslist=[0 for i in range(n)]
#開始地点1のところは0を基準としている
#1には初めに訪れる
def search(i):
        flag=False
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag=True
                if j[1]%2==0:
                    anslist[j[0]-1]=anslist[i-1]
                elif j[1]%2!=0:
                    anslist[j[0]-1]=1-anslist[i-1]      
            else:
                pass  
        if flag:    
            for j in kilist[i-1]:
                return search(j[0])
        if not flag:
            pass
            
search(1)
for k in anslist:
    print(k)


Fixed submission:
n,k=map(int,input().split())
s=list(input())
s[k-1]=s[k-1].lower()
print("".join(s))
Buggy python submission (verdict: Runtime Error):
lists=[]
for i n range(5):
  nums=int(input())
  lists.append(nums)
dis=int(input())
lists=sorted(lists)
if lists[-1]-lists[0]<=dis:
  print("Yay!")
else:
  print(":(")

Fixed submission:
lists=[]
for i in range(5):
  nums=int(input())
  lists.append(nums)
dis=int(input())
lists=sorted(lists)
if lists[-1]-lists[0]<=dis:
  print("Yay!")
else:
  print(":(")
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
emptylists=[]
for i in range(5):
    s=int(input())
    emptylists.append(s)
    
lists=[n,0,0,0,0,0]
cnt=0
while lists[5]<n:
    if lists[0]>0:
        which1=min(lists[0],emptylists[1])
    else:
        which1=0
        
    if lists[1]>0:
        whichi2=min(lists[1],emptylists[1])
    else:
        which2=0
        
    if lists[2]>0:
        which3=min(lists[2],emptylists[2])
    else:
        which3=0
        
    if lists[3]>0:
        which4=min(lists[3],emptylists[3])
    else:
        which4=0
        
        
    if lists[4]>0:
        which5=min(lists[4],emptylists[4])
    else:
        which5=0
        
    lists[0]=lists[0]-which1
    lists[1]=lists[1]+which1-which2
    lists[2]=lists[2]+which2-which3
    lists[3]=lists[3]+which3-which4
    lists[4]=lists[4]+which4-which5
    lists[5]=lists[5]+which5
    cnt+=1
print(cnt)

Fixed submission:
import math
n=int(input())
lists=[]
for x in range(5):
    s=int(input())
    lists.append(s)
min_numbers=min(lists[:])
Nums=math.ceil(n/min_numbers)
print(Nums+4)
Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
some=input()
lists=[]
    
for _ in range(q):
    add=list(map(int,input().split()))
    lists.append(add)
for j in range(q):
    nums=0
    nums+=some[lists[j][0]-1:lists[j][1]].count("AC")
    print(nums)


Fixed submission:
n,q=map(int,input().split())
some=input()
lists=[]
for _ in range(q):
    add=list(map(int,input().split()))
    lists.append(add)

emptylists=[0]

for _ in range(n-1):
    numbers=emptylists[-1]
    if some[_ : _+2]=="AC":
        numbers=1+emptylists[-1]        
        emptylists.append(numbers)
    else:
        emptylists.append(numbers)

for j in range(q):
    print(emptylists[lists[j][1]-1]-emptylists[lists[j][0]-1])
Buggy python submission (verdict: Runtime Error):
n=int(input())

s=input()

s=s+str(X)

counter=1

lists=[]

for i in range(n):

  if s[i]==s[i+1]:

    counter+=1

  else:

    lists.append(counter)

    counter=1

ans=1

for i in lists:

  ans=ans*i%(10**9+7)

print(ans)


Fixed submission:
n=int(input())
s=input()
import collections
s=dict(collections.Counter(s))
ans=1
for i in s.values():
    ans*=(i+1)
    ans=(ans)%(10**9+7)
print(ans-1)

Buggy python submission (verdict: Runtime Error):
n=int(input())

s=input()

s=s+str(X)

counter=1

lists=[]

for i in range(n):

  if s[i]==s[i+1]:

    counter+=1

  else:

    lists.append(counter)

    counter=1

ans=1
13
for i in lists:

  ans=ans*i%(10**9+7)

print(ans)

Fixed submission:
n=int(input())
s=input()
import collections
s=dict(collections.Counter(s))
ans=1
for i in s.values():
    ans*=(i+1)
    ans=(ans)%(10**9+7)
print(ans-1)
Buggy python submission (verdict: Runtime Error):
#reversi
n=int(input())
lists=[]
for i in range(n):
    a=int(input())
    lists.append(a)
dp=[0 for i in range(n+1)]
dp[0]=1

before=[0 for i in range(n+1)]

for i in range(n):
    a=lists[i]
    if before[a]==0:
        dp[i+1]=dp[i]
        before[a]=i+1
    elif before[a]!=0:
        if before[a]==i:
            before[a]=i+1
            dp[i+1]=dp[i]
        else:
            dp[i+1]=dp[i]+dp[before[a]]
            before[a]=i+1
print(dp[n])  


Fixed submission:
#reversi
n=int(input())
lists=[]
for i in range(n):
    a=int(input())
    lists.append(a)
dp=[0 for i in range(n+1)]
dp[0]=1
mod=10**9+7
before=[0 for i in range(2*10**5+1)]

for i in range(n):
    a=lists[i]
    if before[a]==0:
        dp[i+1]=dp[i]
        before[a]=i+1
        continue
        
    elif before[a]!=0:
        if before[a]==i:
            before[a]=i+1
            dp[i+1]=dp[i]
        else:
            dp[i+1]=(dp[i]+dp[before[a]])%mod

            before[a]=i+1
print(dp[n]%mod)
Buggy python submission (verdict: Runtime Error):
import math
n=int(input())
lists=list(map(int,input().split()))
gcds=lists[0]
for x in range(n-1):
    if x==0:
        gcds=math.gcd(lists[0],lists[1])
    else:
        add=math.gcd(lists[x],lists[x+1])
        gcds=math.gcd(gcds,add)
print(gcds)

Fixed submission:
import fractions
n=int(input())
lists=list(map(int,input().split()))
gcds=lists[0]
for x in range(n-1):
    if n==0:
        gcds=fractions.gcd(lists[0],lists[1])
    else:
        add=fractions.gcd(lists[x],lists[x+1])
        gcds=fractions.gcd(gcds,add)
print(gcds)

Buggy python submission (verdict: Runtime Error):
import math
n=int(input())
lists=list(map(int,input().split()))
gcds=lists[0]
for x in range(n-1):
    if x==0:
        gcds=math.gcd(lists[0],lists[1])
    else:
        add=math.gcd(lists[x],lists[x+1])
        gcds=math.gcd(gcds,add)
print(gcds)

Fixed submission:
import fractions
n=int(input())
lists=list(map(int,input().split()))
gcds=lists[0]
for x in range(n-1):
    if n==0:
        gcds=fractions.gcd(lists[0],lists[1])
    else:
        add=fractions.gcd(lists[x],lists[x+1])
        gcds=fractions.gcd(gcds,add)
print(gcds)

Buggy python submission (verdict: Runtime Error):
import math
n=int(input())
lists=list(map(int,input().split()))
gcds=lists[0]
for x in range(n-1):
    if n==0:
        gcds=math.gcd(lists[0],lists[1])
    else:
        add=math.gcd(lists[x],lists[x+1])
        gcds=math.gcd(gcds,add)
print(gcds)


Fixed submission:
import fractions
n=int(input())
lists=list(map(int,input().split()))
gcds=lists[0]
for x in range(n-1):
    if n==0:
        gcds=fractions.gcd(lists[0],lists[1])
    else:
        add=fractions.gcd(lists[x],lists[x+1])
        gcds=fractions.gcd(gcds,add)
print(gcds)
Buggy python submission (verdict: Runtime Error):
n=int(input())
lists=[]
lists1=[]
for i in range(n):
    a,b=map(int,input().split())
    lists.append((a+b,a,b))
listed=sorted(lists,key=lambda x:x[0],reverse=True)

ans=0
for n in range(n):
if n%2==0:
    ans+=listed[n][1]
    
elif n%2!=0:
    ans-=listed[n][2]
print(ans)
    

Fixed submission:
n=int(input())
lists=[]
lists1=[]
for i in range(n):
    a,b=map(int,input().split())
    lists.append((a+b,a,b))
listed=sorted(lists,key=lambda x:x[0],reverse=True)

ans=0
for n in range(n):
    if n%2==0:
        ans+=listed[n][1]
    
    elif n%2!=0:
        ans-=listed[n][2]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
import bisect
mod=10**9+7
a.sort()
b.sort()
ans=1
flag=True
if len(set(a))!=n or len(set(b))!=m:
    flag=False
    print(0)
def find(X,lists):
    return bisect.bisect_right(lists,X)!=bisect.bisect_left(lists,X)
    
if flag:
    for i in range(n*m,0,-1):
        #n*m-i+1番目の値をたす.
        if find(i,a):
            if find(i,b):
                pass    
            else:
                ans*=(m-bisect.bisect_left(b,i))
                ans=ans%mod
            
        else:
            if find(i,b):
                ans*=(n-bisect.bisect_right(a,i))
                ans=ans%mod
                
            else:
                ans*=((n-bisect.bisect_left(a,i))*(m-bisect.bisect_left(b,i))-(n*m-i))
                ans=ans%mod
    print(ans)             



Fixed submission:
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
import bisect
mod=10**9+7
a.sort()
b.sort()
ans=1
flag=True
if len(set(a))!=n or len(set(b))!=m:
    flag=False
    print(0)
def find(X,lists):
    return bisect.bisect_right(lists,X)!=bisect.bisect_left(lists,X)
    
if flag:
    for i in range(n*m,0,-1):
        #n*m-i+1番目の値をたす.
        if find(i,a):
            if find(i,b):
                pass    
            else:
                ans*=(m-bisect.bisect_left(b,i))
                ans=ans%mod
            
        else:
            if find(i,b):
                ans*=(n-bisect.bisect_right(a,i))
                ans=ans%mod
                
            else:
                ans*=((n-bisect.bisect_left(a,i))*(m-bisect.bisect_left(b,i))-(n*m-i))
                ans=ans%mod
    print(ans)
Buggy python submission (verdict: Runtime Error):
h,w=map(int,input().split())
lists=[list(input()) for i in range(h)]
visited=[[False for i in range(h)] for j in range(w)]
from collections import deque

ans=0
dif=[(-1,0),(1,0),(0,-1),(0,1)]
def solve(i,j):
    global ans 
    ans=ans
    visited[i][j]=True
    d=deque()
    e=deque()
    d.append((i,j))
    black=0
    white=0
    while d:
        while d:
            p=d.popleft()
            x,y=p
            color=lists[x][y]
            if color=="#":
                black+=1
            else:
                white+=1
            for que in dif:
                dx,dy=que
                if 0<=dx+x<h and 0<=dy+y<w:
                    if visited[dx+x][dy+y]==False and visited[dx+x][dy+y]!=color:
                        visited[dx+x][dy+y]=True
                        e.append((dx+x,dy+y))
                        if color=="#":
                            white+=1
                        else:
                            black+=1
        if e:
            d=e
            e=deque()
    ans+=white*black
flag=True
while flag:
    sub=False
    for i in range(h):
        for j in range(w):
            if visited[i][j]==False:
                solve(i,j)
                sub=True
    if sub==False:
        flag=False
print(ans)
        
        
    
        
        
                        
                
            
    

Fixed submission:
h,w=map(int,input().split())
lists=[list(input()) for i in range(h)]
visited=[[False for i in range(w)] for j in range(h)]
from collections import deque

ans=0
dif=[(-1,0),(1,0),(0,-1),(0,1)]

def solve(i,j):
    global ans 
    ans=ans
    black=0
    white=0
    if visited[i][j]==False:
        if lists[i][j]=="#":
            black+=1
        else:
            white+=1
        visited[i][j]=True
        
    d=deque()
    e=deque()
    d.append((i,j))
    while d:
        while d:
            p=d.popleft()
            x,y=p
            color=lists[x][y]
            for que in dif:
                dx,dy=que
                if 0<=dx+x<h and 0<=dy+y<w:
                    if visited[dx+x][dy+y]==False and lists[dx+x][dy+y]!=color:
                        visited[dx+x][dy+y]=True
                        e.append((dx+x,dy+y))
                        if color=="#":
                            white+=1
                        else:
                            black+=1
        if e:
            d=e
            e=deque()
    ans+=(white)*(black)
flag=True
while flag:
    sub=False
    for i in range(h):
        for j in range(w):
            if visited[i][j]==False:
                solve(i,j)
                sub=True
    if sub==False:
        flag=False
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#flog2
n,k=map(int,input().split())
lists=list(map(int,input().split()))
mini_list=[0 for i in range(n+1)]
#mini_list[i]=iだんめに行くまでに払う最小のコスト
#帰るには一段上がるか、、、、、K段上がるかのK通りで、それぞれの値を計算してそれのmin値を採用すればいい
mini_list[1]=0
mini_list[2]=abs(lists[0]-lists[1])
for i in range(3,n+1):
    a=10**10
    for j in range(1,k+1):
        if   i>j :
            a=min(a,mini_list[i-j]+abs(lists[i-1]-lists[i-1-j]))
        else:
            break
    mini_list[i]=a
print(mini_list[-1])

Fixed submission:
#flog2
n,k=map(int,input().split())
lists=list(map(int,input().split()))
mini_list=[0 for i in range(n+1)]
#mini_list[i]=iだんめに行くまでに払う最小のコスト
#帰るには一段上がるか、、、、、K段上がるかのK通りで、それぞれの値を計算してそれのmin値を採用すればいい
mini_list[1]=0
mini_list[2]=abs(lists[0]-lists[1])
for i in range(3,n+1):
    a=10**10
    for j in range(1,k+1):
        if   i>j :
            a=min(a,mini_list[i-j]+abs(lists[i-1]-lists[i-1-j]))
        else:
            break
    mini_list[i]=a
print(mini_list[-1])

Buggy python submission (verdict: Time Limit Exceeded):
#flog2
n,k=map(int,input().split())
lists=list(map(int,input().split()))
mini_list=[0 for i in range(n+1)]
#mini_list[i]=iだんめに行くまでに払う最小のコスト
#帰るには一段上がるか、、、、、K段上がるかのK通りで、それぞれの値を計算してそれのmin値を採用すればいい
mini_list[1]=0
mini_list[2]=abs(lists[0]-lists[1])
for i in range(3,n+1):
    a=10**10
    for j in range(1,k+1):
        if   i>j :
            a=min(a,mini_list[i-j]+abs(lists[i-1]-lists[i-1-j]))
    mini_list[i]=a
print(mini_list[-1])

Fixed submission:
#flog2
n,k=map(int,input().split())
lists=list(map(int,input().split()))
mini_list=[0 for i in range(n+1)]
#mini_list[i]=iだんめに行くまでに払う最小のコスト
#帰るには一段上がるか、、、、、K段上がるかのK通りで、それぞれの値を計算してそれのmin値を採用すればいい
mini_list[1]=0
mini_list[2]=abs(lists[0]-lists[1])
for i in range(3,n+1):
    a=10**10
    for j in range(1,k+1):
        if   i>j :
            a=min(a,mini_list[i-j]+abs(lists[i-1]-lists[i-1-j]))
        else:
            break
    mini_list[i]=a
print(mini_list[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = list(map(int, input().split()))
# dp[x][y][Person]:= 左端がx 番目,右端がy 番目の時の,この時動かすのがPersonの時の X - Y の値(0<=x<=Y<N)
dp = [[[0, 0] for j in range(N)] for i in range(N)]
for i in range(N):
    dp[i][i][0] = a[i]
    dp[i][i][1] = -a[i]

for i in range(1, N+1):
    # y-x = i  thus y = x+i  0<=x<N and 0<=x+i<N thus 0<=x <N-i
    for x in range(N-i):
        dp[x][x+i][0] = max(a[x]+dp[x+1][x+i][1], a[x+i]+dp[x][x+i-1][1])
        dp[x][x+i][1] = min(dp[x+1][x+i][0]-a[x], dp[x][x+i-1][0]-a[x+i])

ans = dp[0][N-1][0]
print(ans)

Fixed submission:
N = int(input())
a = list(map(int, input().split()))
dp = [[0]*(2*N) for i in range(N)]
for i in range(N):
    dp[i][i] = a[i]
    dp[i][i+N] = -a[i]

for i in range(1, N+1):
    for x in range(N-i):
        dp[x][x+i] = max(a[x]+dp[x+1][x+i+N], a[x+i]+dp[x][x+i-1+N])
        dp[x][x+i+N] = min(dp[x+1][x+i]-a[x], dp[x][x+i-1]-a[x+i])
ans = dp[0][N-1]
print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
lists=[]
for i in range(n):
	s=int(input())
  	lists.append(s)
if all(lists[i]%2==0 for i in range(n)):
  print("second")
else:
  print("first")

Fixed submission:
n=int(input())
lists=[]
for i in range(n):
    s=int(input())
    lists.append(s)
if all(lists[i]%2==0 for i in range(n)):
    print("second")
else:
    
    print("first")