Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
r,c,k = list(map(int, input().split()))

dp=[[[0]*4 for _ in range(c)] for _ in range(r)]


F = [[0]*c for _ in range(r)]

for _ in range(k):
  x,y,v = list(map(int, input().split()))
  x-=1
  y-=1
  F[x][y] = v
  
for i in range(r):
  for j in range(c):

    val = F[i][j]
  
      
    mxv = max(dp[i-1][j][0], dp[i-1][j][1], dp[i-1][j][2], dp[i-1][j][3],0)

    dp[i][j][3] = max(dp[i][j-1][3], dp[i][j-1][2] + val)
    dp[i][j][2] = max(dp[i][j-1][2], dp[i][j-1][1] + val)
    dp[i][j][1] = max(dp[i][j-1][1], dp[i][j-1][0] + val, mxv + val)
    dp[i][j][0] = mxv

best = 0

for j in range(c-1,c):
  for k in range(4):
    best = max(best, dp[-1][j][k])
    
print(best)

Fixed submission:
r,c,k = list(map(int, input().split()))
import copy
dp=[[[0]*4 for _ in range(c)] for _ in range(2)]


F = [[0]*c for _ in range(r)]

for _ in range(k):
  x,y,v = list(map(int, input().split()))
  x-=1
  y-=1
  F[x][y] = v
  
for nn in range(r):
  for j in range(c):
    i = 1
    val = F[nn][j]
  
      
    mxv = max(dp[i-1][j][0], dp[i-1][j][1], dp[i-1][j][2], dp[i-1][j][3],0)

    dp[i][j][3] = max(dp[i][j-1][3], dp[i][j-1][2] + val)
    dp[i][j][2] = max(dp[i][j-1][2], dp[i][j-1][1] + val)
    dp[i][j][1] = max(dp[i][j-1][1], dp[i][j-1][0] + val, mxv + val)
    dp[i][j][0] = mxv

  dp[0] = dp[1] 
  dp[1] = [[0]*4 for _ in range(c)]

best = 0


for k in range(4):
  best = max(best, dp[0][c-1][k])
    
print(best)

Buggy python submission (verdict: Time Limit Exceeded):
r,c,k = list(map(int, input().split()))

dp=[[[0]*4 for _ in range(c)] for _ in range(r)]

F = {}

for _ in range(k):
  x,y,v = list(map(int, input().split()))
  x-=1
  y-=1
  F[(x,y)] = v
  
for i in range(r):
  for j in range(c):
    if (i,j) in F:
      val = F[(i,j)]
    else:
      val = 0
      
    mxv = max(dp[i-1][j][0], dp[i-1][j][1], dp[i-1][j][2], dp[i-1][j][3],0)

    dp[i][j][3] = max(dp[i][j-1][3], dp[i][j-1][2] + val)
    dp[i][j][2] = max(dp[i][j-1][2], dp[i][j-1][1] + val)
    dp[i][j][1] = max(dp[i][j-1][1], dp[i][j-1][0] + val, mxv + val)
    dp[i][j][0] = mxv
    #print(dp[i])
    
best = 0

for j in range(c-1,c):
  for k in range(4):
    best = max(best, dp[-1][j][k])
    
print(best)

Fixed submission:
r,c,k = list(map(int, input().split()))
import copy
dp=[[[0]*4 for _ in range(c)] for _ in range(2)]


F = [[0]*c for _ in range(r)]

for _ in range(k):
  x,y,v = list(map(int, input().split()))
  x-=1
  y-=1
  F[x][y] = v
  
for nn in range(r):
  for j in range(c):
    i = 1
    val = F[nn][j]
  
      
    mxv = max(dp[i-1][j][0], dp[i-1][j][1], dp[i-1][j][2], dp[i-1][j][3],0)

    dp[i][j][3] = max(dp[i][j-1][3], dp[i][j-1][2] + val)
    dp[i][j][2] = max(dp[i][j-1][2], dp[i][j-1][1] + val)
    dp[i][j][1] = max(dp[i][j-1][1], dp[i][j-1][0] + val, mxv + val)
    dp[i][j][0] = mxv

  dp[0] = dp[1] 
  dp[1] = [[0]*4 for _ in range(c)]

best = 0


for k in range(4):
  best = max(best, dp[0][c-1][k])
    
print(best)
Buggy python submission (verdict: Runtime Error):
n,k = list(map(int,input().split()))
f = list(map(int,input().split()))

s = (10**9) // 2
step = s
best= 999999999999
import math

for j in range(50):
  c = 0
  arr = list(f)
  for i in range(n):
    c += arr[i] // s
    arr[i] /= (c+1)
    
  step = step//2
  step = max(1, step)
 
  if c<=k:
    s -= step
    best = min(best,math.ceil(max(arr)))
  else:
    s += step
      
print(best)

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

s = (10**9) // 2
step = s
best= 999999999999
import math

for j in range(50):
  c = 0
  arr = list(f)

  for i in range(n):
    if arr[i] > s:
      v = 0
      if arr[i] % s != 0:
        c += arr[i] // s
        v += arr[i] // s
      else:
        c += arr[i] // s
        v += arr[i] // s
        c -= 1
        v -= 1
      cor = 0
      if arr[i] % (v+1) != 0:
        cor = 1
      arr[i] = arr[i]//(v+1) + cor
    
  step = step//2
  step = max(1, step)
 
  if c<=k:
    best = min(best,max(arr))
   # print(s,best)
    s -= step
  else:
    s += step
    
  if s==0:
    s=1
      
print(best)
Buggy python submission (verdict: Runtime Error):
s = list(input())
k = int(input())
n = len(s)
s += ' '

l = []
cnt = 1
for i in range(1, n + 1):
    if s[i - 1] != s[i]:
        l.append(cnt)
        cnt = 1
    else:
        cnt += 1
m = sum(map(lambda li: li // 2, l))
if s[0] == s[-2]:
    if len(l) == 1:
        ans = k * n // 2
    elif l[0] % 2 == l[-1] % 2 == 1:
        ans = k * m + k - 1
    else:
        ans = k * m
print(ans)

Fixed submission:
s = list(input())
k = int(input())
n = len(s)
s.append(' ')

l = []
cnt = 1
for i in range(1, n + 1):
    if s[i - 1] != s[i]:
        l.append(cnt)
        cnt = 1
    else:
        cnt += 1
m = sum(map(lambda li: li // 2, l))
if len(l) == 1:
    ans = k * n // 2
elif s[0] == s[-2] and l[0] % 2 == l[-1] % 2 == 1:
    ans = k * m + k - 1
else:
    ans = k * m
print(ans)
Buggy python submission (verdict: Runtime Error):
from math import gcd

a, b = map(int, input().split())
d = gcd(a, b)

ans = 1
n = d
for i in range(2, d + 1):
    if n % i == 0:
        ans += 1
        while n % i == 0:
            n //= i
    if n < i * i:
        if 1 < n:
            ans += 1
        break
print(ans)

Fixed submission:
from fractions import gcd

a, b = map(int, input().split())
d = gcd(a, b)

ans = 1
n = d
for i in range(2, d + 1):
    if n % i == 0:
        ans += 1
        while n % i == 0:
            n //= i
    if n < i * i:
        if 1 < n:
            ans += 1
        break
print(ans)

Buggy python submission (verdict: Runtime Error):
from math import gcd

a, b = map(int, input().split())
d = gcd(a, b)

ans = 1
n = d
for i in range(2, d + 1):
    if n % i == 0:
        ans += 1
        while n % i == 0:
            n //= i
    if n < i * i:
        if 1 < n:
            ans += 1
        break
print(ans)

Fixed submission:
from fractions import gcd

a, b = map(int, input().split())
d = gcd(a, b)

ans = 1
n = d
for i in range(2, d + 1):
    if n % i == 0:
        ans += 1
        while n % i == 0:
            n //= i
    if n < i * i:
        if 1 < n:
            ans += 1
        break
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def f(s):
    if s == 0:
        return (0, 0)
    a = s
    b = 1
    k = 2
    while k**2 < 1e9:
        if a <= 1e9 and b <= 1e9:
           break
        if a % k == 0:
            a //= k
            b *= k
        else:
            k += 1
    return (a, b)

s = int(input())
for i in range(100000):
    a, d = f(s - i)
    b, c = f(i)
    if max(a, b, c, b + d) <= 1e9:
        print("%d 0 %d %d 0 %d" % (a, c, b + d, b))
        break

Fixed submission:
ps = [2]
for i in range(3, int(1e9**0.5)):
    n = i
    for p in ps:
        if n % p == 0:
            n //= p
            break
    if n == i:
        ps.append(n)



def f(s):
    if s == 0:
        return (0, 0)
    a = s
    b = 1
    i = 0
    while i < len(ps):
        if a <= 1e9 and b <= 1e9:
            break
        p = ps[i]
        if a % p == 0 and 1e9 < b * p:
            break
        if a % p == 0:
            a //= p
            b *= p
        else:
            i += 1
    return (a, b)

s = int(input())

l = 0
r = s
while l + 1 < r:
    m = (l + r) // 2
    if m ** 2 < s:
        l = m
    else:
        r = m
ds = r**2 - s

a, b = f(ds)
print("0 0 %d %d %d %d" % (r, a, b, r))
Buggy python submission (verdict: Runtime Error):
khabarovsk 20
n = int(input())
dict = {}
for i in range(n):
    s, p = input().split()
    if s not in dict:
        dict[s] = []
    dict[s].append((int(p), i + 1))

for s in sorted(dict.keys()):
    for (p, i) in reversed(sorted(dict[s])):
        print(i)

Fixed submission:
n = int(input())
dict = {}
for i in range(n):
    s, p = input().split()
    if s not in dict:
        dict[s] = []
    dict[s].append((int(p), i + 1))

for s in sorted(dict.keys()):
    for (p, i) in reversed(sorted(dict[s])):
        print(i)
Buggy python submission (verdict: Runtime Error):
from math import gcd

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

if n == 1:
    ans = 1000000000
elif n == 2:
    ans = max(a)
else:
    l = [a[0]]
    for i in range(1, n):
        l.append(gcd(l[-1], a[i]))
    r = [a[-1]]
    for i in range(n - 1, -1, -1):
        r.append(gcd(r[-1], a[i]))
    r = list(reversed(r))
    ans = max(l[-2], r[1])
    for i in range(1, n - 1):
        ans = max(ans, gcd(l[i - 1], r[i + 1]))
print(ans)

Fixed submission:
from fractions import gcd

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

if n == 1:
    ans = 1000000000
elif n == 2:
    ans = max(a)
else:
    l = [a[0]]
    for i in range(1, n):
        l.append(gcd(l[-1], a[i]))
    r = [a[-1]]
    for i in range(n - 1, -1, -1):
        r.append(gcd(r[-1], a[i]))
    r = list(reversed(r))
    ans = max(l[-2], r[1])
    for i in range(1, n - 1):
        ans = max(ans, gcd(l[i - 1], r[i + 1]))
print(ans)
Buggy python submission (verdict: Runtime Error):
n, p = map(int, input().split())

ans = 1
q = p
if n == 1:
    ans = p
else:
    for d in range(2, 1000001):
        cnt = 0
        while q % d == 0:
            q //= d
            cnt += 1
        if p < d**n:
            break
        ans *= d**(cnt // n)
print(ans)

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

ans = 1
if n == 1:
    ans = p
else:
    q = p
    for d in range(2, 1000001):
        if q < d**2:
            break
        cnt = 0
        while q % d == 0:
            q //= d
            cnt += 1
        ans *= d**(cnt // n)
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
ss = input().splist()

ans = "Three"

if any(ss[i] == 'Y' for i in range(n)):
    ans = "Four"

print(ans)

Fixed submission:
n = int(input())
ss = input().split()

ans = "Three"

if any(ss[i] == 'Y' for i in range(n)):
    ans = "Four"

print(ans)
Buggy python submission (verdict: Runtime Error):
s = str(input())
x, y = map(int, input().split())

n = 8000
fs = list(map(len, s.split('T')))
x -= fs[0]
dx = []
dy = []
for i in range(1, len(fs)):
    if fs[i] == 0:
        continue
    if i % 2 == 0:
        dx.append(fs[i])
    else:
        dy.append(fs[i])
dpx = [[False for _ in range(4 * n + 1)] for _ in range(2)]
dpy = [[False for _ in range(4 * n + 1)] for _ in range(2)]
dpx[0][2 * n] = True
dpy[0][2 * n] = True
for i in range(len(dx)):
    for j in range(4 * n + 1):
        if dpx[i % 2][j]:
            if 0 <= j - dx[i]:
                dpx[(i + 1) % 2][j - dx[i]] = True
            if j + dx[i] <= 4 * n:
                dpx[(i + 1) % 2][j + dx[i]] = True
for i in range(len(dy)):
    for j in range(4 * n + 1):
        if dpy[i % 2][j]:
            if 0 <= j - dy[i]:
                dpy[(i + 1) % 2][j - dy[i]] = True
            if j + dy[i] <= 4 * n:
                dpy[(i + 1) % 2][j + dy[i]] = True
ix = 2 * n + x
iy = 2 * n + y
if 0 <= ix <= 4 * n and dpx[len(dx) % 2][ix] and 0 <= iy <= 4 * n and dpy[len(dy) % 2][iy]:
    print("Yes")
else:
    print("No")

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

cnt = {}
for ai in a:
    if ai in cnt:
        cnt[ai] += 1
    else:
        cnt[ai] = 1

ans = 0
for k, v in cnt.items():
    if k < v:
        ans += v - k
    elif v < k:
        ans += v
print(ans)
Buggy python submission (verdict: Runtime Error):
n, m, k = map(int, input().split())
 
ans = "No"
for i in range(n + 1):
    for j in range(m + 1):
        if i * (m - j) + j * (n - i) == k:
            ans = "Yes"
print(ans)

Fixed submission:
s = list(input())
 
if 4 <= len(s) and s[:4] == list("YAKI"):
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
gr = {i:[] for i in range(1, n + 1)}
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    gr[a].append((b, c))
    gr[b].append((a, c))
q, k = map(int, input().split())
dmax = 10**14 + 1
dist = [dmax for _ in range(n + 1)]
dist[k] = 0
ls = [k]
while 0 < len(ls):
    u = ls[0]
    for v, c in gr[u]:
        if dist[v] == dmax:
            dist[v] = dist[u] + c
            ls.append(v)
    ls = ls[1:]

for _ in range(q):
    x, y = map(int, input().split())
    print(dist[x] + dist[y])

Fixed submission:
from collections import deque

n = int(input())
gr = { i:[] for i in range(1, n + 1)}
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    gr[a].append((b, c))
    gr[b].append((a, c))
q, k = map(int, input().split())
dmax = 10**14 + 1
dist = [dmax for _ in range(n + 1)]
dist[k] = 0
ls = deque([k])
while 0 < len(ls):
    u = ls[0]
    for v, c in gr[u]:
        if dist[v] == dmax:
            dist[v] = dist[u] + c
            ls.append(v)
    ls.popleft()

for _ in range(q):
    x, y = map(int, input().split())
    print(dist[x] + dist[y])
Buggy python submission (verdict: Runtime Error):
import fractions

n, k = map(int, input().split())
a = list(map(int, input().split()))

d = fractions.gcd(a[0], a[1])
for i in range(2, n):
    d = fractions.gcd(d, a[i])

ans = "IMPOSSIBLE"
for ai in a:
    if k <= ai and (ai - k) % d == 0:
        ans = "POSSIBLE"
        break
print(ans)

Fixed submission:
import fractions

n, k = map(int, input().split())
a = list(map(int, input().split()))

ans = "IMPOSSIBLE"

d = a[0]
for i in range(1, n):
    d = fractions.gcd(d, a[i])

for ai in a:
    if k <= ai and (ai - k) % d == 0:
        ans = "POSSIBLE"
        break
print(ans)
Buggy python submission (verdict: Runtime Error):
DEBUG = False
if DEBUG:
    N = int(input())

def check(n):
    print("? " + str(n), flush = True)
    if DEBUG:
        rtn = 'Y' if (n <= N) == (str(n) <= str(N)) else 'N'
        print(rtn)
        return rtn
    else:
        return input()

if check(10000000000) == 'Y':
    for i in range(11, 0, -1):
        n = 1
        tmp = 10**i - 1
        if check(tmp) == 'N':
            n = tmp + 1
            break
else:
    for i in range(1, 10):
        tmp = 10**i
        if check(tmp) == 'N':
            l = tmp // 10
            r = tmp - 1
            break
    while l + 1 < r:
        m = (l + r) // 2
        if check(10 * m) == 'Y':
            r = m
        else:
            l = m
    n = r

print("! "+ str(n), flush = True)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
s = [0]
ans = 1e18
for ai in a:
    s.append(s[-1] + ai)
for i in range(1, n):
    ans = min(ans, abs(s[i] - (s[-1] - s[i])))
print(ans)
Buggy python submission (verdict: Runtime Error):
def dist(r, c):
    return min(r, H - r - 1, c, W - c - 1)

H, W, K = map(int, input().split())
A = [list(input()) for _ in range(H)]

for r in range(H):
    for c in range(W):
        if A[r][c] == 'S':
            sr = r
            sc = c

dxy = [(1, 0), (0, -1), (-1, 0), (0, 1)]
pos = [(sr, sc)]
dic = {(sr, sc): K}
cnt = 0
ans = H * W
i = 0
while i < len(pos):
    r0, c0 = pos[i]
    d0 = dist(r0, c0)
    ans = min(ans, (d0 + K - 1) // K + 1)
    m0 = dic[(r0, c0)]
    if 0 < m0:
        m = m0 - 1
        for (dx, dy) in dxy:
            r = r0 + dy
            c = c0 + dx
            d = dist(r, c)
            if 0 <= r < H and 0 <= c < W and A[r][c] != '#' and (r, c) not in dic:
                pos.append((r, c))
                dic[(r, c)] = m
    i += 1

print(ans)

Fixed submission:
A, B, C = map(int, input().split())
dict = {}
ans = 0
while ans < 1000000:
    tpl = tuple(sorted([A, B, C]))
    if tpl in dict:
        ans = -1
        break
    elif A % 2 == 1 or B % 2 == 1 or C % 2 == 1:
        break
    dict[tpl] = True
    A, B, C = (B + C) // 2, (C + A) // 2, (A + B) // 2
    ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def dist(r, c):
    return min(r, H - r - 1, c, W - c - 1)

H, W, K = map(int, input().split())
A = [list(input()) for _ in range(H)]

for r in range(H):
    for c in range(W):
        if A[r][c] == 'S':
            sr = r
            sc = c

dxy = [(1, 0), (0, -1), (-1, 0), (0, 1)]
pos = [(sr, sc)]
dic = {(sr, sc): K}
cnt = 0
ans = H * W
while 0 < len(pos):
    r0, c0 = pos[0]
    pos = pos[1:]
    d0 = dist(r0, c0)
    ans = min(ans, (d0 + K - 1) // K + 1)
    m0 = dic[(r0, c0)]
    if 0 < m0:
        m = m0 - 1
        for (dx, dy) in dxy:
            r = r0 + dy
            c = c0 + dx
            d = dist(r, c)
            if 0 <= r < H and 0 <= c < W and A[r][c] != '#' and (r, c) not in dic:
                pos.append((r, c))
                dic[(r, c)] = m

print(ans)

Fixed submission:
def dist(r, c):
    return min(r, H - r - 1, c, W - c - 1)

H, W, K = map(int, input().split())
A = [list(input()) for _ in range(H)]

for r in range(H):
    for c in range(W):
        if A[r][c] == 'S':
            sr = r
            sc = c

dxy = [(1, 0), (0, -1), (-1, 0), (0, 1)]
pos = [(sr, sc)]
dic = {(sr, sc): K}
cnt = 0
ans = H * W
i = 0
while i < len(pos):
    r0, c0 = pos[i]
    d0 = dist(r0, c0)
    ans = min(ans, (d0 + K - 1) // K + 1)
    m0 = dic[(r0, c0)]
    if 0 < m0:
        m = m0 - 1
        for (dx, dy) in dxy:
            r = r0 + dy
            c = c0 + dx
            d = dist(r, c)
            if 0 <= r < H and 0 <= c < W and A[r][c] != '#' and (r, c) not in dic:
                pos.append((r, c))
                dic[(r, c)] = m
    i += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
Rmax = 0
Rmin = 1000000000
Bmax = 0
Bmin = 1000000000

N = int(input())
xs = []
ys = []
arr = []
for i in range(N):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)
    arr.append((max(x, y) / min(x, y), min(x, y), max(x, y)))

arr = list(sorted(arr))
for (_, x, y) in arr:
    Rmin0 = min(Rmin, x)
    Rmax0 = max(Rmax, x)
    Bmin0 = min(Bmin, y)
    Bmax0 = max(Bmax, y)
    p0 = (Rmax0 - Rmin0) * (Bmax0 - Bmin0)
    Rmin1 = min(Rmin, y)
    Rmax1 = max(Rmax, y)
    Bmin1 = min(Bmin, x)
    Bmax1 = max(Bmax, x)
    p1 = (Rmax1 - Rmin1) * (Bmax1 - Bmin1)
    if p0 <= p1:
        Rmin = Rmin0
        Rmax = Rmax0
        Bmin = Bmin0
        Bmax = Bmax0
    else:
        Rmin = Rmin1
        Rmax = Rmax1
        Bmin = Bmin1
        Bmax = Bmax1

ans = (Rmax - Rmin) * (Bmax - Bmin)
print(ans)

Fixed submission:
N, T = map(int, input().split())
ts = list(map(int, input().split()))

ans = sum([min(ts[i + 1] - ts[i], T) for i in range(N - 1)]) + T
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def cnt(str):
    rtn = 1
    for i in range(1, len(str)):
        if str[i] == str[0]:
            rtn += 1
        else:
            break
    return rtn

S = input()
T = input()
q = int(input())
ans = []
for _ in range(q):
    a, b, c, d = map(int, input().split())
    si = S[a - 1: b]
    ti = T[c - 1: d]
    ls = len(si)
    for c in list(si):
        if c == ti[0]:
            ls += 1
    while 0 < len(ti):
        ls *= 2
        lt = cnt(ti)
        ti = ti[lt:]
        while ls <= lt:
            ls *= 4
        ls -= lt
    if ls % 3 == 0:
        ans.append('YES')
    else:
        ans.append('NO')

for yn in ans:
    print(yn)


Fixed submission:
S = input()
T = input()
q = int(input())
ans = []

cnt = 0
sbs = [0]
for c in S:
    if c == 'B':
        cnt += 1
    sbs.append(cnt)
cnt = 0
tbs = [0]
for c in T:
    if c == 'B':
        cnt += 1
    tbs.append(cnt)

for _ in range(q):
    a, b, c, d = map(int, input().split())
    sb = sbs[b] - sbs[a - 1]
    tb = tbs[d] - tbs[c - 1]
    sa = (b - a) + sb
    if tb % 2 == 0:
        ta = (d - c - tb) + tb // 2
    else:
        ta = (d - c - tb) + (tb + 3) // 2
    if (sa - ta) % 3 == 0:
        ans.append('YES')
    else:
        ans.append('NO')

for yn in ans:
    print(yn)
Buggy python submission (verdict: Time Limit Exceeded):
INT_MIN = 0

def init(n_):
    n = 1
    while n < n_:
        n *= 2
    dat = [INT_MIN] * (2*n-1)
    return n, dat

def update(k, a):
    k += n-1
    dat[k] = a
    while k > 0:
        k = (k-1) // 2
        dat[k] = max(dat[k * 2 + 1], dat[k * 2 + 2])

def query(a, b, k, l, r):
    if r <= a or b <= l:
        return INT_MIN
    if a <= l and r <= b:
        return dat[k]
    else:
        vl = query(a, b, k*2+1, l, (l+r)//2)
        vr = query(a, b, k*2+2, (l+r)//2, r)
        return max(vl, vr)

N, K = map(int, input().split())
A = [int(input()) for i in range(N)]
MAX_Ai = 3*10**5+1
n, dat = init(MAX_Ai)
for ai in A:
    max_len = query(max(ai-K, 0), min(ai+K+1, MAX_Ai), 0, 0, n)
    update(ai, max_len+1)
ans = query(0, MAX_Ai, 0, 0, n)
print(ans)

Fixed submission:
INT_MIN = 0

def init(n_):
    n = 1
    while n < n_:
        n *= 2
    dat = [INT_MIN] * (2*n-1)
    return n, dat

def update(k, a):
    k += n-1
    dat[k] = a
    while k > 0:
        k = (k-1) // 2
        dat[k] = max(dat[k * 2 + 1], dat[k * 2 + 2])

def query(l, r, n):
    res = INT_MIN
    l += n
    r += n
    while l < r:
        if l & 1:
            res = max(res, dat[l-1])
            l += 1
        if r & 1:
            r -= 1
            res = max(res, dat[r-1])
        l >>= 1
        r >>= 1
    return res

N, K = map(int, input().split())
A = [int(input()) for i in range(N)]
MAX_Ai = 3*10**5+1
n, dat = init(MAX_Ai)

for ai in A:
    max_len = query(max(ai-K, 0), min(ai+K+1, MAX_Ai), n)
    update(ai, max_len+1)
ans = query(0, MAX_Ai, n)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 998244353
N, K = map(int, input().split())
L = []
R = []
for k in range(K):
    l, r = map(int, input().split())
    L += [l]
    R += [r]
# memo = [[0 for i in range(N+2)] for k in range(K)]
memo = [0 for i in range(N+2)]
memo[1] = 1
memo[2] = -1
cusum = 0
for i in range(1, N+1):
    cusum += memo[i]
    # print(cusum)
    for k in range(K):
        l, r = L[k], R[k]
        # for j in range(i+l, min(i+r+1, N+1)):
        #     memo[j] += memo[i]
        memo[min(i+l, N+1)] += cusum
        memo[min(i+r+1, N+1)] -= cusum
    # print(memo)
# for i in range(1, N+1):
#     for k in range(K):
#         memo[k][i+1] += memo[k][i]
print(cusum % MOD)

Fixed submission:
MOD = 998244353
N, K = map(int, input().split())
L = []
R = []
for k in range(K):
    l, r = map(int, input().split())
    L += [l]
    R += [r]
# memo = [[0 for i in range(N+2)] for k in range(K)]
memo = [0 for i in range(N+2)]
memo[1] = 1
memo[2] = -1
cusum = 0
for i in range(1, N+1):
    cusum = (cusum + memo[i]) % MOD
    # print(cusum)
    for k in range(K):
        l, r = L[k], R[k]
        # for j in range(i+l, min(i+r+1, N+1)):
        #     memo[j] += memo[i]
        memo[min(i+l, N+1)] += cusum
        memo[min(i+r+1, N+1)] -= cusum
    # print(memo)
# for i in range(1, N+1):
#     for k in range(K):
#         memo[k][i+1] += memo[k][i]
print(cusum % MOD)
Buggy python submission (verdict: Runtime Error):
import math
def eratos(n):
    isprime = [0 for i in range(n+1)]
    # isprime[0] = 0
    isprime[1] = 1
    for i in range(2, int(math.sqrt(n))+1):
        if isprime[i] == 0:
            j = i
            while j <= n:
                if isprime[j] == 0:
                    isprime[j] = i
                j = j + i
    return isprime

N = int(input())
A = list(map(int, input().split()))
isprime = eratos(10**6)
count = [0 for i in range(10**6+1)]
for ai in A:
    primes = {}
    while ai != 1:
        p = isprime[ai]
        primes[p] = 1
        ai //= p
    for p in primes.keys():
        count[p] += 1
max_c = max(count)
if max_c <= 1:
    print('pairwise coprime')
elif max_c == N:
    print('not coprime')
else:
    print('setwise coprime')

Fixed submission:
import math
def eratos(n):
    isprime = [i for i in range(n+1)]
    # isprime[0] = 0
    isprime[1] = 1
    for i in range(2, int(math.sqrt(n))+1):
        if isprime[i] == i:
            j = i
            while j <= n:
                if isprime[j] == j:
                    isprime[j] = i
                j = j + i
    return isprime

N = int(input())
A = list(map(int, input().split()))
isprime = eratos(10**6)
count = [0 for i in range(10**6+1)]
for ai in A:
    primes = {}
    while ai != 1:
        p = isprime[ai]
        primes[p] = 1
        ai //= p
    for p in primes.keys():
        count[p] += 1
max_c = max(count)
if max_c <= 1:
    print('pairwise coprime')
elif max_c == N:
    print('not coprime')
else:
    print('setwise coprime')