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

N,W = [int(v) for v in input().split()]
items = [[int(v) for v in input().split()] for _ in range(N)]

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1,N+1):
    w,v = items[i-1]
    for cap in range(W+1):
        if cap - w >= 0:
            dp[i][cap] = max(dp[i][cap],dp[i-1][cap-w]+v)
        dp[i][cap] = max(dp[i][cap],dp[i-1][cap])

print(dp[-1][-1])


### FIXED CODE ###

N,W = [int(v) for v in input().split()]
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1,N+1):
    w,v = [int(v) for v in input().split()]
    for cap in range(W+1):
        if cap - w >= 0:
            dp[i][cap] = max(dp[i][cap],dp[i-1][cap-w]+v)
        dp[i][cap] = max(dp[i][cap],dp[i-1][cap])

print(dp[-1][-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n,q=map(int,input().split())
g=[[]for i in range(n)]
res=[0 for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

for k in range(q):
    p,x=map(int,input().split())
    res[p-1]+=x
    


def my_add(v,par):
    for vn in g[v]:
        if vn==par:
            continue
        res[vn]+=res[v]
        my_add(vn,v)

my_add(0,-1)
print(*res)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n,q=map(int,input().split())
g=[[]for _ in range(n)]
res=[0 for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)

for _ in range(q):
    p,x=map(int,input().split())
    res[p-1]+=x
    


def my_add(v,par):
    for vn in g[v]:
        if vn==par:
            continue
        res[vn]+=res[v]
        my_add(vn,v)

my_add(0,-1)
print(*res)
### BUGGY CODE ###

def main():
    S = str(input())
    K = int(input())
    N = len(S)

    tmp = [[] for _ in range(26)]
    for i in range(N):
        tmp[ord(S[i]) - ord('a')].append(i)

    lst = []
    lst_append = lst.append
    s = set()
    s_add = s.add
    for num in tmp:
        for i in num:
            for j in range(i + 1, N + 1):
                if S[i:j] in s:
                    continue
                else:
                    s_add(S[i:j])
                    lst_append(S[i:j])
        if len(s) >= K:
            lst.sort()
            print (lst[K - 1])
            # print (lst)
            return

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    S = str(input())
    K = int(input())
    N = len(S)

    tmp = [[] for _ in range(26)]
    for i in range(N):
        tmp[ord(S[i]) - ord('a')].append(i)

    lst = []
    lst_append = lst.append
    s = set()
    s_add = s.add
    for num in tmp:
        for i in num:
            for j in range(i + 1, min(N, i + K) + 1):
                if S[i:j] in s:
                    continue
                else:
                    s_add(S[i:j])
                    lst_append(S[i:j])
        if len(s) >= K:
            lst.sort()
            print (lst[K - 1])
            # print (lst)
            return

if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
for _ in range(Q):
    l, r = map(int, input().split())
    print(S[l-1:r].count('AC'))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

ans = [0]
num = 0
for x, y in zip(S[:-1], S[1:]):
    if x == 'A' and y == 'C':
        num += 1
        ans.append(num)
    else:
        ans.append(num)

for _ in range(Q):
    l, r = map(int, input().split())
    if l == 1:
        print(ans[r-1])
    else:
        b = ans[r-1]-ans[l-2]
        if S[l-1] == 'C' and S[l-2] == 'A':
            print(b-1)
        else:
            print(b)
### BUGGY CODE ###

s = input()
k = len(s)
f = 0
while f == 0: 
  s = s.replace('01', '').replace('10', '')
  if s.count('0') == 0 or s.count('1') == 0:
    f = 1 
    break
print(k - len(s))

### FIXED CODE ###

s = input()
k = len(s)
a = s.count('0')
b = s.count('1')
ans = 0
if a >= b:
  ans = k - a + b
else:
  ans = k + a - b
print(ans)
### BUGGY CODE ###

n, k, *a = map(int, open(0).read().split())
print(n - sum(sorted([a.count(i) for i in range(n)])[:-k-1:-1]))

### FIXED CODE ###

from collections import Counter
n, k, *a = map(int, open(0).read().split())
_, c = zip(*Counter(a).most_common())
print(n - sum(c[:k]))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import heapq

n,m,s,t = map(int, input().split())
s -= 1
t -= 1
e = [[] for _ in range(n)]
for _ in range(m):
    v,u,a,b = map(int, input().split())
    v -= 1
    u -= 1
    e[v].append((u,(a,b)))
    e[u].append((v,(a,b)))


inf = 10**18
def dijkstra(s,cu):
    d = [inf]*n
    d[s] = 0
    q = [s]
    heapq.heapify(q)

    while len(q)>0:
        v = heapq.heappop(q)
        for u,ud in e[v]:
            if d[u]<=d[v]+ud[cu]:
                continue
            d[u] = d[v] + ud[cu]
            heapq.heappush(q, u)
    return d


da = dijkstra(s,0)
db = dijkstra(t,1)
res = [0]*n
res[n-1] = da[n-1]+db[n-1]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], da[i]+db[i])

x = 10**15
for i in range(n):
    print(x - res[i])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import heapq
n,m,s,t = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    u,v,a,b = map(int, input().split())
    g[u].append((v,(a,b)))
    g[v].append((u,(a,b)))

inf = 10**18
def dijkstra(s, currency):
    d = [inf]*(n+1)
    d[s] = 0

    que = [(d[s],s)]
    heapq.heapify([que])
    while len(que)>0:
        _,v = heapq.heappop(que)
        for u,c in g[v]:
            if d[v]+c[currency]>=d[u]:
                continue
            d[u] = d[v]+c[currency]
            heapq.heappush(que, (d[u], u))
    return d

yen_c = dijkstra(s,0)
snuuk_c = dijkstra(t,1)

res = [0]*n
res[n-1] = yen_c[n] + snuuk_c[n]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], yen_c[i+1]+snuuk_c[i+1])

for r in res:
    print(10**15-r)
### BUGGY CODE ###

import itertools
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
kabeset = set()

for i in range(h):
	for j in range(w):
		if chizu[i][j] == "#":
			kabeset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
kouho = 1
mode = 1
cost = 0

while kouho > 0:
	while kouho > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			kouho -= 1
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if 0 <= k[0] < h and 0 <= k[1] < w:
					if not k in kabeset:
						if not k in setmada:
							if not k in settansaku:
								setmada.add(k)
								kouho += 1
								if k == goal:
									mode = 0
								
	if mode == 0:
		break
	
	cost += 1
	newkouho = len(stock)
	while newkouho > 0:
		for i, j in list(stock):
			stock.remove((i, j))
			newkouho -= 1
			for k in itertools.product(range(i-2, i+3), range(j-2, j+3)):
				if 0 <= k[0] < h and 0 <= k[1] < w:
					if not k in kabeset:
						if not k in setmada:
							if not k in settansaku:
								setmada.add(k)
								kouho += 1
								if k == goal:
									mode = 0
								
	if mode == 0:
		break
	
	kouho = len(setmada)

if mode == 0:
	print(cost)
else:
	print(-1)

### FIXED CODE ###

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)
### BUGGY CODE ###

k = int(input())
i = 1
a = 7
while a % k != 0:
  i += 1
  a = 10*a + 7
  if i == 10**9+7:
    i = -1
    break

print(i)
  


### FIXED CODE ###

k = int(input())
i = 1
a = 7
a = a % k
while a != 0:
  i += 1
  a = (10*a + 7) % k
  if i == 10**6:
    i = -1
    break

print(i)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
sum = 0

for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            sum += gcd(a, b, c)

print(sum)


### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
sum = 0

for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            sum += gcd(a, b, c)

print(sum)
### BUGGY CODE ###

from fractions import gcd
N = int(input())
A = [0 for _ in range(N)]
g = 0
for i,a in enumerate(map(int,input().split(" "))):
    A[i] = a
    if i == 0:
        g = a
    g = g*a//gcd(a,g)
ans = 0
A = tuple(A)
for a in A:
    ans += g//a
    ans %= (10**9+7)
print(ans)

### FIXED CODE ###

def gcd(a,b):
    while b:a,b=b,a%b
    return a
def lcm(a,b):
    return a*b//gcd(a,b)

N = int(input())
A = tuple(map(int,input().split(" ")))
ans = 0
mod = 10**9+7
l = 1
for i in range(N):
    l = lcm(l,A[i])
l %= mod

for i in A:
    ans += l*pow(i,mod-2,mod)
    ans %= mod

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

N = int(input())
P = list(map(int, input().split()))
c = 0
for i in range(N):
    if all([P[i] <= p for p in P[:i+1]]):
        c += 1
    #if P[i] >= P[i + 1]:
     #   c += 1
print(c)


### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
c = 0
m = N+1
for i in range(N):
    if P[i] <= m:
        c += 1
    m = min(P[i], m)
print(c)
### BUGGY CODE ###

import sys
inf = float('inf')

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N, Ma, Mb = map(int, input().split())
    wa = [None]
    wb = [None]
    costs = [None]

    for i in range(N):
        a, b, c = map(int, input().split())
        wa.append(a)
        wb.append(b)
        costs.append(c)

    dp = [[[inf]*(10*N + 1) for j in range(10*N + 1)]
                           for k in range(N + 1)]

    # debug(dp, locals())
    dp[0][0][0] = 0

    for k in range(1, N + 1):
        for a in range(10*N + 1):
            for b in range(10*N + 1):
                dp[k][a][b] = dp[k - 1][a][b]
                if a - wa[k] >= 0 and b - wb[k] >= 0:
                    dp[k][a][b] = min(dp[k][a][b],
                                        dp[k - 1][a - wa[k]][b - wb[k]] + costs[k])

    min_c = inf

    for a in range(1, 10*N + 1):
        for b in range(1, 10*N + 1):
            if a * Mb == b * Ma:
                min_c = min(min_c, dp[N][a][b])

    if min_c == inf:
        ans = -1
    else:
        ans = min_c

    print(ans)

if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N, Ma, Mb = map(int, input().split())
    a_w = []
    b_w = []
    costs = []

    for i in range(N):
        a, b, c = map(int, input().split())
        a_w.append(a)
        b_w.append(b)
        costs.append(c)

    dp = [[[-1]*(10*N + 1) for j in range(10*N + 1)]
            for k in range(2)]

    dp[0][0][0] = 0
    dp[1][0][0] = 0

    for i in range(N):
        for a in range(10*N + 1):
            for b in range(10*N + 1):
                if a - a_w[i] >= 0 and b - b_w[i] >= 0:
                    if dp[0][a - a_w[i]][b - b_w[i]] >= 0:
                        if dp[1][a][b] == -1:
                            dp[1][a][b]= dp[0][a - a_w[i]][b - b_w[i]] + costs[i]
                        else:
                            min_ = min(dp[1][a][b],
                                       dp[0][a - a_w[i]][b - b_w[i]] + costs[i])
                            dp[1][a][b] = min_
        
        for k in range(10*N + 1):
            dp[0][k] = dp[1][k][:]

        # for i in range(10*N + 1):
            # print(*dp[0][i], file=sys.stderr)


    min_cost = float('inf')

    for a in range(10*N + 1):
        for b in range(10*N + 1):
            if a != 0 and b != 0:
                if a * Mb == b * Ma and dp[1][a][b] > 0:
                    min_cost = min(min_cost, dp[1][a][b])

    if min_cost == float('inf'):
        ans = -1
    else:
        ans = min_cost

    print(ans)


if __name__ == '__main__':
    solve()
### BUGGY CODE ###

import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())), dtype=object)

ans = np.prod(a)
if ans > 10**18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
if 0 in a:
  print(0)
  exit()
for i in a:
  ans*=i
  if ans>10**18:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

def main():
    k = int(input())
    que = [1,2,3,4,5,6,7,8,9]
    cnt = 0
    while cnt!= k:
        x = que.pop(0)
        cnt += 1
        if x%10==0:
            que.append(x*10)
            que.append(x*10+1)
        elif x%10==9:
            que.append(x*10+8)
            que.append(x*10+9)
        else:
            que.append(x*10+x%10-1)
            que.append(x*10+x%10)
            que.append(x*10+x%10+1)
    print(x)

            
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    from queue import Queue
    k = int(input())
    q = Queue()
    for i in range(1,10):
        q.put(i)
    cnt = 0
    while cnt!= k:
        x = q.get()
        cnt += 1
        if x%10!=0:
            q.put(x*10+x%10-1)
        q.put(x*10+x%10)
        if x%10!=9:
            q.put(x*10+x%10+1)
    print(x)

            
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# coding: utf-8
from bisect import bisect_left, bisect_right


def solve(*args: str) -> str:
    n, m, v, p = map(int, args[0].split())
    A = list(map(int, args[1].split()))
    A.sort()

    ret = 0
    for i in range(n):
        pts = 0
        for j in range(n):
            if j <= i or n-p < j:
                pts += m
            else:
                pts += A[i]+m-A[j]

        if m*v <= pts:
            ret += 1

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n, m, v, p = map(int, args[0].split())
    A = list(map(int, args[1].split()))
    A.sort()

    left, right = -1, n

    while left+1 < right:
        i = (left+right)//2

        if A[i]+m < A[n-p]:
            left = i
            continue

        pts = m*min(n, i+p)
        for j in range(i+1, n-(p-1)):
            pts += max(0, A[i]+m-A[j])

        if m*v <= pts:
            right = i
        else:
            left = i

    return str(n-right)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, a, b = MAP()

def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, int(y/2)) ** 2 % mod
    else:
        return power(x, int((y-1)/2)) ** 2 * x % mod
    
a_max = 2 * 10 ** 5
# a, bの最大値+2
fact = [1] * (a_max + 2)
# 逆元
for i in range(1, a_max + 1):
    fact[i] = (fact[i-1] * i) % mod

# combination
def C(n, a):
    tmp = 1
    for i in range(n, n-a, -1):
        tmp = (tmp * i) % mod
    return tmp * power(fact[a], mod - 2)

print((pow(2, n) - 1 - C(n, a) - C(n, b)) % mod)


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, a, b = MAP()

def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, int(y/2)) ** 2 % mod
    else:
        return power(x, int((y-1)/2)) ** 2 * x % mod
ans = power(2, n) - 1
    
a_max = 2 * 10 ** 5
# a, bの最大値+2
fact = [1] * (a_max + 2)
# 逆元
for i in range(1, a_max + 1):
    fact[i] = (fact[i-1] * i) % mod
# combination
def C(n, a):
    tmp = 1
    for i in range(n, n-a, -1):
        tmp = (tmp * i) % mod
    return tmp * power(fact[a], mod - 2)

print((ans - C(n, a) - C(n, b)) % mod)
### BUGGY CODE ###

#!python3

INF = 10 ** 15


# input
N = int(input())
a, b, c, d = [None] * N, [None] * N, [None] * N, [None] * N
for i in range(N):
    a[i], b[i] = list(map(int, input().split()))
for i in range(N):
    c[i], d[i] = list(map(int, input().split()))


class MaxFlow():

    def __init__(self, n):
        self.n = n
        self.c = [[0] * n for _ in range(n)]
        self.visit = [False] * n
        self.link = [set() for _ in range(n)]

    def add_link(self, x, y, capa):
        self.c[x][y] += capa
        self.link[x].add(y)
    
    def solve(self, t, v, f):
        if v == t:
            return f
        self.visit[v] = True
        
        w = 0
        
        for i in self.link[v]:
            if self.visit[i] or self.c[v][i] == 0:
                continue
            d = self.solve(t, i, min(f - w, self.c[v][i]))
            if d > 0:
                self.c[v][i] -= d
                self.c[i][v] += d
                self.link[i].add(v)
                w += d
                if w == f:
                    break
        
        self.visit[v] = False
        return w
        

def main():
    w = MaxFlow(2 * N + 2)
    for i in range(N):
        w.add_link(0, i + 1, 1)
        w.add_link(N + i + 1, 2 * N + 1, 1)
        for j in range(N):
            if a[i] < c[j] and b[i] < d[j]:
                w.add_link(i + 1, N + j + 1, 1)
    
    ans = w.solve(2 * N + 1, 0, INF)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!python3

INF = 10 ** 15


# input
N = int(input())
a, b, c, d = [None] * N, [None] * N, [None] * N, [None] * N
for i in range(N):
    a[i], b[i] = list(map(int, input().split()))
for i in range(N):
    c[i], d[i] = list(map(int, input().split()))


class MaxFlow():

    def __init__(self, n):
        self.n = n
        self.c = [[0] * n for _ in range(n)]
        self.visit = [False] * n

    def add_link(self, x, y, capa):
        self.c[x][y] += capa
    
    def dfs(self, v, t, f):
        if v == t:
            return f
        self.visit[v] = True
        
        for i in range(self.n):
            if self.visit[i] or self.c[v][i] == 0:
                continue
            d = self.dfs(i, t, min(f, self.c[v][i]))
            if d > 0:
                self.c[v][i] -= d
                self.c[i][v] += d
                return d
                
        return 0

    
    def max_flow(self, s, t):
        ans = 0
        while True:
            f = self.dfs(s, t, INF)
            self.visit = [False] * self.n
            if f == 0:
                return ans
            else:
                ans += f
        

def main():
    w = MaxFlow(2 * N + 2)
    for i in range(N):
        w.add_link(0, i + 1, 1)
        w.add_link(N + i + 1, 2 * N + 1, 1)
        for j in range(N):
            if a[i] < c[j] and b[i] < d[j]:
                w.add_link(i + 1, N + j + 1, 1)
    
    ans = w.max_flow(0, 2 * N + 1)
    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import deque
N = int(input())
A = deque(map(int, input().split()))
ans = 1
for i in range(N):
    ans *= A.pop()
if ans > 10 ** 18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

#from collections import deque
def hanbun(L):
    N = len(L)
    flag = N % 2
    N = N // 2
    ans = []
    for i in range(N):
        ans.append(L[2 * i] * L[2 * i + 1])
    if flag == 1:
        ans.append(L[-1])
    return(ans)

N = int(input())
A = list(map(int, input().split()))
while len(A) > 1:
    A = hanbun(A)
ans = A[0]
if ans > 10 ** 18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

A,B,Q=map(int,input().split())
s=[]
t=[]
for i in range(A):
  s.append(int(input()))
for i in range(B):
  t.append(int(input()))
for i in range(Q):
  x=int(input())
  s1=s[:]
  s1.append(x)
  s1.sort()
  j=s1.index(x)
  if j==0:
    kouhoA=[s[j]]
  elif j==A:
    kouhoA=[s[j-1]]
  else:
    kouhoA=[s[j],s[j-1]]
  t1=t[:]
  t1.append(x)
  t1.sort()
  k=t1.index(x)
  if k==0:
    kouhoB=[t[k]]
  elif k==B:
    kouhoB=[t[k-1]]
  else:
    kouhoB=[t[k],t[k-1]]
  if len(kouhoA)==1:
    
    if len(kouhoB)==1:
      a=abs(kouhoA[0]-kouhoB[0])
      ans=min([abs(x-kouhoA[0])+a,abs(x-kouhoB[0])+a])
    else:
      u=abs(x-kouhoA[0])
      a=abs(kouhoA[0]-kouhoB[0])
      b=abs(kouhoA[0]-kouhoB[1])
      ans=min([u+a,abs(x-kouhoB[0])+a,u+b,abs(x-kouhoB[1])+b])
  else:
    if len(kouhoB)==1:
      a=abs(kouhoA[0]-kouhoB[0])
      c=abs(kouhoB[0]-kouhoA[1])
      v=abs(x-kouhoB[0])
      ans=min([abs(x-kouhoA[0])+a,v+a,abs(x-kouhoA[1])+c,v+c])
    else:
      u=abs(x-kouhoA[0])
      a=abs(kouhoA[0]-kouhoB[0])
      b=abs(kouhoA[0]-kouhoB[1])
      c=abs(kouhoB[0]-kouhoA[1])
      d=abs(kouhoA[1]-kouhoB[1])
      v=abs(x-kouhoB[0])
      w=abs(x-kouhoA[1])
      y=abs(x-kouhoB[1])
      ans=min([u+a,v+a,w+d,y+d,w+c,v+c,u+b,y+b])
  print(ans)


### FIXED CODE ###

import bisect
A,B,Q=map(int,input().split())
s=[]
t=[]
for i in range(A):
  s.append(int(input()))
for i in range(B):
  t.append(int(input()))
for i in range(Q):
  x=int(input())
  j=bisect.bisect_left(s,x)
  if j==0:
    kouhoA=[s[j]]
  elif j==A:
    kouhoA=[s[j-1]]
  else:
    kouhoA=[s[j],s[j-1]]
  k=bisect.bisect_left(t,x)
  if k==0:
    kouhoB=[t[k]]
  elif k==B:
    kouhoB=[t[k-1]]
  else:
    kouhoB=[t[k],t[k-1]]
  if len(kouhoA)==1:
    
    if len(kouhoB)==1:
      a=abs(kouhoA[0]-kouhoB[0])
      ans=min([abs(x-kouhoA[0])+a,abs(x-kouhoB[0])+a])
    else:
      u=abs(x-kouhoA[0])
      a=abs(kouhoA[0]-kouhoB[0])
      b=abs(kouhoA[0]-kouhoB[1])
      ans=min([u+a,abs(x-kouhoB[0])+a,u+b,abs(x-kouhoB[1])+b])
  else:
    if len(kouhoB)==1:
      a=abs(kouhoA[0]-kouhoB[0])
      c=abs(kouhoB[0]-kouhoA[1])
      v=abs(x-kouhoB[0])
      ans=min([abs(x-kouhoA[0])+a,v+a,abs(x-kouhoA[1])+c,v+c])
    else:
      u=abs(x-kouhoA[0])
      a=abs(kouhoA[0]-kouhoB[0])
      b=abs(kouhoA[0]-kouhoB[1])
      c=abs(kouhoB[0]-kouhoA[1])
      d=abs(kouhoA[1]-kouhoB[1])
      v=abs(x-kouhoB[0])
      w=abs(x-kouhoA[1])
      y=abs(x-kouhoB[1])
      ans=min([u+a,v+a,w+d,y+d,w+c,v+c,u+b,y+b])
  print(ans)