Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def comb_mod(n,r,m):
    ans = 1
    for i in range(1,r+1):
        ans *= (n-i+1) % m
        ans *= pow(i,m-2,m) % m
        ans = ans % m
    return ans
n,k = map(int,input().split())
m = 10**9+7
for i in range(1,k+1):
    print(comb_mod(n-k+1, i, m)*comb_mod(k-1, i-1, m)%m)

Fixed submission:
def factorial_mod(n,mod):
    ret = 1
    for i in range(1,n+1):
        ret *= i
        ret %= mod
    return ret
def comb_mod(n,r,mod):
    if r > n or r < 0:
        ret = 0
    else:
        fact_n  = factorial_mod(n, mod)
        fact_r  = factorial_mod(r, mod)
        fact_nr = factorial_mod(n-r, mod)
        ret = fact_n * pow(fact_r, mod-2, mod) * pow(fact_nr, mod-2, mod) % mod
    return ret

n,k = map(int,input().split())
m = 10**9+7
for i in range(1,k+1):
    print(comb_mod(n-k+1, i, m)*comb_mod(k-1, i-1, m)%m)

Buggy python submission (verdict: Time Limit Exceeded):
def comb_mod(n,r,m):
    ans = 1
    for i in range(1,r+1):
        ans *= (n-i+1) % m
        ans *= pow(i,m-2,m) % m
        ans = ans % m
    return ans
n,k = map(int,input().split())
m = 10**9+7
for i in range(1,k+1):
    print(comb_mod(n-k+1, i, m)*max(1,comb_mod(k-1, i-1, m))%m)

Fixed submission:
def factorial_mod(n,mod):
    ret = 1
    for i in range(1,n+1):
        ret *= i
        ret %= mod
    return ret
def comb_mod(n,r,mod):
    if r > n or r < 0:
        ret = 0
    else:
        fact_n  = factorial_mod(n, mod)
        fact_r  = factorial_mod(r, mod)
        fact_nr = factorial_mod(n-r, mod)
        ret = fact_n * pow(fact_r, mod-2, mod) * pow(fact_nr, mod-2, mod) % mod
    return ret

n,k = map(int,input().split())
m = 10**9+7
for i in range(1,k+1):
    print(comb_mod(n-k+1, i, m)*comb_mod(k-1, i-1, m)%m)

Buggy python submission (verdict: Time Limit Exceeded):
def comb_mod(n,r,m):
    ans = 1
    for i in range(1,r+1):
        ans *= (n-i+1) % m
        ans *= pow(i,m-2,m) % m
        ans = ans % m
    return ans
n,k = map(int,input().split())
m = 10**9+7
for i in range(1,k+1):
    print(comb_mod(n-k+1, i, m)*max(1,comb_mod(k-1, i-1, m))%m)

Fixed submission:
def factorial_mod(n,mod):
    ret = 1
    for i in range(1,n+1):
        ret *= i
        ret %= mod
    return ret
def comb_mod(n,r,mod):
    if r > n or r < 0:
        ret = 0
    else:
        fact_n  = factorial_mod(n, mod)
        fact_r  = factorial_mod(r, mod)
        fact_nr = factorial_mod(n-r, mod)
        ret = fact_n * pow(fact_r, mod-2, mod) * pow(fact_nr, mod-2, mod) % mod
    return ret

n,k = map(int,input().split())
m = 10**9+7
for i in range(1,k+1):
    print(comb_mod(n-k+1, i, m)*comb_mod(k-1, i-1, m)%m)
Buggy python submission (verdict: Runtime Error):
a,b,c,d = map(int,input().split())
import math
e =  (c*d) // math.gcd(c,d)
count = 0
if c != d:
    count =  (b-a)//c + (b-a)//d - (b-a)//e
else:
    count = (b-a)//c
print(b-a-count)

Fixed submission:
from fractions import gcd
a,b,c,d = map(int,input().split())
 
e = c*d//gcd(c,d)
A = (a-1)//c + (a-1)//d - (a-1)//e
B = b//c + b//d -b//e
print(b - a + 1 + A - B)
Buggy python submission (verdict: Runtime Error):
x,a = map(int,input().split())
print([0,10][x//a])

Fixed submission:
x,a = map(int,input().split())
if x < a:
    print(0)
else:
    print(10)
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
a = [0]*m
for i in range(m):
    a[i] = int(input())
s = 1
for i in range(m-1):
    if a[i+1] - a[i] == 1:
        s = 0
        break
if s == 0:
    print(0)
else:
    dp = [0]*(n+1)
    j = 0
    dp[0] = 1
    dp[1] = 1
    a = a + [0]
    for i in range(n-1):
        if a[j] == i+1:
            dp[i+2] = dp[i]
        elif a[j] == i:
            dp[i+2] = dp[i+1]
            j += 1
        else:
            dp[i+2] = dp[i+1] + dp[i]
    print(dp[-1]%1000000007)

Fixed submission:
n,m = map(int,input().split())
a = [0]*m
for i in range(m):
    a[i] = int(input())
s = 1
for i in range(m-1):
    if a[i+1] - a[i] == 1:
        s = 0
        break
if s == 0:
    print(0)
else:
    dp = [0]*(n+1)
    j = 0
    dp[0] = 1
    dp[1] = 1
    a = a + [-1]
    for i in range(n-1):
        if a[j] == i+1:
            dp[i+2] = dp[i]
        elif a[j] == i:
            dp[i+2] = dp[i+1]
            j += 1
        else:
            dp[i+2] = dp[i+1] + dp[i]
    print(dp[-1]%1000000007)
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = [0]*m
for i in range(m):
    bc[i] = list(map(int,input().split()))
sortsecond = lambda val : val[1]
bc.sort(key=sortsecond,reverse = True)
a = sorted(a)
i = 0
j = 0
count = 0
while a[i] < bc[j][1]:
    a[i] = bc[j][1]
    i += 1
    count += 1
    if count == bc[j][0]:
        j += 1
        count = 0
        if j>=m:
            break
print(sum(a))

Fixed submission:
n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = [0]*m
for i in range(m):
    bc[i] = list(map(int,input().split()))
sortsecond = lambda val : val[1]
bc.sort(key=sortsecond,reverse = True)
a = sorted(a)
i = 0
j = 0
count = 0
while a[i] < bc[j][1]:
    a[i] = bc[j][1]
    i += 1
    if i >= len(a):
        break
    count += 1
    if count == bc[j][0]:
        j += 1
        count = 0
        if j>=m:
            break
print(sum(a))
Buggy python submission (verdict: Time Limit Exceeded):
r,g,b,n = map(int,input().split())
c = 0
for i in range(n+1):
    for j in range(n+1):
        if (n-i*r-j*g) >= 0 and (n-i*r-j*g)%b == 0:
            c += 1
print(c)

Fixed submission:
r,g,b,n = map(int,input().split())
c = 0
for i in range(n+1):
    for j in range(n+1):
        if (n-i*r-j*g) >= 0 and (n-i*r-j*g)%b == 0:
            c += 1
print(c)
Buggy python submission (verdict: Time Limit Exceeded):
n,q = map(int,input().split())
s = input()
LR = [0]*q
for i in range(q):
    LR[i] = list(map(int,input().split()))
A = [0]*n
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        A[i] = 1
for i in range(q):
    print(sum(A[LR[i][0]-1:LR[i][1]-1]))

Fixed submission:
n,q = map(int,input().split())
s = input()
LR = [0]*q
for i in range(q):
    
    LR[i] = list(map(int,input().split()))
A = [0]*n
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        A[i+1] = 1
    A[i+1] += A[i]
for i in range(q):
    print(A[LR[i][1]-1]-A[LR[i][0]-1])
Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*n
for i in range(1,n):
    a = [0]*k
    for j in range(1,k+1):
        if i-j < 0:
            a[j-1] = 10**10
        else:
            a[j-1] = dp[i-j] + abs(h[i]-h[i-j])
    dp[i] = min(a)
print(dp[-1])

Fixed submission:
n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*n
for i in range(1,n):
    a = [0]*k
    for j in range(1,k+1):
        if i-j < 0:
            a[j-1] = 10**10
        else:
            a[j-1] = dp[i-j] + abs(h[i]-h[i-j])
    dp[i] = min(a)
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
n,w = map(int,input().split())
v = [0]*n
for i in range(n):
    v[i] = list(map(int,input().split()))
dp =  [[0 for j in range(w+1)] for i in range(n+1)]
for i in range(n):
    for j in range(w+1):
        if j - v[i][0] >= 0:
            if dp[i][j-v[i][0]] + v[i][1] > dp[i][j]:
                dp[i+1][j] = dp[i][j-v[i][0]] + v[i][1]
        dp[i+1][j] = max(dp[i+1][j],dp[i][j])
print(dp[-1][-1])

Fixed submission:
n,w = map(int,input().split())
v = [0]*n
for i in range(n):
    v[i] = list(map(int,input().split()))
dp =  [[0 for j in range(w+1)] for i in range(n+1)]
for i in range(n):
    for j in range(w+1):
        if j - v[i][0] >= 0:
            if dp[i][j-v[i][0]] + v[i][1] > dp[i][j]:
                dp[i+1][j] = dp[i][j-v[i][0]] + v[i][1]
        dp[i+1][j] = max(dp[i+1][j],dp[i][j])
print(dp[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
s=list(input())
count = 0
i = 0
while i<len(s)-1:
    if s[-1-i] == 'W' and s[-2-i] == 'B':
        s[-1-i] = 'B'
        s[-2-i] = 'W'
        count += 1
        i = i-1
    else:
        i += 1
print(count)

Fixed submission:
s=list(input())
count = 0
black = 0
for name in s:
    if name == 'B':
        black += 1
    else:
        count += black
print(count)
Buggy python submission (verdict: Runtime Error):
n = input()
a = 0
for i in range(len(n)):
    a += int(n[i])
print(["Yes","No"][int(n)%a])

Fixed submission:
n = input()
a = 0
for i in range(len(n)):
    a += int(n[i])
print(["Yes","No"][min(int(n)%a,1)])
Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
a = list(map(int,input().split()))
if k == n:
    print(1)
else:
    print(1+math.ceil((n-k)/(k-1)))

Fixed submission:
n,k = map(int,input().split())
a = list(map(int,input().split()))
import math
if k == n:
    print(1)
else:
    print(1+math.ceil((n-k)/(k-1)))
Buggy python submission (verdict: Runtime Error):
d,n = map(int,input().split())

if d == 0:
    if n == 100:
        print(101)
    else:
        if n == 100:
        print(n)
else:
    if n == 100:
        print(100**d * 101)
    else:
        print(100**d * n)

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

if d == 0:
    if n == 100:
        print(101)
    else:
        print(n)
else:
    if n == 100:
        print(100**d * 101)
    else:
        print(100**d * n)
Buggy python submission (verdict: Runtime Error):
h,w = map(int,input().split())
s = [0]*(h+2)
s[0] = ["."]*(w+2)
s[-1] = ["."]*(w+2)
for i in range(1,w+1):
    s[i] = ["."] + list(input()) + ["."]
ans = 1
for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j] == "#":
            if s[i-1][j] == "." and s[i+1][j] == "." and s[i][j-1] == "." and s[i][j+1] == ".":
                ans = 0
                break
print(["No","Yes"][ans])

Fixed submission:
h,w = map(int,input().split())
s = [0]*(h+2)
s[0] = ["."]*(w+2)
s[-1] = ["."]*(w+2)
for i in range(1,h+1):
    s[i] = ["."] + list(input()) + ["."]
ans = 1
for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j] == "#":
            if s[i-1][j] == "." and s[i+1][j] == "." and s[i][j-1] == "." and s[i][j+1] == ".":
                ans = 0
                break
print(["No","Yes"][ans])
Buggy python submission (verdict: Runtime Error):
n,m,x = map(int,input().split())
a = list(map(int,input().split()))

for i in range(m):
    if a[i] > x:
        break
    y = i+1
for i in range(m):
    if a[-1-i] < x:
        break
    z = i+1
print(min([m-y,m-z]))

Fixed submission:
n,m,x = map(int,input().split())
a = list(map(int,input().split()))
y = 0
z = 0
for i in range(m):
    if a[i] > x:
        break
    y = i+1
for i in range(m):
    if a[-1-i] < x:
        break
    z = i+1
print(min([m-y,m-z]))
Buggy python submission (verdict: Runtime Error):
n = list(input())
s = 0
for a in n:
    s += int(a)

if len(n) >= 2:
    if int(n[0]) >= 2:
        print(max(s, (len(n)-1)*9+int(n[0])-1))
    else:
        print(max(s, (len(n)-1)*9))
else:
    print(int(n))

Fixed submission:
n = list(input())
s = 0
for a in n:
    s += int(a)

if len(n) >= 2:
    if int(n[0]) >= 2:
        print(max(s, (len(n)-1)*9+int(n[0])-1))
    else:
        print(max(s, (len(n)-1)*9))
else:
    print(int(n[0]))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
import numpy as np
a0 = np.array(a)
b0 = np.array(b)
c0 = np.array(c)
count = 0
for i in range(n):
    L_A = 0
    L_C = 0
    A = a0[a0<b[i]]
    L_A = len(A)
    C = c0[c0>b[i]]
    L_C = len(C)
    count += L_A*L_C
print(count)

Fixed submission:
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a = sorted(a)
b = sorted(b)
c = sorted(c)
count = 0
import bisect
for i in range(n):
    A = bisect.bisect_right(a,b[i]-1)
    C = bisect.bisect_left(c,b[i]+1)
    count += A*(n-C)
print(count)
Buggy python submission (verdict: Runtime Error):
n = int(input())
p = list(map(int,input().split()))
c = 0
for i in range(n):
    if p[i] == i+1:
        p[i],p[i+1] = p[i+1],p[i]
        c += 1
print(c)

Fixed submission:
n = int(input())
p = list(map(int,input().split()))
c = 0
for i in range(n-1):
    if p[i] == i+1:
        p[i],p[i+1] = p[i+1],p[i]
        c += 1
if p[n-1] == n:
    c += 1
print(c)
Buggy python submission (verdict: Runtime Error):
def lcm(a, b): #lcm(int, int)
    if a<b:
        a,b = b,a
    x = a*b
    r = a%b
    while r != 0:
        a = b
        b = r
        r = a % b
    return x//b
n = int(input())
t = [0]*n
for i in range(n):
    t[i] = int(input())
ans = lcm(t[0],t[1])
for i in range(2,n):
    ans = lcm(ans,t[i])
print(ans)

Fixed submission:
def lcm(a, b): #lcm(int, int)
    if a<b:
        a,b = b,a
    x = a*b
    r = a%b
    while r != 0:
        a = b
        b = r
        r = a % b
    return x//b
n = int(input())
t = [0]*n
for i in range(n):
    t[i] = int(input())
ans = t[0]
for i in range(1,n):
    ans = lcm(ans,t[i])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
V = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    V[a].append(b)
    V[b].append(a)
from collections import deque
q = deque([])
q.append(1)
reach = [0]*(n+1)
reach[0] = -1
while q:
    x = q.popleft()
    for v in V[x]:
        if reach[v] == 0:
            q.append(v)
            reach[v] = reach[x]+1
    if max(reach) >= 3:
        break
if reach[-1] == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Fixed submission:
n,m = map(int,input().split())
V = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    V[a].append(b)
    V[b].append(a)
W = V[1]
z = []
for x in W:
    z.append(V[x])
s = 0
for q in z:
    if n in q:
        s = 1
        break
if s == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
V = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    V[a].append(b)
    V[b].append(a)
from collections import deque
q = deque([])
q.append(1)
reach = [0]*(n+1)
reach[0] = -1
while q:
    x = q.popleft()
    for v in V[x]:
        if reach[v] == 0:
            q.append(v)
            reach[v] = reach[x]+1
    if max(reach) >= 3:
        break
if reach[-1] == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Fixed submission:
n,m = map(int,input().split())
V = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    V[a].append(b)
    V[b].append(a)
W = V[1]
z = []
for x in W:
    z.append(V[x])
s = 0
for q in z:
    if n in q:
        s = 1
        break
if s == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
Buggy python submission (verdict: Runtime Error):
n,p = map(int,input().split())
a = list(map(int,input().split()))

s = [0]*n
for i in range(n):
    if a[i]%2 == 0:
        s[i] = 0
    else:
        s[i] = 1
import collections
c = collections.Counter(s)
odd  = c[1]
even = c[0]
x = 0
i = 0
while  2*i+p <= even:
    x += comb(even, i, exact=True)
    i += 1
from scipy.special import comb
ans = 0
i = 0
while  2*i+p <= odd:
    ans += comb(odd, 2*i+p, exact=True)*x
    i += 1
if p == 0:
    print(ans)
else:
    print(ans*2)

Fixed submission:
import math
def comb(n, r): #comb(int, int)
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n,p = map(int,input().split())
a = list(map(int,input().split()))
a_even = 0
a_odd = 0
for i in range(n):
    if a[i]%2 == 0:
        a_even += 1
    else:
        a_odd += 1
ans = 0
if p%2 == 0:
    k = 0
    for i in range(10**10):
        if 2*i > a_odd:
            break
        k += comb(a_odd, 2*i)
    print(k*2**a_even)
else:
    k = 0
    for i in range(10**10):
        if 2*i+1 > a_odd:
            break
        k += comb(a_odd, 2*i+1)
    print(k*2**a_even)
Buggy python submission (verdict: Runtime Error):
h,w = map(int,input().split())
a = [0]*h
for i in range(h):
    a[i] = input().split()
for i in range(h+2):
    for j in range(w+2):
        if i == 0 or i == h+1:
            print('#',end='')
        elif j == 0 or j == w+1:
            print('#',end='')
        else:
            print(a[i-1][j-1],end='')
    print()

Fixed submission:
h,w = map(int,input().split())
C = [["#" for j in range(w+2)] for i in range(h+2)]
for i in range(h):
    C[i+1][1:] = list(input()) + ["#"]
for i in range(h+2):
    print("".join(C[i][:]))
Buggy python submission (verdict: Runtime Error):
sx,sy,tx,ty = map(int,input().split())
ans = ["U"]*(ty-sy) + ["R"]*(tx-sx) + ["D"]*(ty-sy) + ["L"]*(tx-sx+1) + ["U"]*(ty-sy+1) + ["R"]*(tx-sx+1) + ["D"] + ["R"] + ["D"]*(ty-sy+1) + ["L"]*(tx-sx+1) + ["U"]
print("".join(ans))

Fixed submission:
s = list(input())
s[5] = " "
s[13] = " "
print("".join(s))
Buggy python submission (verdict: Runtime Error):
s=input()
k=int(input())
ss = [0]*len(s)
for i in range(len(s)):
    if k >= 26:
        k = k + ord(s[i])-97-26
        ss[i] = "a"
    elif 97+26 - ord(s[i]) <= k:
        k = k + ord(s[i])-97-26
        ss[i] = "a"
    else:
        ss[i] = s[i]
if k != 0:
    ss[-1] = chr(ord(s[-1])+k)

for i in range(len(s)):
    print(ss[i],end='')
print()

Fixed submission:
def str_rotate(S,k): # str_rotate(str,int)
    if k >= 26:
        k = k%26
    if ord(S) + k > 123:
        S = chr(ord(S)+k-97)
    else:
        S = chr(ord(S)+k)
    return S

s = list(input())
k = int(input())
for i in range(len(s)):
    if k == 0:
        break
    if s[i] == "a":
        pass
    elif 123 - ord(s[i]) <= k:
        k -= 123 - ord(s[i])
        s[i] = "a"
    else:
        pass
s[-1] = str_rotate(s[-1],k)
print("".join(s))

Buggy python submission (verdict: Runtime Error):
s=input()
k=int(input())
ss = [0]*len(s)
for i in range(len(s)):
    if k >= 26:
        k = k + ord(s[i])-97-26
        ss[i] = 'a'
    elif 97+26 - ord(s[i]) <= k:
        k = k + ord(s[i])-97-26
        ss[i] = 'a'
    else:
        ss[i] = s[i]
ss[-1] = chr(ord(s[-1])+k)
#print((ss))

for i in range(len(s)):
    print(ss[i],end='')
print()

Fixed submission:
def str_rotate(S,k): # str_rotate(str,int)
    if k >= 26:
        k = k%26
    if ord(S) + k > 123:
        S = chr(ord(S)+k-97)
    else:
        S = chr(ord(S)+k)
    return S

s = list(input())
k = int(input())
for i in range(len(s)):
    if k == 0:
        break
    if s[i] == "a":
        pass
    elif 123 - ord(s[i]) <= k:
        k -= 123 - ord(s[i])
        s[i] = "a"
    else:
        pass
s[-1] = str_rotate(s[-1],k)
print("".join(s))
Buggy python submission (verdict: Runtime Error):

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


class SegTree:
    X_unit = 0
    X_f = max

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)


def main():
    n, k = input_int_list()
    segtree = SegTree(300000)
    for _ in range(n):
        a = input_int()

        val = segtree.fold(max(0, a - k), min(300000, a + k + 1))
        segtree.set_val(a, val + 1)

    print(segtree.X[1])

    return


if __name__ == "__main__":
    main()


Fixed submission:

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


class SegTree:
    X_unit = 0
    X_f = max

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)


def main():
    n, k = input_int_list()
    segtree = SegTree(500000)
    for _ in range(n):
        a = input_int()

        val = segtree.fold(max(0, a - k), min(500000, a + k + 1))
        segtree.set_val(a, val + 1)

    print(segtree.X[1])

    return


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    x, k, d = [int(i) for i in input().strip().split()]
    div = x // d
    if x <= d:
        even = x
        odd = abs(x - d)
        if k % 2 == 0:
            ans = even
        else:
            ans = odd
    else:
        if k <= div:
            ans = x - (d * k)
        else:
            k = k - div
            even = x % d
            odd = abs(d - even)
            if even == odd:
                ans = even
            elif k % 2 == 1 and odd < even:
                ans = odd
            elif k % 2 == 0 and even < odd:
                ans = even
    print(ans)
    return


if __name__ == "__main__":
    main()

Fixed submission:

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    x, k, d = [int(i) for i in input().strip().split()]
    div = x // d
    L = x - d * k
    R = x + d * k
    if L >= 0:
        print(L)
        return
    if R < 0:
        print(-R)
        return
    if k <= div:
        ans = x - (d * k)
    else:
        k = k - div
        even = x % d
        odd = abs(d - even)
        if k % 2 == 1:
            ans = odd
        else:
            ans = even
    print(ans)
    return


if __name__ == "__main__":
    main()