Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import math


def pattern(x, y, z):
    if x == y == z:
        return 1
    elif x != y and y != z and x != z:
        return 6
    else:
        return 3


def check(ans):
    cnt = 0
    for x in range(1, ans):
        # if pow(x, 2) > ans:
        # break
        for y in range(x, ans):
            # if pow(x+y, 2) > ans:
            # break
            for z in range(y, ans):
                tmp = x*(x+y+z) + y*(y+z) + z*z
                #tmp = pow(x+y+z, 2) - x*(y+z) - y*z
                if tmp == ans:
                    cnt += pattern(x, y, z)
                elif tmp > ans:
                    break
    print(cnt)


N = int(input())
# x^2 + y^2 + z^2 + x*y + y*z + z*x = n

for i in range(1, N+1):
    #upper_value = int(math.sqrt(i))
    check(i)


### FIXED CODE ###

import math


def pattern(x, y, z):
    if x == y == z:
        return 1
    elif x != y and y != z and x != z:
        return 6
    else:
        return 3


def check(ans):
    cnt = 0
    upper = int(math.sqrt(ans))
    for x in range(1, upper):
        if pow(x, 2) > ans:
            break
        for y in range(x, upper):
            if pow(x+y, 2) > ans:
                break
            for z in range(y, upper):
                tmp = x*(x+y+z) + y*(y+z) + z*z
                # tmp = pow(x+y+z, 2) - x*(y+z) - y*z
                if tmp == ans:
                    cnt += pattern(x, y, z)
                    if x == y and y == z and z == x:
                        print(cnt)
                        return
                elif tmp > ans:
                    break
    print(cnt)


N = int(input())
# x^2 + y^2 + z^2 + x*y + y*z + z*x = n

for i in range(1, N+1):
    # upper_value = int(math.sqrt(i))
    check(i)
### BUGGY CODE ###

e=enumerate
h,w=map(int,input().split())
a=[list(map(int,input().split()))for _ in range(h)]
b=[list(map(int,input().split()))for _ in range(h)]
dp=[[]for _ in range(w)]
dp[0]={a[0][0]-b[0][0],b[0][0]-a[0][0]}
for i,(a,b)in e(zip(a,b)):
  for j,(d,x,y)in e(zip(dp,a,b)):
    x,y=x-y,y-x
    t=[]
    add=t.append
    if i:
      for v in d:
        add(v+x)
        add(v+y)
    if j:
      for v in dp[j-1]:
        add(v+x)
        add(v+y)
    if i+j:dp[j]=set(t)
print(min(map(abs,dp[w-1])))

### FIXED CODE ###

e=enumerate
h,w=map(int,input().split())
a=[list(map(int,input().split()))for _ in range(h)]
b=[list(map(int,input().split()))for _ in range(h)]
dp=[0]*w
c=13000
for i,(a,b)in e(zip(a,b)):
  for j,(x,y)in e(zip(a,b)):
    x=abs(x-y)
    if i==j==0:
      dp[j]=2**c<<x
      continue
    t=0
    if j:
      t|=dp[j-1]<<x
      t|=dp[j-1]>>x
    if i:
      t|=dp[j]<<x
      t|=dp[j]>>x
    dp[j]=t
*a,=map(int,(bin(dp[w-1])[2:]).zfill(26001))
print(min([i for i,f in e(a[13000:])if f]+[i for i,f in e(a[13000::-1])if f]))
### BUGGY CODE ###

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 CODE ###

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 CODE ###

MOD = int(1e9 + 7)
N = int(1e5)
M = 13

s = input()
dp = [[0 for x in range(M)] for x in range(N)]
dp[0][0] = 1

for i in range(len(s)):
    for j in range(M):
        for k in range(10):
            if s[i] == "?" or s[i] == str(k):
                dp[i+1][(j*10 +k) % M] += dp[i][j]
                dp[i+1][(j*10 +k) % M] %= MOD


print(dp[len(s)][5])


### FIXED CODE ###

MOD = int(1e9 + 7)
N = int(1e5)
M = 13

s = input()
dp = [[0 for x in range(M)] for x in range(N+10)]
dp[0][0] = 1

for i in range(len(s)):
    for j in range(M):
        for k in range(10):
            if s[i] == "?" or s[i] == str(k):
                dp[i+1][(j*10 +k) % M] += dp[i][j]
                dp[i+1][(j*10 +k) % M] %= MOD


print(dp[len(s)][5])
### BUGGY CODE ###

import heapq

N = int(input())
A = list(map(int, input().split()))
Temp = input().split()
B = []
for i in range(N):
    heapq.heappush(B, (-int(Temp[i]), i))
now = list(map(int, Temp))
complete = [False]*N
fin = [True]*N
ans = 0
while True:
    v, i = heapq.heappop(B)
    if A[i] == now[i]:
        complete[i] = True

    if not complete[i]:
        if i == 0:
            nv = v + now[-1] + now[1]
        elif i == N-1:
            nv = v + now[0] + now[-2]
        else:
            nv = v + now[i-1] + now[i+1]
        if nv <= -A[i]:
            heapq.heappush(B, (nv, i))
            now[i] = -nv
            ans += 1
    else:
        if complete == fin:
            break
    if not B:
        print(-1)
        exit()
print(ans)

### FIXED CODE ###

import heapq

N = int(input())
A = list(map(int, input().split()))
B = input().split()
C = []
for i in range(N):
    heapq.heappush(C, (A[i] - int(B[i]), i))
B = list(map(int, B))
ans = 0
while True:
    v, i = heapq.heappop(C)
    if v == 0:
        break

    nv = B[i-1] + B[(i+1) % N]
    n = -v // nv
    if n <= 0:
        print(-1)
        exit()
    v += n * nv
    B[i] -= n * nv
    heapq.heappush(C, (v, i))
    ans += n
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())

A = list(map(int, input().split()))
A.sort()
X = []
for i in range(m):
    b, c = map(int, input().split())
    X += [c]*b
X.sort(reverse=True)

ans = sum(A)
for i in range(min(len(A), len(X))):
    if A[i] >= X[i]:
        break
    ans += X[i] - A[i]

print(ans)

### FIXED CODE ###

n, m = map(int, input().split())

A = list(map(int, input().split()))
A.sort()
bc = []
for i in range(m):
    b, c = map(int, input().split())
    bc.append([b, c])
bc.sort(key=lambda x:x[1], reverse=True)

X = []
for b, c in bc:
    X += [c]*b
    if len(X) >= len(A):
        break

ans = sum(A)
for i in range(min(len(A), len(X))):
    if A[i] >= X[i]:
        break
    ans += X[i] - A[i]

print(ans)
### BUGGY CODE ###

import copy
N,K = map(int,input().split())
A = list(map(int,input().split()))
#B = copy.copy(A)
#B = [0 for _ in range(N)]
for t in range(K):
  while min(A) >= N:
    ans = [N]*N
    print(*ans)
    exit()
  B = [0 for _ in range(N)]
  for i in range(N):
    MIN = max(0,i-A[i])
    MAX = min(N-1,i+A[i])
    p = MIN
    while p<=MAX:
      B[p] +=1
      p += 1
  A = B
  #print(B)
print(*B)

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))

for i in range(K):
  if min(A) == N:
    ans = [N]*N
    print(*ans)
    exit()
  B = [0 for _ in range(N)]
  for j in range(N):
    left = max(0,j-A[j])
    right = min(N-1,j+A[j])
    B[left] += 1
    if right+1 <= N-1:
      B[right+1] -=1
  #print(B)
  for t in range(1,N):
    B[t] += B[t-1]
  A = B
print(*B)
### BUGGY CODE ###

n = input()
array = []
for i in range(n):
	inst = raw_input().split()
	if inst[0] == "insert":
		array.insert(0,inst[1])
	if inst[0] == "delete":
		if inst[1] in array:
			array.remove(inst[1])
	if inst[0] == "deleteFirst":
		del array[0]
	if inst[0] == "deleteLast":
		del array[len(array)-1]
print " ".join(i for i in array)

### FIXED CODE ###

n = input()
array = []
base = 0
for i in xrange(n):
    inst = raw_input().split()
    if inst[0][0] == 'i':
        array.append(int(inst[1]))
    elif inst[0] == "delete":
        if int(inst[1]) in array:
            x = array[::-1].index(int(inst[1]))
            if x != -1 and int(inst[1]):
                del array[-x-1]
    elif inst[0][6] == 'F':
        array.pop()
    else:
        base += 1
print (" ".join(map(str,array[base:][::-1])))
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
ans=0
for i in range(3001):
    if i*r>n:
        break
    for j in range(3001):
        if i*r+j*g>n:
            break
        if (n-(r*i+g*j))%b==0 or (n-(r*i+g*j))==0:
                ans+=1
print(ans)

### FIXED CODE ###

r,g,b,n=map(int,input().split())
ans=0
for i in range(3001):
    if i*r>n:
        break
    for j in range(3001):
        if i*r+j*g>n:
            break
        if (n-(r*i+g*j))%b==0 or (n-(r*i+g*j))==0:
                ans+=1
print(ans)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for _ in range(n)]
m=max(a)
for i in range(n):
  if a[i]<m:
    print(m)
  else:
    print(sorted(a)[-2])

### FIXED CODE ###

n=int(input())
a=[int(input()) for _ in range(n)]
m=max(a)
b=sorted(a)
for i in range(n):
  if a[i]==m:
    print(b[-2])
  else:
    print(m)
### BUGGY CODE ###

def main():
    S = str(input())
    T = str(input())

    dp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

    for i in range(len(S)):
        for j in range(len(T)):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

    lst = []

    N = i + 1
    M = j + 1
    while (N - 1) >= 0 and (M - 1) >= 0:
        if S[N - 1] == T[M - 1]:
            lst.append(S[N - 1])
            N -= 1
            M -= 1
        else:
            if dp[N][M] == dp[N - 1][M]:
                N -= 1
            else:
                M -= 1

    print (*lst[::-1], sep = '')

if __name__ == '__main__':
    main()

### FIXED CODE ###

S = str(input())
T = str(input())

dp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

lst = []

N = i + 1
M = j + 1
while (N - 1) >= 0 and (M - 1) >= 0:
    if S[N - 1] == T[M - 1]:
        lst.append(S[N - 1])
        N -= 1
        M -= 1
    else:
        if dp[N][M] == dp[N - 1][M]:
            N -= 1
        else:
            M -= 1

print (*lst[::-1], sep = '')
### BUGGY CODE ###

N = int(input())

L = []
for i in range(N):
    L.append(tuple(map(int, input().split())))

nowT = L[0][0]
nowA = L[0][1]
for i in range(1, N):
    tmpT = L[i][0]
    tmpA = L[i][1]
    mul = 2
    while not(tmpT >= nowT and tmpA >= nowA):
        tmpT = L[i][0] * mul
        tmpA = L[i][1] * mul
        mul += 1
    nowT = tmpT
    nowA = tmpA

print(nowT + nowA)


### FIXED CODE ###

N = int(input())

nowT = 1
nowA = 1
for i in range(N):
    nextT, nextA = map(int, input().split())

    # mul = max(ceil(nowT / nextT), ceil(nowA / nextA))
    mul = max(-(-nowT // nextT), -(-nowA // nextA))
    nowT = nextT * mul
    nowA = nextA * mul

print(nowT + nowA)
### BUGGY CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Ciの値でsortする、Tを0000で固定した後、最後に2**N倍
N = ir()
C = np.array(lr())
MOD = 10 ** 9 + 7
C.sort()
two_power = np.array([(1+N-i) * 2**(N-2) if i < N-1 else 2 ** i for i in range(N)])
answer = (C * two_power % MOD).sum() * 2**N
print(answer%MOD)


### FIXED CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Ciの値でsortする、Tを0000で固定した後、最後に2**N倍
N = ir()
C = np.array(lr())
MOD = 10 ** 9 + 7
C.sort()
two_power = np.array([(1+N-i) * pow(2, (N-2), MOD) % MOD if i < N-1 else pow(2, i, MOD) for i in range(N)])
answer = (C * two_power % MOD).sum() * 2**N
print(answer%MOD)
### BUGGY CODE ###

import functools
MOD=10**9+7
def euclid(a, b):
  if b == 0:
    return a
  else:
    return euclid(b, a%b)

def multiple(a, b):
  return a*b // euclid(a, b)

def lcm(nums):
  return functools.reduce(multiple, nums)
n=int(input())
a=list(map(int,input().split()))
x=lcm(a)
sum=0
for i in range(n):
    sum+=x//a[i]
print(sum%MOD)

### FIXED CODE ###

import functools
MOD=10**9+7
def euclid(a, b):
  if b == 0:
    return a
  else:
    return euclid(b, a%b)

def multiple(a, b):
  return a*b // euclid(a, b)

def lcm(nums):
  return functools.reduce(multiple, nums)
n=int(input())
a=list(map(int,input().split()))
x=lcm(a)
sum=0
for i in range(n):
    sum+=x//a[i]
print(sum%MOD)
### BUGGY CODE ###

s = input()
l = len(s)

while True:
    if s.count('0') == 0 or s.count('1') == 0:
        break
    elif 4 <= len(s):
        s = s.replace('0011', '')
        s = s.replace('1010', '')
        s = s.replace('0101', '')
        s = s.replace('1100', '')
    else:
        s = s.replace('01', '')
        s = s.replace('10', '')

print(l - len(s))

### FIXED CODE ###

s = input()
one = s.count('1')
zero = s.count('0')

print(len(s) - abs(one - zero))
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
a_list = list(map(int, input().split()))
ans = 1
flag = 1
for a in a_list:
    ans *= a
    if ans > 10 ** 18:
        flag = 0
    if a == 0:
        flag = 1
if flag == 0:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
import numpy as np
n = int(input())
a_list = np.array(list(map(int, input().split())))
y = np.argsort(a_list)
if a_list[y[0]] == 0:
    print(0)
else:
    ans = 1
    flag = 1
    for i in range(0, n):
        ans *= int(a_list[y[n - 1 - i]])
        if ans > 10 ** 18:
            flag = 0
            break
    if flag == 0:
        print(-1)
    else:
        print(ans)
### BUGGY CODE ###

import bisect

x, y, a, b, c = map(int, input().split())
p = [int(_) for _ in input().split()]
q = [int(_) for _ in input().split()]
r = [int(_) for _ in input().split()]

p.sort()
q.sort()
r.sort()

x_list = p[-x:]
y_list = q[-y:]

while (min(x_list[0], y_list[0]) < r[-1]):
    if x_list[0] > y_list[0]:
        i = bisect.bisect_right(r, y_list[0])
        y_list.pop(0)
        target = r.pop(i)
        bisect.insort(y_list, target)
    else:
        i = bisect.bisect_right(r, x_list[0])
        x_list.pop(0)
        target = r.pop(i)
        bisect.insort(x_list, target)

    if len(r) == 0:
        break

print(sum(x_list) + sum(y_list))

### FIXED CODE ###

x, y, a, b, c = map(int, input().split())
p = [int(_) for _ in input().split()]
q = [int(_) for _ in input().split()]
r = [int(_) for _ in input().split()]
 
p.sort()
q.sort()
r.sort()
 
x_list = p[-x:]
y_list = q[-y:]
all_apple = x_list + y_list + r
all_apple.sort()
 
print(sum(all_apple[-(x+y):]))
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))

E = 0
max = 0
for i in range(N - K + 1):
    work = sum(P[i:i+K])
    if work > max:
        max = work
        max_values = P[i:i+K]

for m in max_values:
    E += (1 + m) * m * (1/2) * (1/m)

print(E)


### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
P_E = list(((1 + P[i]) / 2) for i in range(N))

E = 0
prog = sum(P_E[0:K])
max = prog
for i in range(N - K):
    prog += P_E[i + K] - P_E[i]
    if prog > max:
        max = prog
    else:
        pass
    
print(max)
### BUGGY CODE ###

n,m=map(int,input().split());a=0
while n and m>1:
    n-=1;m-=2;a+=1
print(a+m//4)

### FIXED CODE ###

n,m=map(int,input().split())
print(min((m+2*n)//4,m//2))
### BUGGY CODE ###

import numpy as np
n = int(input())
l_ls = list(map(int, input().split()))
l_ls.sort()
stick_count = [0] * (10**3+1)
for i in range(n):
    stick_count[l_ls[i]] += 1
stick_csum = list(np.cumsum(stick_count))
ans = 0
for first_i in range(n):
    for second_i in range(first_i+1, n):
        #境界は含まない
        greater_than = abs(l_ls[first_i] - l_ls[second_i])
        smaller_than = min(10**3,l_ls[first_i] + l_ls[second_i])
        num_canmake = max(0, stick_csum[smaller_than-1] - stick_csum[greater_than])
        if greater_than < l_ls[first_i] < smaller_than:
            num_canmake -= 1
        if greater_than < l_ls[second_i] < smaller_than:
            num_canmake -= 1
        num_canmake = max(0,num_canmake)
        ans += num_canmake
print(ans//3)




### FIXED CODE ###

n = int(input())
l_ls = list(map(int, input().split()))
l_ls.sort()
stick_count = [0] * (10**3+1)
stick_csum = [0] * (10**3+1)
for i in range(n):
    stick_count[l_ls[i]] += 1
now = 0
for i in range(10**3+1):
    now += stick_count[i]
    stick_csum[i] = now

ans = 0
for first_i in range(n):
    for second_i in range(first_i+1, n):
        #境界は含まない
        greater_than = abs(l_ls[first_i] - l_ls[second_i])
        smaller_than = min(10**3+1,l_ls[first_i] + l_ls[second_i])
        num_canmake = max(0, stick_csum[smaller_than-1] - stick_csum[greater_than])
        if greater_than < l_ls[first_i] < smaller_than:
            num_canmake -= 1
        if greater_than < l_ls[second_i] < smaller_than:
            num_canmake -= 1
        num_canmake = max(0,num_canmake)
        ans += num_canmake
print(ans//3)
### BUGGY CODE ###

N = int(input())
W = []
for _ in range(N):
    n = input()
    if n in W:
        W.remove(n)
    else:
        W.append(n)
print(len(W))


### FIXED CODE ###

import collections

N = int(input())
W = [int(input()) for _ in range(N)]
c = collections.Counter(W)
print(len([i for i in c.values() if i % 2 != 0]))
### BUGGY CODE ###

#dojkstra (prioroty queue ver.)
import queue
G=[]
#infの値に注意
inf=3*10**15
#V, E=map(int,input().strip().split(' '))
V=int(input().strip())
E=V-1

for i in range(V):
    G.append([])
for i in range(E):
    at,bt,ct=map(int,input().strip().split(' '))
    G[at-1].append([ct,bt-1])
    G[bt-1].append([ct,at-1]) #無向グラフのときはon
'''
#入力が0-indexedのとき
    G[at].append([ct,bt])
    G[bt].append([ct,at]) #無向グラフのときはon
'''
#入力が1-indexedのとき


def dijkstra(s):
    d=[inf]*V
    d[s]=0
    q=queue.PriorityQueue()
    q.put([0,s])
    while q.empty()==False:
        dq,v=q.get()
        if d[v]<dq:
            continue
        for i in range(len(G[v])):
            ec, et=G[v][i]
            #print(ec,et)
            if d[et]>d[v]+ec:
                d[et]=d[v]+ec
                q.put([d[et],et])
    return d

Q, K=map(int,input().strip().split(' '))
K-=1 #0-indexedに直す
x=[]
y=[]

d=dijkstra(K)

for i in range(Q):
    xt, yt=map(int,input().strip().split(' '))
    x.append(xt-1)#0-indexedに直して入れる
    y.append(yt-1)#0-indexedに直して入れる
for i in range(Q):
    print(d[x[i]]+d[y[i]])

### FIXED CODE ###

import sys
#limit=sys.getrecursionlimit()
sys.setrecursionlimit(10000000)
#sys.setrecursionlimit(1000000000)

V=int(input().strip())
E=V-1
inf=3*10**15
G=[]
dist=[inf]*V

for i in range(V):
    G.append([])
for i in range(E):
    at,bt,ct=map(int,input().strip().split(' '))
    G[at-1].append([ct,bt-1])
    G[bt-1].append([ct,at-1])

visited=[False]*V
def dfs(v,p,d):
    #global d
    dist[v]=d
    for q in G[v]:
        if q[1]==p:
            continue
        dfs(q[1],v,d+q[0])

Q, K=map(int,input().strip().split(' '))
K-=1 #0-indexedに直す

dfs(K,-1,0)

x=[]
y=[]

for i in range(Q):
    xt, yt=map(int,input().strip().split(' '))
    x.append(xt-1)#0-indexedに直して入れる
    y.append(yt-1)#0-indexedに直して入れる
for i in range(Q):
    print(dist[x[i]]+dist[y[i]])
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))

l = []
for i in range(N):
    for j in range(i + 1):
        if P[i] <= P[j]:
            continue
        else:
            l.append(i)
            break
print(N - len(l))

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))

l = []
a = P[0]
for i in range(N):
    if P[i] <= a:
        a = P[i]
        continue
    else:
        l.append(i)
print(N - len(l))
### BUGGY CODE ###

inf = float("INF")
a,b,q = map(int, input().split())
s = [None] * (a + 3)
s[0:2] = [-inf,-inf]
s[-1] = inf
t = [None] * (b + 3)
t[0:2] = [-inf,-inf]
t[-1] = inf
for i in range(a):
	s[i+2] = int(input())
for i in range(b):
	t[i+2] = int(input())

from bisect import bisect_left
from collections import defaultdict

dp = defaultdict(lambda: None)

def f(s,t,x,ss,i):
  if dp[(ss,i)] != None: return abs(x - s[ss]) + dp[(ss,i)]
  tr = bisect_left(t, s[ss])
  tl = tr - 1
  dp[(ss,i)] = min(abs(s[ss] - t[tl]), abs(s[ss] - t[tr]))
  return abs(x - s[ss]) + dp[(ss,i)]


for _ in range(q):
  ans = inf
  x = int(input())
  sr = bisect_left(s, x)
  ans = min(ans, f(s,t,x,sr,0))
  ans = min(ans, f(s,t,x,sr - 1,0))
  tr = bisect_left(t, x)
  ans = min(ans, f(t,s,x,tr,1))
  ans = min(ans, f(t,s,x,tr - 1,1))
  print(ans)
  


### FIXED CODE ###

#A

"""
s = input().split("/")
if int(s[1]) <= 4:
    print("Heisei")
else:
    print("TBD")
"""
#B
"""
n = int(input())
ans = 0
for i in range(n):
    a = input().split()
    if a[1] == "JPY":
        ans += int(a[0])
    else:
        ans +=  float(a[0]) * 380000
print(ans)
"""

#C
"""
n, a, b, c = map(int, input().split())
abc = [a,b,c]
x = [int(input()) for i in range(n)]
x.sort()
ans = []
flg = 0
for i in x:
    if i in abc:
        ans.append(i)
        flg = 1
if flg:
    for i in ans:
        abc.remove(i)
        x.remove(i)

"""
#D

a, b, q = map(int, input().split())
s = [int(input()) for i in range(a)]
t = [int(input()) for i in range(b)]
s.sort()
t.sort()

import bisect


for i in range(q):
    x = int(input())
    s_l = bisect.bisect_left(s, x) - 1
    t_l = bisect.bisect_left(t, x) - 1
    s_r = s_l + 1
    t_r = t_l + 1
    if s_l == -1:
        s_l = 0
    if t_l == -1:
        t_l = 0
    if s_l == a :
        s_l = a - 1
        s_r = a - 1
    if s_r == a:
        s_r = a - 1
    if t_l == b:
        t_l = b - 1
        t_r = b - 1
    if t_r == b:
        t_r = b - 1
    ans = min(abs(t[t_l] - s[s_r]) + min(abs(t[t_l] - x), abs(s[s_r] - x)),
    abs(s[s_l] - t[t_r]) + min(abs(s[s_l] - x), abs(t[t_r] - x)),
    abs(s[s_l] - t[t_l]) + min(abs(s[s_l] - x), abs(t[t_l] - x)),
    abs(s[s_r] - t[t_r]) + min(abs(s[s_r] - x), abs(t[t_r] - x)),
    )
    
    print(ans)