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

def main():
  from bisect import bisect
  n,k,*a=map(int,open(0).read().split())
  a.sort()
  i=bisect(a,0)
  a,b=a[i:],a[i-1::-1]
  n,m=len(a),len(b)
  ok=10**18
  ng=-ok
  while ok-ng>1:
    x=(ok+ng)//2
    s=0
    if x>=0:
      i=n
      for y in a:
        while i and a[i-1]*y>x:i-=1   
        s+=i
        if y*y<=x:s-=1
      i=m
      for y in b:
        while i and b[i-1]*y>x:i-=1
        s+=i
        if y*y<=x:s-=1
      s=s//2+n*m
    else:
      i=m
      for y in a:
        while i and b[i-1]*y<=x:i-=1
        s+=m-i
    if s>=k:ok=x
    else:ng=x
  print(ok)
main()

### FIXED CODE ###

from bisect import*
def solve(x):
  s=t=0
  i=n
  j=-1
  for y in a:
    while i and a[i-1]*y>x:i-=1
    while j+1<m and b[j+1]*y<=x:j+=1
    s+=j+1
    t+=i
    if y*y<=x:t-=1
  s+=t//2
  t=0
  i=m
  for y in c:
    while i and c[i-1]*y>x:i-=1
    t+=i
    if y*y<=x:t-=1
  s+=t//2
  return s
n,k,*t=map(int,open(0).read().split())
t.sort()
i=bisect(t,0)
a,b,c=t[i:],t[:i],t[i-1::-1]
n,m=len(a),len(b)
ok=10**18
ng=-ok
while ok-ng>1:
  mid=(ok+ng)//2
  if solve(mid)>=k:ok=mid
  else:ng=mid
print(ok)
### BUGGY CODE ###

arr = list(input())

ans = [0]*len(arr)

for i in range(len(arr)):
    if arr[i] == "R":
        move = 0
        
        while arr[i + move] == "R":
            move +=1
        
        if move % 2 ==0:
            ans[i + move] +=1
        else:
            ans[i+move-1] +=1

    if arr[i] == "L":
        move = 0
        
        while arr[i + move] == "L":
            move -=1
        
        if move % 2 ==0:
            ans[i + move] +=1
        else:
            ans[i+move+1] +=1       

        
print(" ".join(map(str,ans)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
arr=list(ss())
temp=0
centr=0
centl=0
ans=[0]*len(arr)

childeven=0
childodd=0

for i in range(len(arr)):
    if arr[i]=="R":
        if temp==0:
            centr=i
            if i%2==0:
                childeven+=1
            else:
                childodd+=1
        else:
            childeven=0
            childodd=0
            centr=i
            temp=0
            if i%2==0:
                childeven+=1
            else:
                childodd+=1

    else:
        if temp==0:
            temp=1
            centl=i

            if i%2==1:
                ans[centr]+=childeven
                ans[centr+1]+=childodd
            else:
                ans[centr]+=childodd
                ans[centr+1]+=childeven
                
            if (i-centl)%2==0:
                ans[centl]+=1
            else:
                ans[centl-1]+=1

        else:
            if (i-centl)%2==0:
                ans[centl]+=1
            else:
                ans[centl-1]+=1
    #print(ans,childeven,childodd)

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

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
Cm = []
Cp = []
for i in range(N):
	if(A[i]-B[i]<0):
		Cm.append(A[i]-B[i])
	elif(A[i]-B[i]>0):
		Cp.append(A[i]-B[i])
Cm.sort()
Cp.sort()

cnt = 0
nowCp = 0
j = 0

for i in range(len(Cp)):

	if(sum(Cp)<abs(sum(Cm))):
		print(-1)
		break
	elif(len(Cm) == 0):
		print(0)
		break

	nowCp += int(Cp[len(Cp)-(i+1)])
	while(j<len(Cm)):
		if(nowCp>=abs(Cm[len(Cm)-j-1])):
			nowCp -= abs(Cm[len(Cm)-j-1])
			cnt += 1
			j += 1
		else:
			break

	if(cnt == len(Cm)):
		print(cnt+i+1)
		break

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
Cm = []
Cp = []
for i in range(N):
	if(A[i]-B[i]<0):
		Cm.append(A[i]-B[i])
	elif(A[i]-B[i]>0):
		Cp.append(A[i]-B[i])
Cm.sort()
Cp.sort()


if(len(Cm) == 0):
	print(0)
	exit(0)
if(sum(Cp)<abs(sum(Cm))):
	print(-1)
	exit(0)

j=0
i = 0
nowCp = int(Cp[len(Cp)-i-1])


while(j<len(Cm)):
	if(nowCp>=abs(Cm[j])):
		nowCp -= abs(Cm[j])
		j += 1
	elif(nowCp<abs(Cm[j]) and i<len(Cp)):
		i += 1
		nowCp += int(Cp[len(Cp)-i-1])

	else:
		break
	

if(j == len(Cm)):
	print(j+i+1)
else:
	print(-1)
### BUGGY CODE ###

a, b, x = map(int, input().split())

count = 0
i = 0
while x*i <= b:
    if a <= x*i:
        count += 1
    i += 1
print(count)

### FIXED CODE ###

# B
def how_many(a, b, c):
    # 1からa-1までのcの倍数の個数と1からbまでのcの倍数の個数を求める
    A, B = (a-1)//c, b//c
    # それらを引いて答えが求まる
    return B-A

a, b, x = map(int, input().split())

print(how_many(a, b, x))
### BUGGY CODE ###

N = int(input())
i = 1
power = 1
while i <= N:
    power = power * i
    i += 1
print(power%(10**9+7))

### FIXED CODE ###

import math
N = int(input())
power = math.factorial(N)
print(power%(10**9+7))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import bisect
import numpy as np
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
x = max(max(a),max(b)).bit_length()+1
b = np.array(b,dtype=np.int32)
ans = 0
for i in range(1,x+1):
  d = sorted(b&(1<<i)-1)
  t = 1<<(i-1)
  anstmp = 0
  for j in range(n):
    y = a[j]&(1<<i)-1
    t1 = np.searchsorted(d,t-y)
    t2 = np.searchsorted(d,2*t-y)
    t3 = np.searchsorted(d,3*t-y)
    anstmp += (t2-t1)+(n-t3)
  if anstmp%2:
    ans += t
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
x = max(max(a),max(b)).bit_length()+1
a = np.array(a,dtype=np.int32)
b = np.array(b,dtype=np.int32)
ans = 0
for i in range(1,x+1):
  c = a&(1<<i)-1
  d = b&(1<<i)-1
  d.sort()
  t = 1<<(i-1)
  anstmp = 0
  t1 = np.searchsorted(d,t-c).sum()
  t2 = np.searchsorted(d,2*t-c).sum()
  t3 = np.searchsorted(d,3*t-c).sum()
  anstmp += (t2-t1)+(n-t3)
  if anstmp%2:
    ans += t
print(ans)
### BUGGY CODE ###

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

ans=0
for i in range(n+1):
  for j in range(n+1):
    for k in range(n+1):
      if i+j+k==s:
        ans+=1
print(ans)

### FIXED CODE ###

k,s=map(int,input().split())

ans=0
for i in range(k+1):
  for j in range(k+1):
    z=s-i-j
    if 0<=z<=k:
      ans+=1
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
for k in range(K):
    B = [0] * N
    for n in range(N):
        l = max(0, n- A[n])
        r = min(N-1, n+A[n])
        B[l] += 1
        if r +1 < N:
            B[r+1] -= 1
    #print(B)
    for i in range(N-1):
        B[i+1] += B[i]
    #print(B)
    if sum(A) == N**2:
        break
    else:
        A = B[:]
ans = ''
for a in A:
    ans += str(a) + ' '
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
for k in range(K):
    B = [0] * N
    for n in range(N):
        l = max(0, n- A[n])
        r = min(N-1, n+A[n])
        B[l] += 1
        if r +1 < N:
            B[r+1] -= 1
    #print(B)
    for i in range(N-1):
        B[i+1] += B[i]
    #print(B)
    if sum(A) == N**2:
        break
    else:
        A = B[:]
print(*A)
### BUGGY CODE ###

def make_ps(n):
    tbl = [False, True, False, False, False, True] * (n // 6 + 1)
    for i in range(1, 4):
        tbl[i] = not tbl[i]
    p, stp, sqrt = 5, 2, n ** 0.5
    while p < sqrt:
        for i in range(p ** 2, n, 2 * p):
            tbl[i] = False
        while True:
            p += stp
            stp = 6 - stp
            if tbl[p]:
                break
    return [i for i in range(n) if tbl[i]]
while True:
    n = int(input())
    ps = make_ps(n)
    if not n:
        break
    if n % 2:
        print(1 if n - 2 in ps else 0)
    else:
        res = 0
        for p in ps:
            if p > n / 2:
                break
            if n - p in ps:
                res += 1
        print(res)

### FIXED CODE ###

def make_tbl(n):
    tbl = [False, True, False, False, False, True] * (n // 6 + 1)
    for i in range(1, 4):
        tbl[i] = not tbl[i]
    p, stp, sqrt = 5, 2, n ** 0.5
    while p < sqrt:
        for i in range(p ** 2, n, 2 * p):
            tbl[i] = False
        while True:
            p += stp
            stp = 6 - stp
            if tbl[p]:
                break
    return tbl
tbl = make_tbl(50000)
ps = [i for i in range(50000) if tbl[i]]
while True:
    n = int(input())
    if not n:
        break
    res = 0
    if n % 2:
        if tbl[n - 2]:
            res += 1
    else:
        res = 0
        for p in ps:
            if 2 * p > n:
                break
            if tbl[n - p]:
                res += 1
    print(res)
### BUGGY CODE ###


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

edge = [[] for _ in range(n)]

counter = [0] * n

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

for _ in range(q):
    a, b = map(int, input().split())
    counter[a-1] += b

parent = [0]
visited = []

for i in parent:
    for v in edge[i]:
        if v in parent:
            continue
        parent.append(v)
        counter[v] += counter[i]
        
for i in range(n):
    print(counter[i], end=" ")
print("")

### FIXED CODE ###


# n, q = map(int, input().split())

# edge = [[] for _ in range(n)]

# counter = [0] * n

# for _ in range(n-1):
#     a, b = map(int, input().split())
#     edge[a-1].append(b-1)
#     edge[b-1].append(a-1)

# for _ in range(q):
#     a, b = map(int, input().split())
#     counter[a-1] += b

# parent = [0]
# visited = []

# for i in parent:
#     visited.append(i)
#     for v in edge[i]:
#         if v in visited:
#             continue
#         parent.append(v)
#         counter[v] += counter[i]
        
# for i in range(n):
#     print(counter[i], end=" ")
# print("")

import sys
input = sys.stdin.readline
 
N, Q = [int(x) for x in input().split()]
 
edge = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = [int(x) for x in input().split()]
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
 
cost = [0] * N
for _ in range(Q):
    p, x = [int(x) for x in input().split()]
    cost[p - 1] += x
 
next = [0]
s_next = {0}
for i in next:
    for v in edge[i]:
        if v in s_next:
            continue
        s_next.add(v)
        next.append(v)
        cost[v] += cost[i]
 
print(" ".join(map(str, cost)))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
h,w=map(int,input().split())
s=[list(input())for i in range(h)]
a=[[float("inf")]*w for i in range(h)]
def f(x,y,t):
    if 0<=x<h and 0<=y<w:
        if s[x][y]=="#":
            a[x][y]=0
            f(x,y+1,1)
            f(x+1,y,1)
            f(x-1,y,1)
            f(x,y-1,1)
        else:
            if a[x][y]>t:
                a[x][y]=t
                f(x,y+1,t+1)
                f(x+1,y,t+1)
                f(x-1,y,t+1)
                f(x,y-1,t+1)
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            f(i,j,0)
            break
print(max(max(i)for i in a))

### FIXED CODE ###

import numpy as np
from scipy.ndimage import distance_transform_cdt as d
h,w=map(int,input().split())
s=[[1 if i=="." else 0 for i in input()]for i in range(h)]
a=d(s,metric='taxicab')
print(a.max())
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc082/tasks/arc087_b

"""
import sys
from sys import stdin
input = stdin.readline


def solve(s, gx, gy):
    n = len(s)
    forwards = [len(x) for x in s.split('T')]

    H = len(forwards)
    dpx = [False] * (n * 2 + 2)
    dpy = [False] * (n * 2 + 2)
    dpx[n + forwards[0]] = True
    dpy[n] = True

    for f in forwards[2::2]:
        if f == 0:
            continue
        n_move = dpx[f:] + [False] * f
        p_move = [False] * f + dpx[:-f]
        t = [a or b for a, b in zip(n_move, p_move)]
        dpx = t

    for f in forwards[1::2]:
        if f == 0:
            continue
        n_move = dpy[f:] + [False] * f
        p_move = [False] * f + dpy[:-f]
        t = [a or b for a, b in zip(n_move, p_move)]
        dpy = t

    if dpy[gy + n] is True and dpx[gx + n] is True:
        return 'Yes'
    else:
        return 'No'


def main(args):
    s = input().strip()
    gx, gy = map(int, input().split())
    # s = 'FTFFTFFFT'
    # gx, gy = 4, 2
    ans = solve(s, gx, gy)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
    


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc082/tasks/arc087_b

"""
import sys
from sys import stdin
input = stdin.readline


def check_x(forwards):
    n = sum(forwards[::2])      #  x軸方向への最大移動量
    dpx = [False] * (n * 2 + 1) #  真ん中を0として、±両方向のdp領域を確保
    dpx[forwards[0] + n] = True #  最初は0からプラス方向に移動

    for f in forwards[2::2]:
        if f == 0:
            continue
        n_move = dpx[f:] + [False]*f
        p_move = [False]*f + dpx[:-f]
        t = [a or b for a, b in zip(n_move, p_move)]
        dpx = t
    return dpx, n


def check_y(forwards):
    n = sum(forwards[1::2])
    dpy = [False] * (n * 2 + 1)
    dpy[n] = True

    for f in forwards[1::2]:
        if f == 0:
            continue
        n_move = dpy[f:] + [False]*f
        p_move = [False]*f + dpy[:-f]
        t = [a or b for a, b in zip(n_move, p_move)]
        dpy = t
    return dpy, n


def solve(s, gx, gy):
    forwards = [len(x) for x in s.split('T')] #  進む歩数情報の数字に変換
    dpx, zx = check_x(forwards)
    dpy, zy = check_y(forwards)

    if zx < abs(gx):
        return 'No'
    if zy < abs(gy):
        return 'No'
    if dpx[gx + zx] is True and dpy[gy + zy] is True:
        return 'Yes'
    else:
        return 'No'


def main(args):
    s = input().strip()
    gx, gy = map(int, input().split())
    # s = 'F'
    # gx, gy = -1, 0
    ans = solve(s, gx, gy)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

n=int(input())
num=list(map(int,input().split()))

sum=1
for i in range(n):
    sum*=num[i]
    if sum==0:
        print(0)
        break
else:
    if sum>10**18:
        print(-1)
    else:
        print(sum)

### FIXED CODE ###

n=int(input())
num=list(map(int,input().split()))

sum=1
if 0 in num:
    print(0)
else:
    for i in range(n):
        sum*=num[i]
        if sum>10**18:
            print(-1)
            break
    else:
        print(sum)
### BUGGY CODE ###

from itertools import combinations
N = int(input())
A = list(map(int, input().split()))
_sum = 0
k = 10**9+7
com = combinations(A,2)
for AA in com:
    _sum += (AA[0]*AA[1])%k
    _sum %= k
print(_sum%k)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 1000000007
S = 0
_sum = 0
for i in range(N):
    S += A[i]
    S %= mod
for i in range(N):
    S -= A[i]
    if S<0:
        S += mod
    _sum += A[i]*S
    _sum %= mod

print(_sum)
### BUGGY CODE ###

MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
s = 0
m = 1
for i in range(60):
    c = 0
    for j in range(n):
        c += a[j] & m
    c //= m
    s = (s + m*c*(n-c))%MOD
    m <<= 1
print(s)

### FIXED CODE ###

MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
s = 0
m = 1
for i in range(60):
    c = sum(ai & m for ai in a)
    c //= m
    s = (s + m*c*(n-c))%MOD
    m <<= 1
print(s)
### BUGGY CODE ###

#!/usr/bin/env python3
def main():
    N, K = map(int, input().split())
    H = [int(x) for x in input().split()] + [0] * 200

    INF = 10 ** 10
    dp = [INF] * 10 ** 6
    dp[0] = 0
    for i in range(N):
        for k in range(1, K + 1):
            dp[i + k] = min(dp[i + k], dp[i] + abs(H[i] - H[i + k]))
    print(dp[N - 1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def resolve():
    import sys
    
    readline = sys.stdin.readline

    N, K = map(int, readline().split())
    h = [int(x) for x in readline().split()]

    inf = float('inf')
    dp = [inf] * N
    dp[0] = 0

    for i in range(1, N):
        leng = i + 1 if i < K else K + 1
        for j in range(leng):
            cal = dp[i - j] + abs(h[i] - h[i - j])
            if dp[i] > cal:
                dp[i] = cal

    print(dp[-1])
            

resolve()
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]
def fact(n):
    if n==0:
        return 1
    else:
        return n*fact(n-1) % p
    
def mod_combination(n, k, mod):
    # nCk (mod m)
    def mod_permutation(n, k, mod):
        if n<=k:
            return 1
        else:
            return (n * mod_permutation(n-1,k,mod))%mod

    def mod_inv_permutation(k, mod):
        k, mod = int(k), int(mod)
        if k<=1:
            return 1
        else:
            return (pow(k,mod-2,mod) * mod_inv_permutation(k-1, mod))%mod

    return (mod_permutation(n,n-k,mod) * mod_inv_permutation(k, mod))%mod

X = [[0,0],[0,1,0]]
p = 10**9 + 7
for i in range(2, N+1):
#    print ("i=",i)
    s = [0] * (i+2)
    for j in range(i):
        a = j + 1 - 1
        b = i - (j + 1)
#        print (i, j, a, b)
#        print ("Bef", s)
        for k in range(a):
#            print ("s[", k+1, "] +=", X[a][k+1]*mod_combination(a+b,a,p)*fact(b)+fact(i-1))
            s[k+1] += ((X[a][k+1]*mod_combination(a+b,a,p) % p)*fact(b) % p +fact(i-1)) % p
        for k in range(b):
#            print ("s[", i-k, "] +=", X[b][k+1]*mod_combination(a+b,a,p)*fact(a)+fact(i-1))
            s[i-k] += ((X[b][k+1]*mod_combination(a+b,a,p) % p) *fact(a) % p +fact(i-1)) % p
#        print ("s[", j+1, "] +=", fact(i-1))
        s[j+1] += fact(i-1)
#        print ("Aft", s)
    X.append(s)
#    print (X)

ans = 0
for i in range(N):
    ans += X[N][i+1] * A[i]
    ans %= p
print (ans)

### FIXED CODE ###

def mod_inv(n,p):
    if n<0:
        return - mod_inv(-n,p) % p
    if n>p:
        return mod_inv(n % p, p)
    
    def mod_inv_calc(a,b):
        if b==0:
            return (a,1)
        else:
            s,t = mod_inv_calc(b, a % b)
            d = a//b
            return (t, -t*d+s)

    return mod_inv_calc(p,n)[1] % p

N = int(input())
A = [int(a) for a in input().split()]
p = 10**9+7
inv_list = [mod_inv(i+1,p) for i in range(N+2)]

fact_list = [1]
for i in range(N):
    fact_list.append(fact_list[i] * (i+1) % p)
s = 0
sum_list = [inv_list[i] * fact_list[N] % p for i in range(N+2)]

for i in range(N):
    s += inv_list[i]
    
s *= fact_list[N]
s %= p
ans = 0
for i in range(N):
    ans += A[i]*s
    ans %= p
    s += (sum_list[i+1] - sum_list[N-i-1])
    s %= p
    
print (ans)
### BUGGY CODE ###

n = int(input())
cc = []
ss = []
ff = []
for i in range(n-1):
    c, s, f = list(map(int, input().split()))
    cc.append(c)
    ss.append(s)
    ff.append(f)
for l in range(n-1):
    ans = ss[l]+cc[l]
    for k in range(l+1, n-1):
        temp = ss[k]
        while temp < ans:
            temp += ff[k]
        ans = temp + cc[k]
    print(ans)
print(0)



### FIXED CODE ###

n = int(input())
cc = []
ss = []
ff = []
for i in range(n-1):
    c, s, f = list(map(int, input().split()))
    cc.append(c)
    ss.append(s)
    ff.append(f)
for l in range(n-1):
    ans = ss[l]+cc[l]
    for k in range(l+1, n-1):
        temp = ss[k]
        while temp < ans:
            temp += ff[k]
        ans = temp + cc[k]
    print(ans)
print(0)
### BUGGY CODE ###

import itertools
while 1:
	N,M = map(int,raw_input().split())
	if N == 0: break
	P = set([int(raw_input()) for i in range(N)])
	ans = 0
	for i in range(2,5):
		for p in itertools.combinations_with_replacement(P,i):
			if ans < sum(p) <= M:
				ans = sum(p)
	print ans

### FIXED CODE ###

from bisect import *
while 1:
	N,M = map(int,raw_input().split())
	if N == 0: break
	P = [int(raw_input()) for i in range(N)] + [0]
	P = sorted(set(i+j for i in P for j in P))
	s = bisect(P,M) - 1
	print max(i + P[bisect(P,M-i) - 1] for i in P[:s])
### BUGGY CODE ###

n = int(input())
i = 1
while i <= n:
 if i % 3 == 0:
  print(' {0}'.format(i))
  continue
 elif i % 10 == 3:
  print(' {0}'.format(i))
  continue

### FIXED CODE ###

n = int(input())
i = 1
for i in range(1, n + 1):
 if i % 3 == 0:
  print(' {0}'.format(i), end = '')
 else:
  st = str(i)
  for x in range(0, len(st)):
   if st[x] == '3':
    print(' {0}'.format(i), end = '')
    break
print()
### BUGGY CODE ###

inf = float("INF")
a,b,q = map(int, input().split())
s = [-inf, -inf]+[int(input()) for _ in range(a)]+[inf]
t = [-inf, -inf]+[int(input()) for _ in range(b)]+[inf]

from bisect import bisect_left

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


for _ in range(q):
  ans = inf
  x = int(input())
  sr = bisect_left(s, x)
  ans = min(ans, f(s,t,x,sr))
  ans = min(ans, f(s,t,x,sr - 1))
  tr = bisect_left(t, x)
  ans = min(ans, f(t,s,x,tr))
  ans = min(ans, f(t,s,x,tr - 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)