Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
ans = [0 for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            v = i*i+j*j+k*k+i*j+j*k+k*i
            if v >n:
                break
            ans[v]+=1
for i in range(n):
    print(ans[i+1])

Fixed submission:
N=int(input())
import math
ans=[0]*(N+1)
n=int(math.sqrt(N))+1
for i in range(1,n+1):
    if i*i +2*i >N:
        break
    for j in range(1,n+1):
        if i*i+j*j+i*j>N:
            break
        for k in range(1,n+1):
            if i*i+j*j+k*k+i*j+j*k+i*k>N:
                break
            else:
                #print(i*i+j*j+k*k+i*j+j*k+i*k,i,j,k)
                ans[i*i+j*j+k*k+i*j+j*k+i*k]+=1
for i in range(len(ans)):
    if i!= 0:
        print(ans[i])

Buggy python submission (verdict: Runtime Error):
N=int(input())
import math
ans=[0]*N
n=int(math.sqrt(N))+1
for i in range(1,n+1):
    if i*i +2*i >N:
        break
    for j in range(1,n+1):
        if i*i+j*j+i*j>N:
            break
        for k in range(1,n+1):
            if i*i+j*j+k*k+i*j+j*k+i*k>N:
                break
            else:
                #print(i*i+j*j+k*k+i*j+j*k+i*k,i,j,k)
                ans[i*i+j*j+k*k+i*j+j*k+i*k]+=1
for i in ans:
    print(i)

Fixed submission:
N=int(input())
import math
ans=[0]*(N+1)
n=int(math.sqrt(N))+1
for i in range(1,n+1):
    if i*i +2*i >N:
        break
    for j in range(1,n+1):
        if i*i+j*j+i*j>N:
            break
        for k in range(1,n+1):
            if i*i+j*j+k*k+i*j+j*k+i*k>N:
                break
            else:
                #print(i*i+j*j+k*k+i*j+j*k+i*k,i,j,k)
                ans[i*i+j*j+k*k+i*j+j*k+i*k]+=1
for i in range(len(ans)):
    if i!= 0:
        print(ans[i])
Buggy python submission (verdict: Runtime Error):
from decimal import Decimal
A,B = input().split()
A=Decimal(A)
B=Decimal(B)
AB=math.floor(A*B)
print(AB)

Fixed submission:
from decimal import Decimal
import math
A,B = input().split()
A=Decimal(A)
B=Decimal(B)
AB=math.floor(A*B)
print(AB)
Buggy python submission (verdict: Runtime Error):
import math

R=int(input())
print(2*math.pie*R)


Fixed submission:
import math
R=int(input())
print(2*R*math.pi)
Buggy python submission (verdict: Time Limit Exceeded):
import math
n, k = map(int, input().split())
aas = list(map(int, input().split()))
left = 1
right = 10**9
def judge(mid):
    cut = 0
    for i in aas:
        cut += math.ceil(i / mid) - 1
    if cut <= k:
        return True
    else:
        return False
while left < right:
    mid = (left + right) / 2
    if math.ceil(left) == math.ceil(right):
        break
    elif judge(mid):
        right = mid
    else:
        left = mid
print(math.ceil(left))

Fixed submission:
import math
n, k = map(int, input().split())
aas = list(map(int, input().split()))
diff = pow(10,-6)
left = 1
right = 10**9
def judge(mid):
    cut = 0
    for i in aas:
        cut += math.ceil(i / mid) - 1
    if cut <= k:
        return True
    else:
        return False
while left < right:
    mid = (left + right) / 2
    if (left <= right <= left + diff) or (right <= left <= right + diff):
        break
    elif judge(mid):
        right = mid
    else:
        left = mid
print(math.ceil(left))
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
aas = list(map(int, input().split()))
scores = []
cnt = 0
tmp = 1
for i in range(n):
    tmp *= aas[i]
    if i >= k-1:
        scores.append(tmp)
        tmp //= aas[i-(k-1)]
for i in range(1,len(scores)):
    if scores[i] > scores[i-1]:
        print('Yes')
    else:
        print('No')

Fixed submission:
n, k = map(int, input().split())
aas = list(map(int, input().split()))
scores = []
for i in range(k,n):
    if aas[i] > aas[i-k]:
        print('Yes')
    else:
        print('No')
Buggy python submission (verdict: Runtime Error):
#以下は上位者のコピー
n, k = map(int, input().split())
mod = 10 ** 9 + 7

from collections import deque

a = list(map(int, input().split()))
a.sort()
minus, zero, plus = 0, 0, 0
for i in range(n):
    if a[i] < 0:
        minus += 1
    elif a[i] == 0:
        zero += 1
    else:
        plus += 1

que = deque(a)

plus_flg = False
tmp = plus - k
if tmp >= 0:
    plus_flg = True
elif tmp*-2 > minus  :
    plus_flg = True

# plus可能
if plus_flg:
    ans = 1
    cnt = 0

    while cnt < k:
        if k - cnt >= 2:
            cnt += 2
            if que[0] * que[1] >= que[-1] * que[-2]:
                ans *= que.popleft()
                ans *= que.popleft()
                ans %= mod
            else:
                ans *= que.pop()
                ans *= que.pop()
                ans %= mod
        else:
            ans *= que.pop()
            ans %= mod
            cnt += 1

    print(ans)



# zero
elif zero > 0:
    print(0)

# minus
else:
    a = [abs(a[i]) for i in range(n)]
    a.sort()
    ans = 1
    for i in range(k):
        ans *= a[i]
        ans %= mod
    ans = -ans % mod
    print(ans)


Fixed submission:
n = int(input())
lis = sorted(list(map(int, input().split())),reverse=True)
idx = 0
res = lis[0]
while True:
    if idx >= n-2:
        break
    res += lis[1+idx//2]
    idx += 1
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
aas = list(map(int, input().split()))
from itertools import combinations as comb
res = -float('inf')
for p in comb(aas, k):
    res_tmp = 1
    for i in p:
        res_tmp *= i
    res = max(res, res_tmp)
print(int(res%1000000007))

Fixed submission:
n, k = map(int, input().split())
mod = 10 ** 9 + 7
from collections import deque

a = list(map(int, input().split()))
a.sort()
minus, zero, plus = 0, 0, 0
for i in range(n):
    if a[i] < 0:
        minus += 1
    elif a[i] == 0:
        zero += 1
    else:
        plus += 1

que = deque(a)

#ここを軽量化した
plus_flg = False
tmp = plus - k
if tmp >= 0:
    plus_flg = True
elif (-tmp <= minus and -tmp%2 == 0) or (-tmp < minus and plus >= 1):
    plus_flg = True

# plus可能
if plus_flg:
    ans = 1
    cnt = 0

    while cnt < k:
        if k - cnt >= 2:
            if que[0] * que[1] >= que[-1] * que[-2]:
                ans *= que.popleft()
                ans *= que.popleft()
                ans %= mod
                cnt += 2
            else:
                ans *= que.pop()
                ans %= mod
                cnt += 1
        else:
            ans *= que.pop()
            ans %= mod
            cnt += 1

    print(ans)



# zero
elif zero > 0:
    print(0)

# minus
else:
    a = [abs(a[i]) for i in range(n)]
    a.sort()
    ans = 1
    for i in range(k):
        ans *= a[i]
        ans %= mod
    ans = -ans % mod
    print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
import numpy
div = np.zeros(N+1, np.int64)
for n in range(1, N+1):
  for m in range(n, N+1, n):
    div[m] += m
print(sum(div))

Fixed submission:
n = int(input())
res = 0
for i in range(1, n + 1):
  d = n // i
  res += d * (d + 1) // 2 * i
print(res)
Buggy python submission (verdict: Runtime Error):
n = int(input())
aas = sorted(list(set(list(map(int, input().split())))))
aas_len = len(aas)
if aas_len == 1:
    print(0)
    exit()
aas_max = aas[-1]
arr = [1]*(aas_max+1)
for i in range(aas_len):
    if arr[aas[i]] == 0:
        continue
    idx = aas[i]*2
    while idx <= aas_max:
        arr[idx] = 0
        idx += aas[i]
res = 0
for i in aas:
    if arr[i] == 1:
        res += 1
print(res)

Fixed submission:
n = int(input())
aas = sorted(list(map(int, input().split())))
aas_len = len(aas)
if aas_len == 1:
    print(1)
    exit()
aas_max = aas[-1]
arr = [1]*(aas_max+1)
for i in range(aas_len):
    if arr[aas[i]] == 0:
        continue
    if arr[aas[i]] == 1:
        arr[aas[i]] = 2
    else:
        arr[aas[i]] = 0
        continue
    idx = aas[i]*2
    while idx <= aas_max:
        arr[idx] = 0
        idx += aas[i]
res = 0
for i in aas:
    if arr[i] != 0:
        res += 1
print(res)

Buggy python submission (verdict: Runtime Error):
n = int(input())
aas = list(set(sorted(list(map(int, input().split())))))
if len(aas) == 1:
    print(0)
    exit()
#aas_max = aas[-1]
i = 0
while i != len(aas):
    j = i + 1
    while j != len(aas):
        if aas[j]%aas[i] == 0:
            del aas[j]
        else:
            j += 1
    i += 1
print(len(aas))

Fixed submission:
n = int(input())
aas = sorted(list(map(int, input().split())))
aas_len = len(aas)
if aas_len == 1:
    print(1)
    exit()
aas_max = aas[-1]
arr = [1]*(aas_max+1)
for i in range(aas_len):
    if arr[aas[i]] == 0:
        continue
    if arr[aas[i]] == 1:
        arr[aas[i]] = 2
    else:
        arr[aas[i]] = 0
        continue
    idx = aas[i]*2
    while idx <= aas_max:
        arr[idx] = 0
        idx += aas[i]
res = 0
for i in aas:
    if arr[i] != 0:
        res += 1
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
aas = list(map(int, input().split()))
if 0 in aas:
    print(0)
    exit()
res = 1
for i in aas:
    res*=i
if res>10**18:
    print(-1)
else:
    print(res)

Fixed submission:
n = int(input())
aas = list(map(int, input().split()))
if 0 in aas:
    print(0)
    exit()
res = 1
for i in aas:
    res*=i
    if res > 10 ** 18:
        print(-1)
        exit()
else:
    print(res)
Buggy python submission (verdict: Time Limit Exceeded):
x = int(input())
n=100
tes = [0]
for i in range(-10001,10001):
    for j in range(-10001,10001):
        if pow(i,5) - pow(j,5) == x:
            print(str(i)+" "+str(j))
            exit()

Fixed submission:
x = int(input())
n=100
tes = [0]
for i in range(-250,250):
    for j in range(-250,250):
        if pow(i,5) - pow(j,5) == x:
            print(str(i)+" "+str(j))
            exit()

Buggy python submission (verdict: Runtime Error):
x = int(input())
n=100
tes = [0]
for i in range(-101,101):
    for j in range(-101,101):
        if pow(i,5) - pow(j,5) == x:
            print(str(i)+" "+str(j))
            exit()
print(tes[1])

Fixed submission:
x = int(input())
n=100
tes = [0]
for i in range(-250,250):
    for j in range(-250,250):
        if pow(i,5) - pow(j,5) == x:
            print(str(i)+" "+str(j))
            exit()
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()
rs = [0]*n
gs = [0]*n
bs = [0]*n
for i in reversed(range(n)):
    if s[i] == 'R':
        rs[i] += 1
    elif s[i] == 'G':
        gs[i] += 1
    else:
        bs[i] += 1
for i in reversed(range(n-1)):
    rs[i] += rs[i+1]
    gs[i] += gs[i+1]
    bs[i] += bs[i+1]
res = 0
for i in range(n):
    for j in range(i+1,n-1):
        if s[i] == s[j]:
            continue
        if s[i]!='B' and s[j]!='B':
            res += bs[j+1]
            if j-i+j < n:
                if s[j-i+j] == 'B':
                    res -=1
        elif s[i]!='G' and s[j]!='G':
            res += gs[j+1]
            if j - i + j < n:
                if s[j-i+j] == 'G':
                    res -=1
        else:
            res += rs[j+1]
            if j - i + j < n:
                if s[j-i+j] == 'R':
                    res -= 1
print(res)

Fixed submission:
n = int(input())
s = input()
rs = [0]*n
gs = [0]*n
bs = [0]*n
for i in reversed(range(n)):
    if s[i] == 'R':
        rs[i] += 1
    elif s[i] == 'G':
        gs[i] += 1
    else:
        bs[i] += 1
for i in reversed(range(n-1)):
    rs[i] += rs[i+1]
    gs[i] += gs[i+1]
    bs[i] += bs[i+1]
res = 0
for i in range(n):
    for j in range(i+1,n-1):
        if s[i] == s[j]:
            continue
        if s[i]!='B' and s[j]!='B':
            res += bs[j+1]
            if j-i+j < n:
                if s[j-i+j] == 'B':
                    res -=1
        elif s[i]!='G' and s[j]!='G':
            res += gs[j+1]
            if j - i + j < n:
                if s[j-i+j] == 'G':
                    res -=1
        else:
            res += rs[j+1]
            if j - i + j < n:
                if s[j-i+j] == 'R':
                    res -= 1
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()
res=0
for i in range(1000):
    digits=str(i)
    if i<100:
        digits='0'*(3-len(str(i)))+digits
        #print(digits)
    cnt = 0
    for j in s:
        if j==digits[cnt]:
            #print(digits)
            cnt+=1
        if cnt>=3:
            res+=1
            break
print(res)

Fixed submission:
n = int(input())
s = input()
res=0
for i in range(1000):
    digits=str(i)
    if i<100:
        digits='0'*(3-len(str(i)))+digits
        #print(digits)
    cnt = 0
    for j in s:
        if j==digits[cnt]:
            #print(digits)
            cnt+=1
        if cnt>=3:
            res+=1
            break
print(res)
Buggy python submission (verdict: Runtime Error):
n,a,b=map(int, input.split())
print(max(n*a,b))

Fixed submission:
n,a,b = map(int,input().split())
print(min(a * n, b))

Buggy python submission (verdict: Runtime Error):
n,a,b=map(int input.split())
print(max(n*a,b))

Fixed submission:
n,a,b = map(int,input().split())
print(min(a * n, b))
Buggy python submission (verdict: Runtime Error):
print('Yes' if len(set(input()))==2, 'No')

Fixed submission:
print('Yes' if len(set(input()))==2 else 'No')
Buggy python submission (verdict: Runtime Error):
x,a=map(int, input.split())
print('10' if x>=a else '0')

Fixed submission:
x,a=map(int, input().split())
print('10' if x>=a else '0')

Buggy python submission (verdict: Runtime Error):
x,a=map(int, input.split())
print(10 if x>=a else 0)

Fixed submission:
x,a=map(int, input().split())
print('10' if x>=a else '0')
Buggy python submission (verdict: Runtime Error):
import heapq
from itertools import accumulate
n, k = map(int, input().split())
vs = list(map(int, input().split()))
vs_hq = vs.copy()
rsw_l = list(accumulate(vs))
rsw_r = vs.copy()
for i in reversed(range(n-1)):
    rsw_r[i] = rsw_r[i+1] + rsw_r[i]
rsw_l = [0] + rsw_l
rsw_r = rsw_r + [0]
n_minus_l = [0]*n
if vs[0] < 0:
    n_minus_l[0] = 1
for i in range(1,n):
    if vs[i] < 0:
        n_minus_l[i] = n_minus_l[i-1] + 1
    else:
        n_minus_l[i] = n_minus_l[i - 1]
n_minus_l = [0] + n_minus_l
n_minus_r = [0]*n
if vs[n-1] < 0:
    n_minus_r[n-1] = 1
for i in reversed(range(n-1)):
    if vs[i] < 0:
        n_minus_r[i] = n_minus_r[i+1] + 1
    else:
        n_minus_r[i] = n_minus_r[i+1]
n_minus_r = n_minus_r + [0]
res = 0
for i in range(min(n,k)+1):
    for j in range(k-i+1):
        tmp = rsw_l[i] + rsw_r[n-j]
        n_dis = min(k-i-j,n_minus_l[i]+n_minus_r[n-j])
        arr = []
        if i > 0:
            arr += vs[:i]
        if j > 0:
            arr += list(reversed(vs))[:j]
        if arr != []:
            tmp -= sum(sorted(arr)[:n_dis])
        res = max(res,tmp)
print(res)

Fixed submission:
from itertools import accumulate
n, k = map(int, input().split())
vs = list(map(int, input().split()))
res = 0
for i in range(min(n,k)+1):
    for j in range(min(n-i,k-i)+1):
        res_tmp = 0
        arr = []
        if i > 0:
            arr += vs[:i]
        if j > 0:
            arr += vs[(n-j):]
        if arr != []:
            arr.sort()
            n_len = len(arr)
            for m in range(min(k-i-j,n_len)):
                if arr[m] >= 0:
                    break
                res_tmp -= arr[m]
            res_tmp += sum(arr)
        res = max(res,res_tmp)
print(res)
Buggy python submission (verdict: Runtime Error):
import heapq
n, m = map(int, input().split())
aas = list(map(int, input().split())).sort()
hq = []
for i in range(m):
    b, c = map(int, input().split())
    heapq.heappush(hq,(-c,b))
i = 0
while hq:
    -c, b = heapq.heappop(hq)
    for j in range(i,min(n,i+b)):
        if aas[j] < c:
            aas[j] = c
        else:
            print(sum(aas))
            exit()
    i = j + 1
print(sum(aas))

Fixed submission:
import heapq
n, m = map(int, input().split())
aas = sorted(list(map(int, input().split())))
hq = []
for i in range(m):
    b, c = map(int, input().split())
    heapq.heappush(hq,(-c,b))
i = 0
while hq:
    c, b = heapq.heappop(hq)
    c = -c
    for j in range(i,min(n,i+b)):
        if aas[j] < c:
            aas[j] = c
        else:
            print(sum(aas))
            exit()
    i = j + 1
print(sum(aas))

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n, m = map(int, input().split())
aas = list(map(int, input().split()))
for i in range(m):
    b, c = map(int, input().split())
    aas.sort()
    idx = bisect.bisect_left(aas, c)
    if idx >= b:
        aas = [c]*b + aas[b:]
    else:
        aas = [c]*idx + aas[idx:]
print(sum(aas))

Fixed submission:
import heapq
n, m = map(int, input().split())
aas = sorted(list(map(int, input().split())))
hq = []
for i in range(m):
    b, c = map(int, input().split())
    heapq.heappush(hq,(-c,b))
i = 0
while hq:
    c, b = heapq.heappop(hq)
    c = -c
    for j in range(i,min(n,i+b)):
        if aas[j] < c:
            aas[j] = c
        else:
            print(sum(aas))
            exit()
    i = j + 1
print(sum(aas))

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n, m = map(int, input().split())
aas = list(map(int, input().split()))
for i in range(m):
    b, c = map(int, input().split())
    aas.sort()
    idx = bisect.bisect_left(aas, c)
    if idx >= b:
        aas = [c]*b + aas[b:]
    else:
        aas = [c]*idx + aas[idx:]
print(sum(aas))

Fixed submission:
import heapq
n, m = map(int, input().split())
aas = sorted(list(map(int, input().split())))
hq = []
for i in range(m):
    b, c = map(int, input().split())
    heapq.heappush(hq,(-c,b))
i = 0
while hq:
    c, b = heapq.heappop(hq)
    c = -c
    for j in range(i,min(n,i+b)):
        if aas[j] < c:
            aas[j] = c
        else:
            print(sum(aas))
            exit()
    i = j + 1
print(sum(aas))
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
s=input()
if s[k-1]=='A':
  s[k-1]='a'
elif s[k-1]=='B':
  s[k-1]='b'
else:
  s[k-1]='c'
print(s)


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

print(s[:k-1]+s[k-1].lower()+s[k:])

Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
s=input()
if s[k-1]=='A':
  s[k-1]='a'
elif s[k-1]=='B':
  s[k-1]='b'
else:
  s[k-1]='c':
print(s)

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

print(s[:k-1]+s[k-1].lower()+s[k:])
Buggy python submission (verdict: Runtime Error):
aas = [int(input()) for _ in range(5)]
k = int(input())
for i in range(1,5):
  if aas[i]-aas[i-1]>k:
    print(':(')
    exit()
print('Yay!)

Fixed submission:
aas = [int(input()) for _ in range(5)]
k = int(input())
print('Yay!' if max(aas)-min(aas)<=k else ':(')
Buggy python submission (verdict: Runtime Error):
n = int(input())
if n == 1:
    print('Yes')
    prnt(2)
    print("1")
    print("1")
    exit()
t = [3]
cnt = 3
while t[-1]+cnt <= n:
    t.append(t[-1]+cnt)
    cnt += 1
if t[-1] != n:
    print('No')
    exit()
print('Yes')
try:
    n_cols = t[-1]-t[-2]
except:
    print(3)
    print("2 1 2")
    print("2 3 1")
    print("2 2 3")
    exit()
print(n_cols+1)
t_len = len(t)
t2 = [i+1 for i in t]
t3 = [0 for i in t]
for col in range(n_cols+1):
    out = str(n_cols)
    if col <=2:
        if col == 0:
            out += " 1 2"
        elif col == 1:
            out += " 1 3"
        elif col == 2:
            out += " 2 3"
    else:
        idx = t[col-3]+1
        while idx <= t[col-2]:
            out += " " + str(idx)
            idx += 1
    for i in range(t_len-1):
        if t2[i] != t[i+1]+1:
            out += " " + str(t2[i])
            t2[i] += 1
    print(out)

Fixed submission:
n = int(input())
if n == 1:
    print('Yes')
    print(2)
    print("1 1")
    print("1 1")
    exit()
t = [3]
cnt = 3
while t[-1]+cnt <= n:
    t.append(t[-1]+cnt)
    cnt += 1
if t[-1] != n:
    print('No')
    exit()
print('Yes')
try:
    n_cols = t[-1]-t[-2]
except:
    print(3)
    print("2 1 2")
    print("2 3 1")
    print("2 2 3")
    exit()
print(n_cols+1)
t_len = len(t)
t2 = [i+1 for i in t]
t3 = [0 for i in t]
for col in range(n_cols+1):
    out = str(n_cols)
    if col <=2:
        if col == 0:
            out += " 1 2"
        elif col == 1:
            out += " 1 3"
        elif col == 2:
            out += " 2 3"
    else:
        idx = t[col-3]+1
        while idx <= t[col-2]:
            out += " " + str(idx)
            idx += 1
    for i in range(t_len-1):
        if t2[i] != t[i+1]+1:
            out += " " + str(t2[i])
            t2[i] += 1
    print(out)
Buggy python submission (verdict: Time Limit Exceeded):
h, w, d = map(int, input().split())
g = [[] for _ in range(w)]
for _ in range(h):
    tmp_list = list(map(int, input().split()))
    for i in range(w):
        g[i].append(tmp_list[i])
q = int(input())
qs = [list(map(int, input().split())) for _ in range(q)]
loc = [0]*(h*w+1)
for i in range(h):
    for j in range(w):
        loc[g[j][i]] = (i,j)
roots = [[0]*(h*w+1) for _ in range(d)]
for i in range(1,d+1):
    j = i + d
    while j < h*w+1:
        cost = abs(loc[j][0]-loc[j-d][0]) + abs(loc[j][1]-loc[j-d][1])
        roots[i-1][j] = cost + roots[i-1][j-d]
        j += d
for i in qs:
    l, r = i[0], i[1]
    print(roots[(l-1)%d][r] - roots[(l-1)%d][l])

Fixed submission:
h, w, d = map(int, input().split())
g = [[] for _ in range(w)]
for _ in range(h):
    tmp_list = list(map(int, input().split()))
    for i in range(w):
        g[i].append(tmp_list[i])
q = int(input())
qs = [list(map(int, input().split())) for _ in range(q)]
loc = [0]*(h*w+1)
for i in range(h):
    for j in range(w):
        loc[g[j][i]] = (i,j)
roots = [0]*(h*w+1)
for i in range(1,d+1):
    j = i + d
    while j < h*w+1:
        cost = abs(loc[j][0]-loc[j-d][0]) + abs(loc[j][1]-loc[j-d][1])
        roots[j] = cost + roots[j-d]
        j += d
for i in qs:
    l, r = i[0], i[1]
    print(roots[r] - roots[l])

Buggy python submission (verdict: Time Limit Exceeded):
h, w, d = map(int, input().split())
g = [[] for _ in range(w)]
for _ in range(h):
    tmp_list = list(map(int, input().split()))
    for i in range(w):
        g[i].append(tmp_list[i])
q = int(input())
qs = [list(map(int, input().split())) for _ in range(q)]
loc = [0]*(h*w+1)
for i in range(h):
    for j in range(w):
        loc[g[j][i]] = (i,j)
roots = [[0]*(h*w+1) for _ in range(d)]
for i in range(1,d+1):
    j = i + d
    while j < h*w+1:
        cost = abs(loc[j][0]-loc[j-d][0]) + abs(loc[j][1]-loc[j-d][1])
        roots[i-1][j] = cost + roots[i-1][j-d]
        j += d
for i in qs:
    l, r = i[0], i[1]
    print(roots[(l-1)%d][r] - roots[(l-1)%d][l])

Fixed submission:
h, w, d = map(int, input().split())
g = [[] for _ in range(w)]
for _ in range(h):
    tmp_list = list(map(int, input().split()))
    for i in range(w):
        g[i].append(tmp_list[i])
q = int(input())
qs = [list(map(int, input().split())) for _ in range(q)]
loc = [0]*(h*w+1)
for i in range(h):
    for j in range(w):
        loc[g[j][i]] = (i,j)
roots = [0]*(h*w+1)
for i in range(1,d+1):
    j = i + d
    while j < h*w+1:
        cost = abs(loc[j][0]-loc[j-d][0]) + abs(loc[j][1]-loc[j-d][1])
        roots[j] = cost + roots[j-d]
        j += d
for i in qs:
    l, r = i[0], i[1]
    print(roots[r] - roots[l])