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

#!/usr/bin/env python

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7

def gcd(x, y): 
    if x == 0: return y
    else: return gcd(y%x, x)

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

l = a[0]
for i in range(n):
    l = lcm(l, a[i])

ans = 0 
for i in range(n):
    ans += (l//a[i])%mod

print(ans%mod)


### FIXED CODE ###

#!/usr/bin/env python
import math
n = int(input()) 
a = list(map(int, input().split()))

mod = 10**9+7

def lcm(a, b): 
    return a*b//math.gcd(a, b)

l = a[0]
for i in range(n):
    l = lcm(l, a[i])
l %= mod 

ans = 0 
for i in range(n):
    inv = pow(a[i], mod-2, mod)
    ans += (l*inv)%mod

print(ans%mod)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
sortedA = sorted(A)
B = [0 for i in range(n)]
for i in range(n):
    B[i] = A.index(sortedA[i])+1
print(*B)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
B = [0 for _ in range(n)]
for i, v in enumerate(A):
    B[v-1] = i+1
print(*B)
### BUGGY CODE ###

N=int(input())
p=list(map(int,input().split()))
count=0
import collections

s=collections.deque()
for i in range(N):
  if p[i]==i+1:
    s.append(i)
ans=0
while(s):
  x=s.popleft()
  if x+1 in s:
    s.popleft()
  ans+=1
  
print(ans)


### FIXED CODE ###

N=int(input())
p=list(map(int,input().split()))
count=0
t=set()
for i in range(N):
  if p[i]==i+1:
    t.add(i)
ans=0
id=0
while(id<N):
  if id in t:
    if id+1 in t:
      id+=1
    ans+=1
  id+=1
  
  
print(ans)
### BUGGY CODE ###

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

dic = {}
for num in A:
    if num in dic:
        dic[num] += 1
    else:
        dic[num] = 1

for _ in range(Q):
    total = 0
    B, C = map(int, input().split())
    if B in dic and C in dic:
        dic[C] += dic[B]
        del dic[B]
    elif B in dic and C not in dic:
        dic[C] = dic[B]
        del dic[B]
    for mykey, myvalue in dic.items():
        total += mykey * myvalue
    print(total)


### FIXED CODE ###

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

dic = {}
for num in A:
    if num in dic:
        dic[num] += 1
    else:
        dic[num] = 1

prev_sum = 0

for key, value in dic.items():
    prev_sum += key * value

for _ in range(Q):
    B, C = map(int, input().split())
    if B in dic and C in dic:
        dic[C] += dic[B]
        dif = (C - B) * dic[B]
        prev_sum += dif
        del dic[B]
    elif B in dic and C not in dic:
        dic[C] = dic[B]
        dif = (C - B) * dic[B]
        prev_sum += dif
        del dic[B]
    print(prev_sum)
### BUGGY CODE ###

int(input())
u = input()
l = []
res = 0


def remove_ad(li):
    li2 = ""
    q = ""
    r = ""
    s = ""
    for p in str(li):
        if (p != q):
            li2 = li2 + p
        else:
            if (p != r):
                li2 = li2 + p
            else:
                if (p != s): li2 = li2 + p
        s = r
        r = q
        q = p
    return(li2)



t = remove_ad(u)
n = len(t)
l = set([])

for i in range(0,n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if(t[i]+t[j]+t[k] not in l):
                l.add(t[i]+t[j]+t[k])
                res += 1

print(res)

### FIXED CODE ###

from itertools import product

N = int(input())
S = input()
S = [int(s) for s in S]


res = 0
for q in product(range(10), repeat=3):
    i = 0
    for s in S:
        if s==q[i]:
            if i==2:
                res += 1
                break
            else:
                i+=1
print (res)
### BUGGY CODE ###

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

ans = 1
for item in a:
  ans = ans * item
  if ans > 1000000000000000000:
    ans = -1

print(ans)

### FIXED CODE ###

def main():
  N = int(input())
  A = list(map(int, input().split()))
  
  if 0 in A:
    print(0)
    return
  
  prod = 1
  for a in A:
    prod *= a
    if prod > 1000000000000000000:
      print(-1)
      return
  print(prod)
  
main()
### BUGGY CODE ###

from collections import deque

N,M = map(int,input().split())
P = list(map(int,input().split()))
L = [list(map(int,input().split())) for i in range(M)]

G = [[] for i in range(N)]

for i in range(len(L)) :
    u,v = L[i]
    u -= 1
    v -= 1
    
    G[u].append(v)
    G[v].append(u)

explored = [0 for i in range(N)]

ans = 0

for i in range(N) :
    
    if explored[i] :
        continue
    
    explored[i] = 1
    q = deque([i])
    
    A = []
    B = []
    while q :
        now = q.popleft()
        
        A.append(now)
        B.append(P[now]-1)
        
        for to in G[now] :
            if explored[to] :
                continue
            
            q.append(to)
            explored[to] = 1
    
    for a in A :
        if a in B :
            ans += 1

print(ans)


### FIXED CODE ###

from collections import deque

N,M = map(int,input().split())
P = list(map(int,input().split()))
L = [list(map(int,input().split())) for i in range(M)]

G = [[] for i in range(N)]

for i in range(len(L)) :
    u,v = L[i]
    u -= 1
    v -= 1
    
    G[u].append(v)
    G[v].append(u)

explored = [0 for i in range(N)]

ans = 0

for i in range(N) :
    
    if explored[i] :
        continue
    
    explored[i] = 1
    q = deque([i])
    
    A = []
    B = []
    while q :
        now = q.popleft()
        
        A.append(now)
        B.append(P[now]-1)
        
        for to in G[now] :
            if explored[to] :
                continue
            
            q.append(to)
            explored[to] = 1
    
    C = set(A) & set(B)
    ans += len(C)
    

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

import numpy as np
import bisect

A, B, Q = map(int,input().split())
s = [0 for _ in range(A+2)]
t = [0 for _ in range(B+2)]
s[0] = -np.inf
s[-1] = np.inf
t[0] = -np.inf
t[-1] = np.inf
for i in range(A):
    s[i+1] = int(input())
for i in range(B):
    t[i+1] = int(input())

def solve(s,t,x):
    ans = np.inf
    for i in range(2):
        a, b = (s, t) if i==0 else (t, s)
        posX1 = bisect.bisect_left(a,x)
        for j in range(2):
            ax = a[posX1 -j]
            posX2 = bisect.bisect_left(b,ax)
            for k in range(2):
                bx = b[posX2-k]
                ans = min(ans, abs(x-ax)+abs(bx-ax))
    return ans

for _ in range(Q):
    x = int(input())
    print(solve(s,t,x))

### FIXED CODE ###

import bisect
import sys

A, B, Q = map(int,input().split())
s = [-(10**18)] + list(map(int, (sys.stdin.readline() for _ in [0]*A))) + [10**18]
t = [-(10**18)] + list(map(int, (sys.stdin.readline() for _ in [0]*B))) + [10**18]


def solve(s,t,x):
    ans = 10**18
    for i in range(2):
        a, b = (s, t) if i==0 else (t, s)
        posX1 = bisect.bisect_left(a,x)
        for j in range(2):
            ax = a[posX1 -j]
            posX2 = bisect.bisect_left(b,ax)
            for k in range(2):
                bx = b[posX2-k]
                ans = min(ans, abs(x-ax)+abs(bx-ax))
    return ans

for _ in range(Q):
    x = int(input())
    print(solve(s,t,x))
### BUGGY CODE ###

import numpy as np


def atcoder_input():
    H, W = (int(i) for i in input().split())
    _ = []

    for i in range(H):
        l = [j for j in input().split()]
        _.append(l)
    _ = np.array(_)

    A = np.zeros((H, W)).astype("int")

    for h in range(H):
        for w in range(W):
            if _[h][0][w] == ".":
                A[h][w] = 0
            else:
                A[h][w] = 1

    return A, H, W


def main():
    A, H, W = atcoder_input()

    old_x_where = list(np.where(A == 1)[0]) 
    old_y_where = list(np.where(A==1)[1])

    counter = 0

    while np.min(A) == 0:
        counter += 1
        new_x_where = []
        new_y_where = []
        for i in range(4):
            if i == 0:
                tmp_x = list(np.clip(np.array(old_x_where) + 1, 0, W - 1))
                tmp_y = list(np.clip(np.array(old_y_where), 0, H - 1))
            elif i == 1:
                tmp_x = list(np.clip(np.array(old_x_where), 0, W - 1))
                tmp_y = list(np.clip(np.array(old_y_where)+1, 0, H - 1))
            elif i == 2:
                tmp_x = list(np.clip(np.array(old_x_where)-1, 0, W - 1))
                tmp_y = list(np.clip(np.array(old_y_where), 0, H - 1))
            else:  # i=3
                tmp_x = list(np.clip(np.array(old_x_where), 0, W - 1))
                tmp_y = list(np.clip(np.array(old_y_where)-1, 0, H - 1))

            new_x_where.extend(tmp_x)
            new_y_where.extend(tmp_y)

        A[new_y_where, new_x_where] = 1
        old_x_where = new_x_where
        old_y_where = new_y_where

    print(counter)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque

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

# input black cells
black_cells = []

for h in range(H):
    line = list(input())
    for w in range(W):
        if line[w] == "#":
            black_cells.append(h * W + w)


# Graph
def r(p):
    q_list = []
    h = p // W
    w = p % W
    if h != 0:
        q_list.append(p - W)
    if h != H-1:
        q_list.append(p + W)
    if w != 0:
        q_list.append(p - 1)
    if w != W-1:
        q_list.append(p + 1)
    return q_list


queue = deque(black_cells)
d = [10000] * (H * W)
for i in black_cells:
    d[i] = 0

# dijkstra
while len(queue) > 0:
    p = queue.popleft()
    for q in r(p):
        if d[q] > d[p] + 1:
            d[q] = d[p] + 1
            queue.append(q)

print(max(d))
### BUGGY CODE ###

from bisect import bisect_left
from functools import lru_cache

n = int(input())
lll = list(map(int, input().split()))
lll.sort()
ans = 0


@lru_cache()
def bisect_left_cache(x):
    return bisect_left(lll, x)


for i in range(n - 2):
    li = lll[i]
    for j in range(i + 1, n - 1):
        k = bisect_left_cache(li + lll[j])
        ans += k - j - 1
print(ans)


### FIXED CODE ###

from bisect import bisect_left

n = int(input())
lll = list(map(int, input().split()))
lll.sort()
ans = 0

for i in range(n - 2):
    li = lll[i]
    for j in range(i + 1, n - 1):
        k = bisect_left(lll, li + lll[j], lo=j)
        ans += k - j - 1
print(ans)
### BUGGY CODE ###

from itertools import combinations

def is_prime(n):
    if n < 2:
        return False
    elif n == 2:
        return True
    else:
        for p in range(2, n):
            if n % p == 0:
                return False
        else:
            return True


# input
N = int(input())

prime_nums = []
append = prime_nums.append
for n in range(2, 55555):
    if is_prime(n) is False:
        continue

    if len(prime_nums) == N:
        break

    if len(prime_nums) >= 5 and not [1 for c in combinations(prime_nums + [n], 5) if is_prime(sum(c))]:
        append(n)

    if len(prime_nums) < 5:
        append(n)

res = " ".join([str(num) for num in prime_nums])

print(res)

### FIXED CODE ###

def is_prime(n):
    if n < 2:
        return False
    else:
        for p in range(2, n):
            if n % p == 0:
                return False
        else:
            return True


# input
N = int(input())

# check
prime_nums = []
append = prime_nums.append
for n in range(2, 55555):
    if is_prime(n) and n % 5 == 1:
        append(n)
        if len(prime_nums) == N:
            break

res = " ".join([str(num) for num in prime_nums])
print(res)
exit(0)
### BUGGY CODE ###

n = int(input())

def calcLucas(n):
    if n == 0:
        return 2
    if n == 1:
        return 1
    return calcLucas(n-1) + calcLucas(n-2)

print(calcLucas(n))

### FIXED CODE ###

n = int(input())

l = [0] * 87
l[0] = 2
l[1] = 1
for i in range(2, n + 1):
    l[i] = l[i-1] + l[i-2]
print(l[n])
### BUGGY CODE ###

import  collections 
N = int(input())
list_a = []
 
for i in range (0,N):
    a = input()
    list_a.append(a)
dict_a = collections.Counter(list_a)
 
 
list_ans = []
 
list_ans.append(dict_a.most_common()[0][0])
a = dict_a.most_common()[0][1]
for i in range (1,len(dict_a)):
    if a == dict_a.most_common()[i][1]:
        list_ans.append(dict_a.most_common()[i][0])
 
list_ans.sort()
for i in range (0,len(list_ans)):
    print(list_ans[i])

### FIXED CODE ###

N = int(input())
S = [input() for i in range(N)]
dictionary = {}
for word in S:
    if word in dictionary:
        dictionary[word] += 1
    else:
        dictionary[word] = 1

maximum = max(dictionary.values())
for key, value in sorted(dictionary.items()):
    if value == maximum:
        print(key)
### BUGGY CODE ###

import heapq
from collections import defaultdict
N, Q = map(int, input().split())
events = []

for i in range(N):
    s, t, x = map(int, input().split())
    events.append([s - x, 'add', x])
    events.append([t - x, 'delete', x])

events.sort()
events.append([float('inf'), 'guard', None])

i = 0
closing = defaultdict(int)
hq = []  # 最小値を高速に入手するため
for q in range(Q):
    d = int(input())
    while d >= events[i][0]:
        time, event, x = events[i]
        if event == 'add':
            closing[x] += 1
            heapq.heappush(hq, x)

        elif event == 'delete':
            closing[x] -= 1

        i += 1

    while hq and (closing[hq[0]] == 0):
        heapq.heappop(hq)

    if hq:
        print(hq[0])
    else:
        print(-1)


### FIXED CODE ###

def main():

    import sys
    import heapq

    N, Q = map(int, sys.stdin.readline().split())
    events = []

    for i in range(N):
        s, t, x = map(int, sys.stdin.readline().split())
        events.append((s - x, 1, x))  # 通行止め追加
        events.append((t - x, -1, x))  # 通行止め削除

    for i in range(Q):
        d = int(input())
        events.append((d, 2, 0))

    events.sort()
    events.append([float('inf'), 'guard', None])

    i = 0
    closing = set()
    hq = []  # 最小値を高速に入手するため
    while d >= events[i][0]:
        time, event, x = events[i]
        if event == 1:
            closing.add(x)
            heapq.heappush(hq, x)

        elif event == -1:
            closing.remove(x)

        else:
            while hq and (hq[0] not in closing):
                heapq.heappop(hq)

            if hq:
                print(hq[0])
            else:
                print(-1)

        i += 1


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

from itertools import combinations
n = int(input())
l = list(map(int, input().split()))

ll = list(combinations(l,3))
cnt = 0
for i in ll:
	a,b,c=i[0],i[1],i[2]
	if a < b+c and b < c+a and c < a+b:
		cnt += 1
print (cnt)

### FIXED CODE ###

import bisect
n = int(input())
l = map(int, input().split())
l = sorted(l)

cnt = 0
for i in range (n-2):
	for j in range (i+1, n-1):
		ab = l[i] + l[j]
		r = bisect.bisect_left(l, ab)
		cnt += r - j - 1

print (cnt)
### BUGGY CODE ###

import collections
n = int(input())
a = map(int, input().split())
li = []
for i in a:
    li.append(i)
king_li=[]
for k in range(n):
    cp_li = li.copy()
    del cp_li[k]
    k_li=[]
    for val in collections.Counter(cp_li).values():
        in_li=[]
        in_li.append(int(val*(val-1)*0.5))
        k_li.append(sum(in_li))
    king_li.append(sum(k_li))
for k in king_li:
  print(k)

### FIXED CODE ###

import collections
n = int(input())
a = map(int, input().split())
li = []
for i in a:
    li.append(i)
collections.Counter(li)
m = 0
dic = collections.Counter(li)
for i in dic.values():
    m += int(i*(i-1)*0.5)
for k in range(n):
      print(m-dic[li[k]]+1)
### BUGGY CODE ###

n = int(input())
A_l = [(A,i) for i, A in enumerate(map(int,input().split()))]
A_l.sort()
A_l.reverse()

dp = []
for _ in range(n+1):
    dp.append([0] * (n+1))
for j in range(1,n+1): # all go bigger
    yb = n - (j-1)
    a, i = A_l[j-1]
    dp[j][0] = dp[j-1][0] + a*(yb-(i+1))
for k in range(1,n+1): # all go smaller
    ys = 1 + (k-1)
    a, i = A_l[k-1]
    dp[0][k] = dp[0][k-1] + a*((i+1)-ys)

for j in range(1,n+1):
    for k in range(1,n-j+1):
        yb = n - (j-1)
        ys = 1 + (k-1)
        a, i = A_l[j+k-1]
        j_plus = a*(yb-(i+1))
        k_plus = a*((i+1)-ys)
        dp[j][k] = max(dp[j-1][k]+j_plus, dp[j][k-1]+k_plus)

result = 0
for j in range(0,n+1):
    k = n-j
    result = max(result, dp[j][k])
print(result)
#for l in range(n+1):
#    print(dp[l])

### FIXED CODE ###

n = int(input())
A_l = [(A,i) for i, A in enumerate(map(int,input().split()))]
A_l.sort(reverse=True)

dp = []
for _ in range(n+1):
    dp.append([0] * (n+1))
for j in range(1,n+1): # all go bigger
    a, i = A_l[j-1]
    dp[j][0] = dp[j-1][0] + a*(n-(j-1) - (i+1))
for k in range(1,n+1): # all go smaller
    a, i = A_l[k-1]
    dp[0][k] = dp[0][k-1] + a*((i+1) - (1+(k-1)))

for j in range(1,n+1):
    for k in range(1,n-j+1):
        a, i = A_l[j+k-1]
        j_plus = a*(n-(j-1) - (i+1))
        k_plus = a*((i+1) - (1+(k-1)))
        dp[j][k] = max(dp[j-1][k]+j_plus, dp[j][k-1]+k_plus)

result = 0
for j in range(0,n+1):
    k = n-j
    result = max(result, dp[j][k])
print(result)
#for l in range(n+1):
#    print(dp[l])
### BUGGY CODE ###

r, g, b, n = map(int, input().split())

m1 = max(r, g, b)
m3 = min(r, g, b)
m2 = r+g+b-(m1+m3)

l1 = [m1*i for i in range(0, n//m1+1)]
cnt = 0

i = 0
while i*m1 <= n:
    j = 0
    while i*m1 + j*m2 <= n:
        if (n - (i*m1 + j*m2))%m3 == 0:
            cnt += 1
        j += 1
    i += 1
    
print(cnt)

### FIXED CODE ###

r, g, b, n = map(int, input().split())

m1 = max(r, g, b)
m3 = min(r, g, b)
m2 = r+g+b-(m1+m3)

l1 = [m1*i for i in range(0, n//m1+1)]
cnt = 0

i = 0
while i*m1 <= n:
    j = 0
    while i*m1 + j*m2 <= n:
        if (n - (i*m1 + j*m2))%m3 == 0:
            cnt += 1
        j += 1
    i += 1
    
print(cnt)
### BUGGY CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
#n = 2*10**8
n = 20001002
prime = [] # i番目の素数
is_prime = [True] * (n+1)
p = 0 # 何番目か　0-indexed
is_prime[0] = False
is_prime[1] = False
ll = 0
#print('a')
for i in range(2,n+1):
    #ll += 1
    #print(i)
    if is_prime[i] == True:
        prime.append(i) # p番目の素数はiとなる
        p += 1
        # print(ll)
        # if p == 1000*ll:
        #     print(p)
        for j in range(2*i, n+1,i):
            is_prime[j] = False # その素数の倍数のやつ

#print(sieve(n,11000000))
#print(prime)
import math
def is_prime(n):
    for i in range(2,int(math.sqrt(n)+1)):
        if n % i == 0:
            return False
    return n != 1 # 1の場合は除外

n = int(input())
if is_prime(n):
    print(1)
    exit()
cnt = 0
for v in prime:
    nya = v
    while n % v == 0:
        cnt += 1
        n //= v
        v *= nya
print(cnt)


### FIXED CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from fractions import gcd
#from itertools import combinations # (string,3) 3回
#from collections import deque
from collections import defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
def soinsu(n):
    dic = defaultdict(int)
    i = 2
    while i*i <= n:
        if n%i == 0:
            dic[i] += 1
            n //= i
        else:
            i += 1
    if n!= 1:
        dic[n] += 1
    return dic
n = I()
dic = soinsu(n)
#print(dic)
cnt = 0
for k,v in dic.items():
    num = 1
    while v - num >= 0:
        cnt += 1
        v -= num
        num += 1
print(cnt)
### BUGGY CODE ###

import numpy as np
N , M = map(int, input().split())
a = list()
for n in range(M):
    a.append(int(input()))
dp = np.zeros(N+1)
dp[0] = 1
if M == 0:
    dp[1] = 1
else:
    dp[1] = 0 if a[0] == 1 else 1
for n in range(2,N+1):
    if n in a:
        dp[n] = 0
    else:
        dp[n] = (dp[n-1]+dp[n-2])%(10**9+7)
print(int(dp[N]))


### FIXED CODE ###

import numpy as np
N , M = map(int, input().split())
a = list()
for n in range(M):
    a.append(int(input()))
dp = np.zeros(N+1)
dp[0] = 1
if M == 0:
    dp[1] = 1
else:
    dp[1] = 0 if a[0] == 1 else 1
ok = [False]*(N+1)
for x in a:
    ok[x] = True
for n in range(2,N+1):
    if ok[n]:
        continue
    dp[n] = (dp[n-1]+dp[n-2])%(10**9+7)
print(int(dp[N]))
### BUGGY CODE ###

N = int(input())
a = [input() for i in range(N)]
a.sort()
b = [0] * N
flag = 1
cc = 0
for i in range(N):
    c = a.count(a[cc])
    b[cc] = c
    if flag == 1:
        max = c
        flag = 0
    if c > max:
        max = c
    cc = cc + c
    if cc >= N:
        break
for i in range(N):
    if b[i] == max:
        print(a[i])




### FIXED CODE ###

N = int(input())
a = [input() for i in range(N)]
a.sort()
b = [0] * N
flag = 1
cc = 0
bef = 132
c = 1
for i in range(N):
    if a[i] == bef:
        c = c + 1
    else:
        c = 1
    bef = a[i]
    b[i] = c
    if flag == 1:
        max = c
        flag = 0
    if c > max:
        max = c
        
for i in range(N):
    if b[i] == max:
        print(a[i])
### BUGGY CODE ###

import math
import numpy as np

S = list(input())
N = len(S)+1
if N%2==0:
    D = np.zeros(N)
else:
    D = np.zeros(N-1)
   
nc = 1
cur = S[0]
curi = 0
for i in range(1,N-1):
    if S[i]==cur:
        nc += 1
    else:
        D[curi] = nc
        cur = S[i]
        curi += 1
        nc = 1
D[curi] = nc
D=D.reshape([-1,2])
Asum = 0
for d in D:
    if d.all == 0:
        break
    else:
        a1 = max(np.absolute(d))
        a2 = min(np.absolute(d))
        Asum += int((a1+1)*a1/2 + a2*(a2-1)/2)

print(Asum)

### FIXED CODE ###

import math
import numpy as np

# N,K = map(int,input().split())
# A = np.sort(list(map(int,input().split())))
# F = np.sort(list(map(int,input().split())))[::-1]
#         if np.sum(AF[AF>0]) > K: 

S = list(input())
if S[0]=='>':
    S = ['<']+S
if S[-1]=='<':
    S = S+['>']

N=len(S)
D=np.zeros(N)
nc = 1
cur = S[0]
curi = 0
for i in range(1,N):
    if S[i]==cur:
        nc += 1
    else:
        D[curi] = nc
        cur = S[i]
        curi += 1
        nc = 1
D[curi] = nc
D = D[D>0]
D=D.reshape([-1,2])
Asum = 0
for d in D:
    a1 = max(d)
    a2 = min(d)
    Asum += int((a1+1)*a1/2 + a2*(a2-1)/2)

print(Asum)
### BUGGY CODE ###

A,B,Q=map(int,input().split())
s=[int(input()) for _ in range(A)]
t=[int(input()) for _ in range(B)]

#二分探索関数
def bin_search(x,seq):
	width=[0,len(seq)-1]
	if len(seq)<=1:
		return [0,0]
	if x<=seq[0]:
		return [0,0]
	elif x>=seq[width[1]]:
		return [width[1],width[1]]
	else:
		while(width[1]-width[0]>1):
			center=(sum(width)//2)
			if x>=seq[center]:
				width=[center,width[1]]
			else:
				width=[width[0],center]
	if x==seq[width[0]]:
		return [width[0],width[0]]
	elif x==seq[width[1]]:
		return [width[1],width[1]]
	else:
		return width

for i in range(Q):
	x=int(input())
	Nb_s=bin_search(x,s)
	Nb_t=bin_search(x,t)
	Nb_s0=s[Nb_s[0]]
	Nb_s1=s[Nb_s[1]]
	Nb_t0=t[Nb_t[0]]
	Nb_t1=t[Nb_t[1]]

	k1=abs(Nb_s0-x)+abs(Nb_t0-Nb_s0)
	k2=abs(Nb_s1-x)+abs(Nb_t0-Nb_s1)
	k3=abs(Nb_s0-x)+abs(Nb_t1-Nb_s0)
	k4=abs(Nb_s1-x)+abs(Nb_t1-Nb_s1)
	k5=abs(Nb_t0-x)+abs(Nb_t0-Nb_s0)
	k6=abs(Nb_t1-x)+abs(Nb_t1-Nb_s1)
	k7=abs(Nb_t0-x)+abs(Nb_t0-Nb_s1)
	k8=abs(Nb_t1-x)+abs(Nb_t1-Nb_s0)
	print(min(k1,k2,k3,k4,k5,k6,k7,k8))

### FIXED CODE ###

inf=10**11
A,B,Q=map(int,input().split())
s=[-inf]+[int(input()) for _ in range(A)]+[inf]
t=[-inf]+[int(input()) for _ in range(B)]+[inf]
x=[[i,int(input())] for i in range(Q)]

x.sort(key=lambda x:x[1])
i,s_i,t_i=0,0,0
ans=[]

for i in range(Q):
    while(1):
        if x[i][1]>=s[s_i]:
            s_i+=1
        else:
            break
    while(1):
        if x[i][1]>=t[t_i]:
            t_i+=1
        else:
            break
    ans.append([x[i][0],x[i][1],s[s_i-1],s[s_i],t[t_i-1],t[t_i]])
ans.sort(key=lambda x:x[0])
for i in range(Q):
    xx=ans[i][1]
    Nb_s0=ans[i][2]
    Nb_s1=ans[i][3]
    Nb_t0=ans[i][4]
    Nb_t1=ans[i][5]

    p1=abs(Nb_s0-xx)
    p2=abs(Nb_s1-xx)
    p3=abs(Nb_t0-xx)
    p4=abs(Nb_t1-xx)
    q1=abs(Nb_t0-Nb_s0)
    q2=abs(Nb_t0-Nb_s1)
    q3=abs(Nb_t1-Nb_s0)
    q4=abs(Nb_t1-Nb_s1)
    print(min(p1+q1,p2+q2,p1+q3,p2+q4,p3+q1,p4+q4,p3+q2,p4+q3))