Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import heapq

n = int(input())
XL = [tuple(map(int, input().split())) for _ in range(n)]

blocked = [0] * n
total = 0
for i in range(n):
    ax, al = XL[i]
    for j in range(i + 1, n):
        bx, bl = XL[j]
        if ax - al < bx - bl < ax + al or ax - al < bx + bl < ax + al:
            blocked[i] -= 1
            blocked[j] -= 1
            total += 1
count = 0
heapq.heapify(blocked)
while total > 0:
    total += heapq.heappop(blocked)
    count += 1

print(n - count)


Fixed submission:
n = int(input())
LR = [None] * n
for i in range(n):
    x, l = map(int, input().split())
    LR[i] = (x - l, x + l)
LR.sort(key=lambda lr: lr[1])
count = 1
cur = LR[0][1]
for l, r in LR[1:]:
    if cur <= l:
        count += 1
        cur = r
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

n = int(input())
XL = [tuple(map(int, input().split())) for _ in range(n)]

blocked = [0] * n
total = 0
for i in range(n):
    ax, al = XL[i]
    for j in range(i + 1, n):
        bx, bl = XL[j]
        if ax - al < bx - bl < ax + al or ax - al < bx + bl < ax + al:
            blocked[i] -= 1
            blocked[j] -= 1
            total += 1
count = 0
heapq.heapify(blocked)
while total > 0:
    total += heapq.heappop(blocked)
    count += 1

print(n - count)


Fixed submission:
n = int(input())
LR = [None] * n
for i in range(n):
    x, l = map(int, input().split())
    LR[i] = (x - l, x + l)
LR.sort(key=lambda lr: lr[1])
count = 1
cur = LR[0][1]
for l, r in LR[1:]:
    if cur <= l:
        count += 1
        cur = r
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def solve(n, XL):
    blocked = [0] * n
    total = 0
    for i in range(n):
        ax, al = XL[i]
        for j in range(i + 1, n):
            bx, bl = XL[j]
            if ax - al < bx - bl < ax + al or ax - al < bx + bl < ax + al:
                blocked[i] -= 1
                blocked[j] -= 1
                total += 1
    count = 0
    heapq.heapify(blocked)
    while total > 0:
        total += heapq.heappop(blocked)
        count += 1
    return n - count

_n = int(input())
_XL = [list(map(int, input().split())) for _ in range(_n)]
print(solve(_n, _XL))


Fixed submission:
n = int(input())
LR = [None] * n
for i in range(n):
    x, l = map(int, input().split())
    LR[i] = (x - l, x + l)
LR.sort(key=lambda lr: lr[1])
count = 1
cur = LR[0][1]
for l, r in LR[1:]:
    if cur <= l:
        count += 1
        cur = r
print(count)
Buggy python submission (verdict: Runtime Error):
k, x = map(int, input())
print('Yes' if 500 * k >= x else 'No')

Fixed submission:
k, x = map(int, input().split())
print('Yes' if 500 * k >= x else 'No')
Buggy python submission (verdict: Runtime Error):
from itertools import product

n = int(input())

d = {}
for i in range(n):
  a = int(input())
  for _ in range(a):
    x, y = map(int, input().split())
    if i + 1 not in d:
      d[i + 1] = []
    d[i + 1].append((x, y))

ret = 0
for x in product((0, 1), repeat=n):
  tmp = [-1] * n
  ok = True
  for i in range(n):
    if x[i] == 1:
      for y in d[i + 1]:
        if tmp[y[0] - 1] == -1:
          tmp[y[0] - 1] = y[1]
        elif tmp[y[0] - 1] != y[1]:
          ok = False
          break
    if not ok:
      break
  if ok and all(a == b or b == -1 for a, b in zip(x, tmp)):
    ret = max(ret, sum(x))

print(ret)

Fixed submission:
from itertools import product

n = int(input())

d = {}
for i in range(n):
  a = int(input())
  for _ in range(a):
    x, y = map(int, input().split())
    if i + 1 not in d:
      d[i + 1] = []
    d[i + 1].append((x, y))

ret = 0
for x in product((0, 1), repeat=n):
  tmp = [-1] * n
  ok = True
  for i in range(n):
    if x[i] == 1 and i + 1 in d:
      for y in d[i + 1]:
        if tmp[y[0] - 1] == -1:
          tmp[y[0] - 1] = y[1]
        elif tmp[y[0] - 1] != y[1]:
          ok = False
          break
    if not ok:
      break
  if ok and all(a == b or b == -1 for a, b in zip(x, tmp)):
    ret = max(ret, sum(x))

print(ret)
Buggy python submission (verdict: Runtime Error):
x = int(input())
dp = [False] * (x + 1)
for i in range(100, 106):
    dp[i] = True
for i in range(106, x + 1):
    dp[i] = any(dp[i - j] for j in range(100, 106))
print(1 if dp[x] else 0)

Fixed submission:
x = int(input())
dp = [False] * max(106, x + 1)
for i in range(100, 106):
    dp[i] = True
for i in range(106, x + 1):
    dp[i] = any(dp[i - j] for j in range(100, 106))
print(1 if dp[x] else 0)
Buggy python submission (verdict: Runtime Error):
index(['SUN','MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT])print(7 - ['SUN','MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT'].index(input()))

Fixed submission:
print(7 - ['SUN','MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT'].index(input()))
Buggy python submission (verdict: Runtime Error):
m = int(input())
CD = [list(map(input().split())) for _ in range(m)]
count = 0
tmp = -1
total = 0
for c, d in CD:
  q, m = divmod(c * d, 9)
  count += q
  tmp += m
  if tmp >= 9:
    count += 1
    tmp %= 9
  total += d
print(total - 1 + count)

Fixed submission:
m = int(input())
CD = [list(map(int, input().split())) for _ in range(m)]
count = 0
tmp = -1
total = 0
for c, d in CD:
  q, m = divmod(tmp + c * d, 9)
  count += q
  tmp = m
  total += d
print(total - 1 + count)
Buggy python submission (verdict: Time Limit Exceeded):
def solve(x, y):
    if (x + y) % 3 != 0:
        return 0
    n = (x + y) // 3
    r = min((2 * y - x) // 3, (2 * x - y) // 3)
    return cmb(n, r, mod)

_x, _y = map(int, input().split())

mod = 10 ** 9 + 7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] # 逆元テーブル計算用テーブル

for i in range(2, _x + _y + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((- inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

def cmb(n, r, mod):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % mod

print(solve(_x, _y))


Fixed submission:
def solve(x, y):
    if (x + y) % 3 != 0:
        return 0
    n = (x + y) // 3
    r = min((2 * y - x) // 3, (2 * x - y) // 3)
    return cmb(n, r, mod)

_x, _y = map(int, input().split())

mod = 10 ** 9 + 7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] # 逆元テーブル計算用テーブル

for i in range(2, max(_x, _y) + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((- inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

def cmb(n, r, mod):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % mod

print(solve(_x, _y))

Buggy python submission (verdict: Runtime Error):

mod = 10 ** 9 + 7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] # 逆元テーブル計算用テーブル

for i in range(2, 10 ** 4 + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((- inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

def cmb(n, r, mod):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % mod

def solve(x, y):
    if (x + y) % 3 != 0:
        return 0
    n = (x + y) // 3
    r = min((2 * y - x) // 3, (2 * x - y) // 3)
    return cmb(n, r, mod)

_x, _y = map(int, input().split())
print(solve(_x, _y))


Fixed submission:
def solve(x, y):
    if (x + y) % 3 != 0:
        return 0
    n = (x + y) // 3
    r = min((2 * y - x) // 3, (2 * x - y) // 3)
    return cmb(n, r, mod)

_x, _y = map(int, input().split())

mod = 10 ** 9 + 7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] # 逆元テーブル計算用テーブル

for i in range(2, max(_x, _y) + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((- inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

def cmb(n, r, mod):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % mod

print(solve(_x, _y))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
L = list(map(int, input().split()))
L.sort()
count = 0
for i in range(n - 2):
  a = L[i]
  for j in range(i + 1, n - 1):
    b = L[j]
    l = j
    r = n
    while r - l > 1:
      p = (l + r) // 2
      if L[p] < a + b:
        l = p
      else:
        r = p
    count += l - j
print(count)


Fixed submission:
n = int(input())
L = list(map(int, input().split()))
L.sort()
count = 0
for i in range(n - 2):
  a = L[i]
  for j in range(i + 1, n - 1):
    b = L[j]
    l = j
    r = n
    while r - l > 1:
      p = (l + r) // 2
      if L[p] < a + b:
        l = p
      else:
        r = p
    count += l - j
print(count)
Buggy python submission (verdict: Runtime Error):
from fractions import gcd

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

a, b = map(int, input().split())
c = gcd(a, b)
count = 1
for num in primes(c):
  if c % num == 0:
    count += 1
print(count)

Fixed submission:
from math import ceil
from fractions import gcd

a, b = map(int, input().split())
c = gcd(a, b)
count = 1
for num in range(2, ceil(c**0.5) + 1):
  if c % num == 0:
    count += 1
    while c % num == 0:
      c = c // num
if c > 1:
  count += 1
print(count)
Buggy python submission (verdict: Runtime Error):
from math import factorial
from collections import OrderedDict

def solve(n, S):
    total = 0
    l = {}
    for s in S:
        key = ''.join(sorted(s))
        l[key] = (l[key] + 1) if key in l else 1
    for v in l.values():
        if v > 1:
            total += int(factorial(v) / factorial(2) / factorial(v - 2))
    return total

_n = int(input())
_S = [input() for _ in range(_n)]
print(solve(_n, _S))

Fixed submission:
from collections import defaultdict

def solve(n, S):
    counts = defaultdict(lambda: 0)
    for s in S:
        counts[''.join(sorted(list(s)))] +=  1
    total = 0
    for v in counts.values():
        if v > 1:
            total += int(v * (v - 1) / 2)
    return total

_n = int(input())
_S = [input() for _ in range(_n)]
print(solve(_n, _S))
Buggy python submission (verdict: Runtime Error):
n = int(input())
A = list(map(int, input().split()))
def check(L):
  for i in range(1, len(L)):
    if L[i] < L[i - 1]:
      return False
  return True
for i in range(n):
  for j in range(i + 1, n):
    if check(A[0:i] + [A[j]] + A[i+1:j] + [A[i]] + A[j+1:]):
      print('YES')
      return
print('NO')

Fixed submission:
def solve(n, A):
    def check(L):
        for i in range(1, len(L)):
            if L[i] < L[i - 1]:
                return False
        return True
    if check(A):
        return 'YES'
    for i in range(n):
        for j in range(i + 1, n):
            if check(A[0:i] + [A[j]] + A[i + 1:j] + [A[i]] + A[j + 1:]):
                return 'YES'
    return 'NO'

_n = int(input())
_A = list(map(int, input().split()))
print(solve(_n, _A))
Buggy python submission (verdict: Runtime Error):
def solve(n, m, A, BC):
    A.sort()
    BC.sort(key=lambda bc: -bc[1])
    i = 0
    finished = False
    for b, c in BC:
        for j in range(b):
            if A[i + j] < c:
                A[i + j] = c
            else:
                finished = True
                break
        if finished:
            break
        i += b
        if i >= n:
            break
    return sum(A)

_n, _m = map(int, input().split())
_A = list(map(int, input().split()))
_BC = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _A, _BC))

Fixed submission:
def solve(n, m, A, BC):
    # https://atcoder.jp/contests/abc127/tasks/abc127_d
    A.sort()
    BC.sort(key=lambda bc: -bc[1])
    i = 0
    finished = False
    for b, c in BC:
        for j in range(b):
            if i + j >= n:
                finished = True
                break
            if A[i + j] < c:
                A[i + j] = c
            else:
                finished = True
                break
        if finished:
            break
        i += b
    return sum(A)

_n, _m = map(int, input().split())
_A = list(map(int, input().split()))
_BC = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _A, _BC))

Buggy python submission (verdict: Runtime Error):
def solve(n, m, A, BC):
    A.sort()
    BC.sort(key=lambda bc: -bc[1])
    i = 0
    finished = False
    for b, c in BC:
        for j in range(b):
            if A[i + j] < c:
                A[i + j] = c
            else:
                finished = True
                break
        if finished:
            break
        i += b
    return sum(A)

_n, _m = map(int, input().split())
_A = list(map(int, input().split()))
_BC = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _A, _BC))

Fixed submission:
def solve(n, m, A, BC):
    # https://atcoder.jp/contests/abc127/tasks/abc127_d
    A.sort()
    BC.sort(key=lambda bc: -bc[1])
    i = 0
    finished = False
    for b, c in BC:
        for j in range(b):
            if i + j >= n:
                finished = True
                break
            if A[i + j] < c:
                A[i + j] = c
            else:
                finished = True
                break
        if finished:
            break
        i += b
    return sum(A)

_n, _m = map(int, input().split())
_A = list(map(int, input().split()))
_BC = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _A, _BC))
Buggy python submission (verdict: Runtime Error):
from math import ceil
n = int(input())

total = 0
for i in range(ceil(n ** 0.5) + 1):
  if n % (i + 1) == 0:
    a = n // (i + 1) - 1
    if n // a == n % a:
      total += a

print(total)

Fixed submission:
from math import ceil
n = int(input())

total = 0
for i in range(ceil(n ** 0.5) + 1):
  if n % (i + 1) == 0:
    a = n // (i + 1) - 1
    if a >= 2 and n // a == n % a:
      total += a

print(total)
Buggy python submission (verdict: Runtime Error):
s = input()
c0 = 0
c1 = 0
for i in range(s):
  if i % 2 == 0:
    if s[i] != '0':
      c0 += 1
    if s[i] != '1':
      c1 += 1
  else:
    if s[i] != '1':
      c0 += 1
    if s[i] != '0':
      c1 += 1
print(min(c0, c1))

Fixed submission:
s = input()
c0 = 0
c1 = 0
for i in range(len(s)):
  if i % 2 == 0:
    if s[i] != '0':
      c0 += 1
    if s[i] != '1':
      c1 += 1
  else:
    if s[i] != '1':
      c0 += 1
    if s[i] != '0':
      c1 += 1
print(min(c0, c1))
Buggy python submission (verdict: Time Limit Exceeded):
x, y, z, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
D = [0] * (x * y)
for i in range(x):
  for j in range(y):
    D[i * y + j] = A[i] + B[j]
D.sort(reverse=True)
E = [0] * (z * k)
size = min(x * y, k)
for i in range(z):
  for j in range(size):
    E[i * size + j] = C[i] + D[j]
E.sort(reverse=True)
print(*E[:k], sep='\n')

Fixed submission:
x, y, z, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
D = [0] * (x * y)
for i in range(x):
  for j in range(y):
    D[i * y + j] = A[i] + B[j]
D.sort(reverse=True)
E = [0] * (z * k)
size = min(x * y, k)
for i in range(z):
  for j in range(size):
    E[i * size + j] = C[i] + D[j]
E.sort(reverse=True)
print(*E[:k], sep='\n')
Buggy python submission (verdict: Runtime Error):
from collections import Counter
c = Counter(list(input())).values()
print(2 * min(c))
from collections import Counter
c = Counter(list(input())).values()
print(0 if len(c) == 1 else 2 * min(c))


Fixed submission:
from collections import Counter
c = Counter(list(input())).values()
print(0 if len(c) == 1 else 2 * min(c))
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):
    dp[i] = min(dp[i - j - 1] + abs(H[i] - H[i - j - 1]) for j in range(min(k, i)))

print(dp[n - 1])


Fixed submission:
n, k = map(int, input().split())
H = list(map(int, input().split()))
dp = [0] * n
for i in range(1, n):
    dp[i] = min(dp[i - j - 1] + abs(H[i] - H[i - j - 1]) for j in range(min(k, i)))

print(dp[n - 1])

Buggy python submission (verdict: Time Limit Exceeded):
def solve(n, k, H):
    dp = [0] * n
    dp[0] = 0
    for i in range(1, n):
        dp[i] = min(dp[i - j - 1] + abs(H[i] - H[i - j - 1]) for j in range(min(k, i)))
    return dp[n - 1]

_n, _k = map(int, input().split())
_H = list(map(int, input().split()))
print(solve(_n, _k, _H))


Fixed submission:
n, k = map(int, input().split())
H = list(map(int, input().split()))
dp = [0] * n
for i in range(1, n):
    dp[i] = min(dp[i - j - 1] + abs(H[i] - H[i - j - 1]) for j in range(min(k, i)))

print(dp[n - 1])
Buggy python submission (verdict: Time Limit Exceeded):
def solve(n, w, WV):
    dp = [[0] * (w + 1) for _ in range(n)]
    for w_limit in range(WV[0][0], w + 1):
        dp[0][w_limit] = WV[0][1]
    for i in range(1, n):
        for w_limit in range(1, w + 1):
            dw, dv = WV[i]
            if dw > w_limit:
                dp[i][w_limit] = dp[i - 1][w_limit]
            else:
                dp[i][w_limit] = max(dp[i - 1][w_limit], dp[i - 1][w_limit - dw] + dv)
    return dp[n - 1][w]

_n, _w = map(int, input().split())
_WV = [list(map(int, input().split())) for _ in range(_n)]
print(solve(_n, _w, _WV))


Fixed submission:
def solve(n, w, WV):
    dp = [[0] * (w + 1) for _ in range(n)]
    for w_limit in range(WV[0][0], w + 1):
        dp[0][w_limit] = WV[0][1]
    for i in range(1, n):
        for w_limit in range(1, w + 1):
            dw, dv = WV[i]
            if dw > w_limit:
                dp[i][w_limit] = dp[i - 1][w_limit]
            else:
                dp[i][w_limit] = max(dp[i - 1][w_limit], dp[i - 1][w_limit - dw] + dv)
    return dp[n - 1][w]

_n, _w = map(int, input().split())
_WV = [list(map(int, input().split())) for _ in range(_n)]
print(solve(_n, _w, _WV))
Buggy python submission (verdict: Runtime Error):
from math import gcd

def solve(n, x0, X):
    X = [abs(x - x0) for x in X]
    g = X.pop()
    for x in X:
        g = gcd(g, x)
    return g

_n , _x0 = map(int, input().split())
_X = map(int, input().split())
print(solve(_n, _x0, _X))


Fixed submission:
def solve(n, x0, X):

    def gcd(a, b):
        if a > b:
            a, b = b, a
        while a % b != 0:
            a, b = b, a % b
        return b

    X = [abs(x - x0) for x in X]
    g = X.pop()
    for x in X:
        g = gcd(g, x)
    return g

_n , _x0 = map(int, input().split())
_X = map(int, input().split())
print(solve(_n, _x0, _X))

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

def solve(n, x0, X):
    X = [x - x0 for x in X]
    g = X.pop()
    for x in X:
        g = math.gcd(g, x)
    return g

_n , _x0 = map(int, input().split())
_X = map(int, input().split())
print(solve(_n, _x0, _X))

Fixed submission:
def solve(n, x0, X):

    def gcd(a, b):
        if a > b:
            a, b = b, a
        while a % b != 0:
            a, b = b, a % b
        return b

    X = [abs(x - x0) for x in X]
    g = X.pop()
    for x in X:
        g = gcd(g, x)
    return g

_n , _x0 = map(int, input().split())
_X = map(int, input().split())
print(solve(_n, _x0, _X))
Buggy python submission (verdict: Runtime Error):
from math import floor

def solve(n, A):
    A.sort()
    b = A[n // 2 + 1]
    return sum(abs(a - (b + i + 1)) for i, a in enumerate(A))

_n = int(input())
_A = list(map(int, input().split()))
print(solve(_n, _A))


Fixed submission:
from math import floor

def solve(n, A):
    B = sorted([a - (i + 1) for i, a in enumerate(A)])
    b = B[n // 2]
    ret = sum(abs(a - (b + i + 1)) for i, a in enumerate(A))
    if n % 2 == 0:
        b = B[n // 2 + 1]
        tmp = sum(abs(a - (b + i + 1)) for i, a in enumerate(A))
        if tmp < ret:
            ret = tmp
    return ret

_n = int(input())
_A = list(map(int, input().split()))
print(solve(_n, _A))
Buggy python submission (verdict: Runtime Error):
from collections import Counter
n = int(input())
s = input()
c = Counter(s)
tmp = c['E'] - (1 if s[0] == 'E' else 0)
best = tmp
for i in range(1, n):
    if s[i - 1] == 'W'
        tmp += 1
    else:
        tmp -= 1
    if tmp < best:
        best = tmp
print(best)

Fixed submission:
from collections import Counter
n = int(input())
s = input()
c = Counter(s)
tmp = c['E']
best = tmp - (1 if s[0] == 'E' else 0)
for i in range(1, n):
    if s[i - 1] == 'W':
        tmp += 1
    else:
        tmp -= 1
    if tmp - (1 if s[i] == 'E' else 0) < best:
        best = tmp - (1 if s[i] == 'E' else 0)
print(best)
Buggy python submission (verdict: Runtime Error):
x = int(input())
print(max(i ** j for i in range(2, 34) for j in range(2, 11) if i ** j <= x))

Fixed submission:
x = int(input())
print(max(i ** j for i in range(1, 34) for j in range(2, 11) if i ** j <= x))
Buggy python submission (verdict: Time Limit Exceeded):
def solve(h, w, d, AA, q, LR):
    Ainv = {
        AA[y][x]: (x, y)
        for x in range(w)
        for y in range(h)
    }

    costs = [0] * q
    for i, (l, r) in enumerate(LR):
        while l != r:
            xf, yf = Ainv[l]
            xt, yt = Ainv[l + d]
            costs[i] += abs(xt - xf) + abs(yt - yf)
            l = AA[yt][xt]

    return costs

_h, _w, _d = map(int, input().split())
_AA = [list(map(int, input().split())) for _ in range(_h)]
_q = int(input())
_LR = [list(map(int, input().split())) for _ in range(_q)]
print(*solve(_h, _w, _d, _AA, _q, _LR), sep='\n')


Fixed submission:
def solve(h, w, d, AA, q, LR):
    Ainv = {
        AA[y][x]: (x, y)
        for x in range(w)
        for y in range(h)
    }
    costs = [0] * (h * w)
    for i in range(d , h * w):
        xf, yf = Ainv[i - d + 1]
        xt, yt = Ainv[i + 1]
        costs[i] = costs[i - d] + abs(xt - xf) + abs(yt - yf)

    ret = [0] * q
    for i, (l, r) in enumerate(LR):
        ret[i] = costs[r - 1] - costs[l - 1]

    return ret

_h, _w, _d = map(int, input().split())
_AA = [list(map(int, input().split())) for _ in range(_h)]
_q = int(input())
_LR = [list(map(int, input().split())) for _ in range(_q)]
print(*solve(_h, _w, _d, _AA, _q, _LR), sep='\n')
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

s = input().split('T')
dx = list(map(len, s[0::2]))
dy = list(map(len, s[1::2]))
lx = sum(dx)
ly = sum(dy)
x, y = map(int, input().split())

dp = [defaultdict(bool) for _ in range(len(dx))]
dp[0][dx[0]] = True
for i in range(1, len(dx)):
    for j in range(-lx, lx + 1):
        dp[i][j] = dp[i - 1][j - dx[i]] or dp[i - 1][j + dx[i]]

x_ok = dp[len(dx) - 1][x]

if len(dy) > 0:
    dp = [defaultdict(bool) for _ in range(len(dy))]
    dp[0][dy[0]] = True
    dp[0][-dy[0]] = True
    for i in range(1, len(dy)):
        for j in range(-ly, ly + 1):
            dp[i][j] = dp[i - 1][j - dy[i]] or dp[i - 1][j + dy[i]]
    y_ok = dp[len(dy) - 1][y]
else:
    y_ok = y == 0

print('Yes' if x_ok and y_ok else 'No')


Fixed submission:
s = input().split('T')
dx = list(map(len, s[0::2]))
dy = list(map(len, s[1::2]))
x, y = map(int, input().split())

def check(start, ds, goal):
    cands = {start}
    for d in ds:
        new_cands = set()
        for c in cands:
            new_cands.add(c - d)
            new_cands.add(c + d)
        cands = new_cands
    return goal in cands

x_ok = check(dx[0], dx[1:], x)
y_ok = check(0, dy, y)

print('Yes' if x_ok and y_ok else 'No')
Buggy python submission (verdict: Runtime Error):
from collections import Counter

def solve(n, A):
    c = Counter(A)
    cands = sorted(filter(lambda kv: kv[1] >= 2, c.items()),  key=lambda kv: -kv[0])
    ret = 0
    if cands[0][1] >= 4:
        ret = cands[0][0] * cands[0][0]
    elif len(cands) >= 2:
        ret = cands[0][0] * cands[1][0]
    return ret

_n = int(input())
_A = map(int, input().split())
print(solve(_n, _A))


Fixed submission:
from collections import Counter

def solve(n, A):
    c = Counter(A)
    cands = sorted(filter(lambda kv: kv[1] >= 2, c.items()),  key=lambda kv: -kv[0])
    ret = 0
    if len(cands) >= 1 and cands[0][1] >= 4:
        ret = cands[0][0] * cands[0][0]
    elif len(cands) >= 2:
        ret = cands[0][0] * cands[1][0]
    return ret

_n = int(input())
_A = map(int, input().split())
print(solve(_n, _A))