Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
A = []
B = []
for _ in range(H):
    A.append(list(map(int, input().split())))
for _ in range(H):
    B.append(list(map(int, input().split())))
d = [[0]*W for _ in range(H)]
for h in range(H):
    for w in range(W):
        d[h][w] = abs(A[h][w]-B[h][w])

dp = [[[] for _ in range(W)] for _ in range(H)]
dp[0][0].append(d[0][0])
for h in range(H):
    for w in range(W):
        if h < H-1:
            dp[h+1][w] += list(map(lambda x: x+d[h+1][w], dp[h][w]))
            dp[h+1][w] += list(map(lambda x: abs(x-d[h+1][w]), dp[h][w]))
        if w < W-1:
            dp[h][w+1] += list(map(lambda x: x+d[h][w+1], dp[h][w]))
            dp[h][w+1] += list(map(lambda x: abs(x-d[h][w+1]), dp[h][w]))
print(min(dp[-1][-1]))

Fixed submission:
def max2(x,y):
    return x if x > y else y

H, W = map(int, input().split())
A = []
B = []
ofs = 80*H*W
for _ in range(H):
    A.append(list(map(int, input().split())))
for _ in range(H):
    B.append(list(map(int, input().split())))
d = [[0]*W for _ in range(H)]
for h in range(H):
    for w in range(W):
        d[h][w] = abs(A[h][w]-B[h][w])

dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1<<ofs
dp[0][0] = (dp[0][0]<<d[0][0])|(dp[0][0]>>d[0][0])
for h in range(H):
    for w in range(W):
        if h < H-1:
            dp[h+1][w] |= (dp[h][w]<<d[h+1][w])|(dp[h][w]>>d[h+1][w])
        if w < W-1:
            dp[h][w+1] |= (dp[h][w]<<d[h][w+1])|(dp[h][w]>>d[h][w+1])
res = dp[-1][-1]>>ofs
print((-res&res).bit_length()-1)

Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
A = []
B = []
for _ in range(H):
    A.append(list(map(int, input().split())))
for _ in range(H):
    B.append(list(map(int, input().split())))
d = [[0]*W for _ in range(H)]
for h in range(H):
    for w in range(W):
        d[h][w] = abs(A[h][w]-B[h][w])

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(d[0][0])
for h in range(H):
    for w in range(W):
        if h < H-1:
            dp[h+1][w] |= set(map(lambda x: x+d[h+1][w], dp[h][w]))
            dp[h+1][w] |= set(map(lambda x: abs(x-d[h+1][w]), dp[h][w]))
        if w < W-1:
            dp[h][w+1] |= set(map(lambda x: x+d[h][w+1], dp[h][w]))
            dp[h][w+1] |= set(map(lambda x: abs(x-d[h][w+1]), dp[h][w]))
print(min(dp[-1][-1]))

Fixed submission:
def max2(x,y):
    return x if x > y else y

H, W = map(int, input().split())
A = []
B = []
ofs = 80*H*W
for _ in range(H):
    A.append(list(map(int, input().split())))
for _ in range(H):
    B.append(list(map(int, input().split())))
d = [[0]*W for _ in range(H)]
for h in range(H):
    for w in range(W):
        d[h][w] = abs(A[h][w]-B[h][w])

dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1<<ofs
dp[0][0] = (dp[0][0]<<d[0][0])|(dp[0][0]>>d[0][0])
for h in range(H):
    for w in range(W):
        if h < H-1:
            dp[h+1][w] |= (dp[h][w]<<d[h+1][w])|(dp[h][w]>>d[h+1][w])
        if w < W-1:
            dp[h][w+1] |= (dp[h][w]<<d[h][w+1])|(dp[h][w]>>d[h][w+1])
res = dp[-1][-1]>>ofs
print((-res&res).bit_length()-1)
Buggy python submission (verdict: Runtime Error):
from itertools import accumulate
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = accumulate([0]+ A)
C = [(b-i)%K for i, b in enumerate(B)]
cnt = [0]*N
cnt[C[0]] = 1
res = 0
for i in range(1, N+1):
    if i >= K:
        cnt[C[i-K]] -= 1
    res += cnt[C[i]]
    cnt[C[i]] += 1
print(res)


Fixed submission:
from itertools import accumulate
from collections import defaultdict
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = accumulate([0]+ A)
C = [(b-i)%K for i, b in enumerate(B)]
cnt = defaultdict(int)
cnt[C[0]] = 1
res = 0
for i in range(1, N+1):
    if i >= K:
        cnt[C[i-K]] -= 1
    res += cnt[C[i]]
    cnt[C[i]] += 1
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
def prime_factors(n):       # 戻り値はiterable type
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i             # whileループを進めるごとにイテレータに値を貯め続ける
    if n > 1:
        yield n

def min2(x,y):
    return x if x < y else y

from itertools import combinations

N = int(input())
P = list(prime_factors(N))
L = len(P) + 1
res =float("inf")

for k in range(L//2, 0, -1):
    for a in combinations(prime_factors(N), k):
        q = 1
        for p in a:
            q *= p
        res = min2((q - 1) + (N // q - 1), res)

print(res)

Fixed submission:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def min2(x,y):
    return x if x < y else y

N = int(input())
P = make_divisors(N)
L = len(P) + 1
res =float("inf")

for p in P:
    res = min2((p - 1) + (N // p - 1), res)

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
def prime_factors(n):       # 戻り値はiterable type
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i             # whileループを進めるごとにイテレータに値を貯め続ける
    if n > 1:
        yield n

def min2(x,y):
    return x if x < y else y

from itertools import combinations

N = int(input())
P = list(prime_factors(N))
L = len(P) + 1
res =float("inf")

for k in range(1, L//2+1):
    for a in combinations(prime_factors(N), k):
        q = 1
        for p in a:
            q *= p
        res = min2((q - 1) + (N // q - 1), res)

print(res)

Fixed submission:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def min2(x,y):
    return x if x < y else y

N = int(input())
P = make_divisors(N)
L = len(P) + 1
res =float("inf")

for p in P:
    res = min2((p - 1) + (N // p - 1), res)

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import *
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
F = list(map(int, input().split()))
F.sort(reverse=True)
data = []
for a, f in zip(A, F):
    heappush(data, (-a*f, a, f))
for _ in range(K):
    x, a, f = heappop(data)
    if a > 0:
        a -= 1
    heappush(data, (-a*f, a, f))

print(-heappop(data)[0])

Fixed submission:
import sys
input = sys.stdin.readline

def binary_search_int(ok, ng, test):
    """
    :param ok: solve(x) = True を必ず満たす点
    :param ng: solve(x) = False を必ず満たす点
    """
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid):
            ok = mid
        else:
            ng = mid
    return ok


N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
F = list(map(int, input().split()))
F.sort(reverse=True)

def max2(x,y):
    return x if x > y else y

def test(x):
    temp = K
    for a, f in zip(A, F):
        temp -= max2((a - x//f), 0)
        if temp < 0:
            return False
    return True

print(binary_search_int(A[-1]**2 + 100, -1,test))
Buggy python submission (verdict: Runtime Error):
from bisect import *
from collections import defaultdict
import sys
input = sys.stdin.readline

S = input().rstrip()
T = input().rstrip()
L = len(S)

dic = defaultdict(list)
for i, s in enumerate(S):
    dic[s].append(i)


s0 = -1
cnt = 0
for t in T:
    if not dic[t]:
        print(-1)
        exit()
    p = bisect_right(dic[t],s0)
    if p >= len(dic[t]):
        cnt += 1
        s0 = min(dic[t])
    else:
        s0 = dic[t][bisect_right(dic[t], p)]

print(L*cnt+s0 +1)

Fixed submission:
from bisect import *
from collections import defaultdict
import sys
input = sys.stdin.readline

S = input().rstrip()
T = input().rstrip()
L = len(S)

dic = defaultdict(list)
for i, s in enumerate(S):
    dic[s].append(i)


s0 = -1
cnt = 0
for t in T:
    if not dic[t]:
        print(-1)
        exit()
    p = bisect_right(dic[t],s0)
    if p >= len(dic[t]):
        cnt += 1
        s0 = min(dic[t])
    else:
        s0 = dic[t][p]

print(L*cnt+s0 +1)
Buggy python submission (verdict: Runtime Error):
def divisors(n):
    i = 1
    table = set()
    while i * i <= n:
        if not n % i:
            table.add(i)
            table.add(n//i)
        i += 1
    table = list(table)
    return table

def binary_search_int(ok, ng, test):
    """
    :param ok: solve(x) = True を必ず満たす点
    :param ng: solve(x) = False を必ず満たす点
    """
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid):
            ok = mid
        else:
            ng = mid
    return ok

import numpy as np
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
S = sum(A)
D = divisors(S)
D.sort()

def test(x):
    k = D[x]
    B = A%k
    B.sort()
    cnt = sum(B)//k
    return k*cnt - sum(B[-cnt:]) <= K

print(D[binary_search_int(0,len(D),test)])

Fixed submission:
def divisors(n):
    i = 1
    table = set()
    while i * i <= n:
        if not n % i:
            table.add(i)
            table.add(n//i)
        i += 1
    table = list(table)
    return table

def binary_search_int(ok, ng, test):
    """
    :param ok: solve(x) = True を必ず満たす点
    :param ng: solve(x) = False を必ず満たす点
    """
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid):
            ok = mid
        else:
            ng = mid
    return ok

import numpy as np
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
S = sum(A)
D = divisors(S)
D.sort()

def test(x):
    k = D[x]
    B = A%k
    B.sort()
    cnt = sum(B)//k
    return k*cnt - sum(B[-cnt:]) <= K

p = binary_search_int(0,len(D),test)
q = binary_search_int(p+1,len(D),test)
print(max(D[p],D[q]) if q != p+1 else D[p])
Buggy python submission (verdict: Runtime Error):
N = int(input())
P = list(map(int, input().split()))
p0 = 0
p1 = P[0]
temp = []
for i, p in enumerate(P[1:]):
    if p >= p1:
        p0 = p1
        p1 = p
        continue
    else:
        temp.append(i)
        p1 = p

if len(temp) > 2:
    print("NO")
    exit()
if len(temp) == 0:
    print("YES")
    exit()

P[temp[0]], P[temp[1]+1] = P[temp[1]+1], P[temp[0]]

p0 = 0
p1 = P[0]
temp = []
for i, p in enumerate(P[1:]):
    if p >= p1:
        p0 = p1
        p1 = p
        continue
    else:
        temp.append(i)
        p1 = p

if len(temp) == 0:
    print("YES")
else:
    print("NO")


Fixed submission:
N = int(input())
P = list(map(int, input().split()))
p0 = 0
p1 = P[0]
temp = []
for i, p in enumerate(P[1:]):
    if p >= p1:
        p0 = p1
        p1 = p
        continue
    else:
        temp.append(i)
        p1 = p

if len(temp) == 2:
    P[temp[0]], P[temp[1]+1] = P[temp[1]+1], P[temp[0]]

    p0 = 0
    p1 = P[0]
    temp = []
    for i, p in enumerate(P[1:]):
        if p >= p1:
            p0 = p1
            p1 = p
            continue
        else:
            temp.append(i)
            p1 = p
    if len(temp) == 0:
        print("YES")
    else:
        print("NO")
elif len(temp)==0:
    print("YES")
else:
    print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
S = list(input())
L = len(S)
M = 13
MOD = 10**9 + 7
dp = [[0]*M for _ in range(L+1)]
dp[0][0]=1
for i in range(L):
    if S[i] == "?":
        for j in range(M):
            for k in range(10):
                s = k*pow(10, L-1-i, 13)
                dp[i+1][(j+s)%13] += dp[i][j]
                dp[i + 1][(j + s) % 13] %= MOD
    else:
        s = int(S[i])
        s *= pow(10, L - 1 - i, 13)
        for j in range(M):
            dp[i+1][(j+s)%13] += dp[i][j]
            dp[i + 1][(j + s) % 13] %= MOD

print(dp[L][5])

Fixed submission:
S = list(input())
L = len(S)
M = 13
MOD = 10**9 + 7
dp = [[0]*M for _ in range(L+1)]
dp[0][0]=1
for i in range(L):
    p = pow(10, L-1-i, 13)
    if S[i] == "?":
        for j in range(M):
            for k in range(10):
                s = k*p
                dp[i+1][(j+s)%13] += dp[i][j]
                dp[i + 1][(j + s) % 13] %= MOD
    else:
        s = int(S[i])
        s *= p
        for j in range(M):
            dp[i+1][(j+s)%13] += dp[i][j]
            dp[i + 1][(j + s) % 13] %= MOD

print(dp[L][5])
Buggy python submission (verdict: Runtime Error):
from itertools import combinations
N, D = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
data = [0]*5002
i = 1
while i**2<=5001:
    data[i**2]=1
    i += 1
res = 0
for a, b in combinations(X,2):
    temp = 0
    for x, y in zip(a, b):
        temp += (x-y)**2
    if data[temp]:
        res += 1
print(res)

Fixed submission:
from itertools import combinations
N, D = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
data = [0]*16002
i = 1
while i**2<=16001:
    data[i**2]=1
    i += 1
res = 0
for a, b in combinations(X,2):
    temp = 0
    for x, y in zip(a, b):
        temp += (x-y)**2
    if data[temp]:
        res += 1
print(res)

Buggy python submission (verdict: Runtime Error):
from itertools import combinations
N, D = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
data = [0]*4001
i = 1
while i**2<=4001:
    data[i**2]=1
    i += 1
res = 0
for a, b in combinations(X,2):
    temp = 0
    for x, y in zip(a, b):
        temp += (x-y)**2
    if data[temp]:
        res += 1
print(res)

Fixed submission:
from itertools import combinations
N, D = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
data = [0]*16002
i = 1
while i**2<=16001:
    data[i**2]=1
    i += 1
res = 0
for a, b in combinations(X,2):
    temp = 0
    for x, y in zip(a, b):
        temp += (x-y)**2
    if data[temp]:
        res += 1
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
class cumsum2D:
    def __init__(self, data):
        self.N = len(data)
        self.M= len(data[0])
        self.cum = [[0] * (self.M + 1) for _ in range(self.N + 1)]
        for i in range(self.N):
            for j in range(self.M):
                self.cum[i + 1][j + 1] = self.cum[i][j + 1] + self.cum[i + 1][j] - self.cum[i][j] + data[i][j]

    def get(self,x1,y1,x2,y2):
        """
        長方形の領域 [x1,x2)*[y1,y2) の範囲内にインプットされた数字の和を取る
        """
        return self.cum[x2][y2] - self.cum[x1][y2] - self.cum[x2][y1] + self.cum[x1][y1]

########################################################################################################
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [[0]*(M+1) for _ in range(N+1)]
cum = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(N):
    for j in range(M):
        if S[i]==T[j]:
            dp[i][j] += cum[i][j] + 1
        cum[i + 1][j + 1] = cum[i][j + 1] + cum[i + 1][j] - cum[i][j] + dp[i][j]
print((cum[N][M]+1)%MOD)

Fixed submission:
# https://atcoder.jp/contests/abc130/tasks/abc130_e
"""
タグ: LCS、二次元累積和
"""
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [[0]*(M+1) for _ in range(N+1)]
cum = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(N):
    for j in range(M):
        if S[i]==T[j]:
            dp[i][j] += cum[i][j] + 1
            dp[i][j]%=MOD
        cum[i + 1][j + 1] = cum[i][j + 1] + cum[i + 1][j] - cum[i][j] + dp[i][j]
        cum[i + 1][j + 1]%=MOD
print(cum[N][M]+1)
Buggy python submission (verdict: Time Limit Exceeded):

def make_mat(grid):
    H = len(grid)
    W = len(grid[0])
    res = [[0] * W for _ in range(H)]
    for h in range(H):
        cnt = 0
        for w in range(W):
            if grid[h][w] == "#":
                for i in range(cnt):
                    res[h][w - 1 - i] = cnt
                cnt = 0
            else:
                cnt += 1
        if grid[h][w] == ".":
            for i in range(cnt):
                res[h][w - i] = cnt
    return res

def max2(x,y):
    return x if x > y else y


import sys
input = sys.stdin.readline

H, W = map(int, input().split())
grid = []
for _ in range(H):
    grid.append(list(input().rstrip()))

A = make_mat(grid)
grid_t = list(zip(*grid))
B = list(zip(*make_mat(grid_t)))
res = 0
for h in range(H):
    for w in range(W):
        res = max2(A[h][w] + B[h][w], res)

print(res-1)

Fixed submission:
def make_mat(grid, H, W):
    res = [[0] * W for _ in range(H)]
    for h in range(H):
        cnt = 0
        for w in range(W):
            if (grid[h]>>w)&1 == 1:
                for i in range(cnt):
                    res[h][w - 1 - i] = cnt
                cnt = 0
            else:
                cnt += 1
        if (grid[h]>>w)&1 == 0:
            for i in range(cnt):
                res[h][w - i] = cnt
    return res

def max2(x,y):
    return x if x > y else y


import sys
input = sys.stdin.readline

H, W = map(int, input().split())


grid = []
grid_t = [0]*W
for h in range(H):
    temp = 0
    for w, s in enumerate(input().rstrip()):
        if s=="#":
            temp += 1<<w
            grid_t[w] += 1<<h
    grid.append(temp)

A = make_mat(grid, H, W)
B = make_mat(grid_t, W, H)

res = 0
for h in range(H):
    for w in range(W):
        res = max2(A[h][w] + B[w][h], res)

print(res-1)
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import *
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
data = []
for _ in range(M):
    B, C = map(int, input().split())
    data.append((B, C))
data.sort(key=lambda x:x[1], reverse=True)

D = []
for B, C in data:
    i = bisect_left(A, C)
    if B<=i:
        D += [C]*B
    else:
        D += [C]*i

res = 0
for i in range(N):
    if i>=len(D) or A[i] > D[i]:
        res += A[i]
    else:
        res += D[i]
print(res)

Fixed submission:
from bisect import *
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
data = []
for _ in range(M):
    B, C = map(int, input().split())
    data.append((B, C))
data.sort(key=lambda x:x[1], reverse=True)

D = []
for B, C in data:
    i = bisect_left(A, C)
    p = min(B, i)
    if len(D)+p <N:
        D += [C]*p
    else:
        D += [C]*(N-len(D))
        break

res = 0
for i in range(N):
    if i>=len(D) or A[i] > D[i]:
        res += A[i]
    else:
        res += D[i]
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
def binary_search_int(ok, ng, test, k, A, B):
    """
    :param ok: solve(x) = True を必ず満たす点
    :param ng: solve(x) = False を必ず満たす点
    """
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid, k, A, B):
            ok = mid
        else:
            ng = mid
    return ok

def get_cnt(x, A, B):
    """
    a+b<=x となるようなAの要素とBの要素の組の数 (A, Bはソート済み)
    """
    cnt = 0
    L = len(B)
    for a in A:
        cnt += L-bisect_left(B, x-a)
    return cnt

def test(x, k, A, B):
    """
    場合の数が k 個(以上)となるような最小の x を探索する関数
    a+b <= x で get_cnt(x,A,B) は同じ値を返すので、最小の x は A, Bの要素の和そのものに一致する
    """
    return get_cnt(x,A,B) >= k

###########################################################

import sys
input = sys.stdin.readline
from bisect import *

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()))
A.sort()
B.sort()
C.sort()

P = []
for k in range(1,K+1):
    tmp = binary_search_int(0, 10**11,test, k, A, B)
    if tmp != 0:
        P.append(tmp)
Q = []
P.sort()
for k in range(1,K+1):
    Q.append(binary_search_int(1, 10**11,test, k, P, C))
print(*Q, sep="\n")

Fixed submission:
def binary_search_int(ok, ng, test, k, A, B):
    """
    :param ok: solve(x) = True を必ず満たす点
    :param ng: solve(x) = False を必ず満たす点
    """
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid, k, A, B):
            ok = mid
        else:
            ng = mid
    return ok

def get_cnt(x, A, B):
    """ a+b>=x となるようなAの要素とBの要素の組の数 (A, Bはソート済み)"""
    l, r = bisect_left(B, x-A[-1]), len(A)-2
    cnt = len(B) - l
    while l < len(B) and r>=0:
        if A[r]+B[l] < x:
            l += 1
        else:
            cnt += len(B) - l
            r -= 1
    return cnt

def test(x, k, A, B):
    return get_cnt(x, A, B) >= k

from bisect import *

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()))
A.sort()
B.sort()
C.sort()

P = []
for k in range(1,K+1):
    tmp = binary_search_int(0, 10**11,test, k, A, B)
    if tmp != 0:
        P.append(tmp)
Q = []
P.sort()
for k in range(1,K+1):
    Q.append(binary_search_int(1, 10**11,test, k, P, C))
print(*Q, sep="\n")
Buggy python submission (verdict: Time Limit Exceeded):
def near(x, Y):
    i = bisect_left(Y,x)
    if i == 0:
        return Y[i]-x
    elif i == len(Y):
        return x-Y[i-1]
    else:
        return min(Y[i]-x, x-Y[i-1])

def near2(x, D):
    Y = [d for d ,_ in D]
    i = bisect_left(Y,x)
    if i == 0:
        return Y[i]-x + D[i][1]
    elif i == len(Y):
        return x-Y[i-1] + D[i-1][1]
    else:
        return min(Y[i]-x+D[i][1], x-Y[i-1]+D[i-1][1])

from bisect import *
A, B, Q = map(int, input().split())
S = []
T = []
for _ in range(A):
    S.append(int(input()))
for _ in range(B):
    T.append(int(input()))
D = []
for a in S:
    D.append((a, near(a, T)))
for b in T:
    D.append((b, near(b, S)))
D.sort(key=lambda x:x[0])
for _ in range(Q):
    x = int(input())
    print(near2(x,D))



Fixed submission:
def near(x, Y):
    i = bisect_left(Y,x)
    if i == 0:
        return Y[i]-x
    elif i == len(Y):
        return x-Y[i-1]
    else:
        return min(Y[i]-x, x-Y[i-1])

def near2(x, Y):
    i = bisect_left(Y,x)
    if i == 0:
        return Y[i]-x + D[i][1]
    elif i == len(Y):
        return x-Y[i-1] + D[i-1][1]
    else:
        return min(Y[i]-x+D[i][1], x-Y[i-1]+D[i-1][1])

from bisect import *
A, B, Q = map(int, input().split())
S = []
T = []
for _ in range(A):
    S.append(int(input()))
for _ in range(B):
    T.append(int(input()))
D = []
for a in S:
    D.append((a, near(a, T)))
for b in T:
    D.append((b, near(b, S)))
D.sort(key=lambda x:x[0])
D2 = [d for d, _ in D]
for _ in range(Q):
    x = int(input())
    print(near2(x,D2))

Buggy python submission (verdict: Time Limit Exceeded):
def near(x, Y):
    i = bisect_left(Y,x)
    if i == 0:
        return Y[i]-x
    elif i == len(Y):
        return x-Y[i-1]
    else:
        return min(Y[i]-x, x-Y[i-1])

def near2(x, D):
    Y = [d for d ,_ in D]
    i = bisect_left(Y,x)
    if i == 0:
        return Y[i]-x + D[i][1]
    elif i == len(Y):
        return x-Y[i-1] + D[i-1][1]
    else:
        return min(Y[i]-x+D[i][1], x-Y[i-1]+D[i-1][1])

from bisect import *
A, B, Q = map(int, input().split())
S = []
T = []
for _ in range(A):
    S.append(int(input()))
for _ in range(B):
    T.append(int(input()))
S.sort()
T.sort()
D = []
for a in S:
    D.append((a, near(a, T)))
for b in T:
    D.append((b, near(b, S)))
D.sort()
for _ in range(Q):
    x = int(input())
    print(near2(x,D))



Fixed submission:
def near(x, Y):
    i = bisect_left(Y,x)
    if i == 0:
        return Y[i]-x
    elif i == len(Y):
        return x-Y[i-1]
    else:
        return min(Y[i]-x, x-Y[i-1])

def near2(x, Y):
    i = bisect_left(Y,x)
    if i == 0:
        return Y[i]-x + D[i][1]
    elif i == len(Y):
        return x-Y[i-1] + D[i-1][1]
    else:
        return min(Y[i]-x+D[i][1], x-Y[i-1]+D[i-1][1])

from bisect import *
A, B, Q = map(int, input().split())
S = []
T = []
for _ in range(A):
    S.append(int(input()))
for _ in range(B):
    T.append(int(input()))
D = []
for a in S:
    D.append((a, near(a, T)))
for b in T:
    D.append((b, near(b, S)))
D.sort(key=lambda x:x[0])
D2 = [d for d, _ in D]
for _ in range(Q):
    x = int(input())
    print(near2(x,D2))