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

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


def main():
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    for i in range(q):
        n, x, m = map(int, input().split())
        last = x
        eq = 0
        for j in range(k):
            num = math.ceil((n-1-j)/k)
            last += (d[j] % m)*num
            if d[j] % m == 0:
                eq += num
        ans = (n-1) - (last//m - x//m) - eq
        print(ans)


main()


### FIXED CODE ###

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


def ceil(a, b):
    return (a+b-1)//b


def main():
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    for i in range(q):
        n, x, m = map(int, input().split())
        last = x
        eq = 0
        for j in range(k):
            num = ceil((n-1-j), k)
            last += (d[j] % m)*num
            if d[j] % m == 0:
                eq += num
        ans = (n-1) - (last//m - x//m) - eq
        print(ans)


main()
### BUGGY CODE ###

import math
n,m,k = map(int,input().split())
ss = (math.factorial(m*n)//math.factorial(k))//math.factorial(m*n-k)
s = (ss*k*(k-1))//2
r = 10**9 +7
xav = ((m**3-m) *n**2)//6
yav = ((n**3-n)*m**2)//6
av = xav + yav
d = (m*n*(m*n-1))//2
print(int(((av*s)//d)%r))



### FIXED CODE ###

n,m,k = map(int,input().split())
x = m*n
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
ss = cmb(x,k)
s = (ss*k*(k-1))//2
r = 10**9 +7
av = (((m**3-m) *n**2)//6 + ((n**3-n)*m**2)//6)%r
d = (x*(x-1))//2
print(int(((av*s)//d)%r))
### BUGGY CODE ###

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

ans=A[0]
for i in range(1,N):
    ans = ans * A[i] 
if(ans > (10 ** 18)):
    print('-1')
else:
    print(ans)

### FIXED CODE ###

import sys  # sys.exit()を使いたいので

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

A.sort()
ans=1
for i in A:
    ans *= i
    if ans > (10 ** 18):
        print('-1')
        sys.exit()
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

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

import math
def eraP(n):
    if n<=1: return [False]*(n+1)
    elif n<=2: return [False, False, True]
    L = [False if i%2==0 or i%3==0 else True for i in range(n)]
    L[0] = False; L[1] = False;
    L[2] = True; L[3] = True; L[5]=True
    limit = math.sqrt(n)
    for i in range(3,n,2):
        if i >= limit: return L
        for s in range(i**2,n,i):
            L[s] = False
    return L

q = int(input())
rmax = 0
L = [0]*q
R = [0]*q
for i in range(q):
    l, r = map(int, input().split())
    L[i], R[i] = l, r
    rmax = max(r,rmax)
P = eraP(rmax+1)

for i in range(q):
    tmp = 0
    for j in range(L[i],R[i]+1):
        if P[j] and P[(j+1)//2]:
            tmp += 1
    print(tmp)

### FIXED CODE ###

import math
def eraP(n):
    if n<=1: return [False]*(n+1)
    elif n<=2: return [False, False, True]
    L = [False if i%2==0 or i%3==0 else True for i in range(n)]
    L[0] = False; L[1] = False;
    L[2] = True; L[3] = True; L[5]=True
    limit = math.sqrt(n)
    for i in range(3,n,2):
        if i >= limit: return L
        for s in range(i**2,n,i):
            L[s] = False
    return L

q = int(input())
LR = [[0,0] for _ in range(q)]
for i in range(q):
    LR[i] = list(map(int, input().split()))
P = eraP(pow(10,5)+1)[1:]

sumP = [0,0,0]
for i in range(2,pow(10,5)):
    sumP.append(sumP[-1]+int(P[i] and P[(i+1)//2]))

for lr in LR:
    print(sumP[lr[1]]-sumP[lr[0]-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
dp = [[0] * N for _ in range(N)]

for l in range(N):
    for i in range(N-l):
        if l == 0:
            dp[i][i] = a[i]
        else:
            j = i + l
            dp[i][j] = max(a[i] - dp[i+1][j], a[j] - dp[i][j-1])
print(dp[0][N-1])

### FIXED CODE ###

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

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

INF = 10**18
dp = [[INF] * N for _ in range(N)]

# def calc(i, j, t):
#     if dp[i][j] != INF:
#         return dp[i][j]
#     if t == 0:
#         if i == j:
#             dp[i][j] = a[i]
#         else:
#             dp[i][j] = max(calc(i+1, j, 1) + a[i], calc(i, j-1, 1) + a[j])
#     else:
#         if i == j:
#             dp[i][j] = -a[i]
#         else:
#             dp[i][j] = min(calc(i+1, j, 0) - a[i], calc(i, j-1, 0) - a[j])
#     return dp[i][j]

# print(calc(0, N-1, 0))

for l in range(N):
    t = (N-l) % 2
    for i in range(N-l):
        j = i + l
        if t == 1:
            if l == 0:
                dp[i][j] = a[i]
            else:
                dp[i][j] = max(dp[i+1][j] + a[i], dp[i][j-1] + a[j])
        else:
            if l == 0:
                dp[i][j] = -a[i]
            else:
                dp[i][j] = min(dp[i+1][j] - a[i], dp[i][j-1] - a[j])
print(dp[0][N-1])
### BUGGY CODE ###

N, L = map(int, input().split())

S = [0] * N

for i in range(N):
    S[i] = input()

from itertools import permutations, combinations,combinations_with_replacement,product

strings = [''.join(s) for s in list(permutations(S))]

strings.sort()
print(strings[0])

### FIXED CODE ###

N, L = map(int, input().split())
S = [input() for _ in range(N)]
S.sort()
ans = ''.join(S)
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [0]*n
c = [0]*n
for i in range(n):
    for j in range(a[i]+1):
        if j == 0:
            b[i] += 1
        else:
            if j <= i:
                b[i-j] +=1
            if j <= n-1-i:
                b[i+j] +=1
for l in range(min(k-1, 50)):
    for i in range(n):
        if b[i]-a[i] > 0:
            for j in range(a[i]+1, b[i]+1):
                if j <= i:
                    c[i-j] += 1
                if j <= n-1-i:
                    c[i+j] += 1
        elif b[i]-a[i] < 0:
            for j in range(b[i]+1, a[i]+1):
                if j <= i:
                    c[i-j] -= 1
                if j <= n-1-i:
                    c[i+j] -= 1
    for i in range(n):
        a[i] = b[i]
        b[i] += c[i]
        c[i] = 0
print(*b)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(min(k, 50)):
    b = [0]*(n+1)
    for i in range(n):
        b[max(0, i-a[i])] += 1
        b[min(i+a[i]+1, n)] -= 1
    for i in range(1, n+1):
        b[i] += b[i-1]
    for i in range(n):
        a[i] = b[i]
print(*a)
### BUGGY CODE ###

import math
N=int(input())

n=math.floor(math.sqrt(N))

for n in range(1,N+1):
    ans=0
    flag=False
    for x in range(1,n ):
        for y in range(1, n):
            for z in range(1, n):
                a=x**2+y**2+z**2+x*y+y*z+z*x
                if a==n:
                    ans+=1
                if a>n:
                    break
            if x**2+y**2+1+x*y+y+x>n:
                break
  
                    
    print(ans)

### FIXED CODE ###

n=int(input())
ans=[0 for _ in range(10001)]

for x in range(1,101):
  for y in range(1,101):
    for z in range(1,101):
      v=x*x+y*y+z*z+x*y+y*z+z*x
      if v<10001:
        ans[v]+=1

for i in range(n):
  print(ans[i+1])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

MOD = 1000000007  # type: int

def solve(S: str):
    N = len(S)
    dp = np.zeros((N, 13))
    if S[N-1] != '?':
        dp[0, int(S[N-1])] = 1
    else:
        dp[0] = np.array([1,1,1,1,1,1,1,1,1,1,0,0,0])
    for i in range(1, len(S)):
        ii = N - i - 1
        for j in range(13):
            if S[ii] == '?':
                for ll in range(10):
                    kk = (ll * 10 ** i) % 13
                    dp[i, j] += dp[i-1, (13 + j - kk) % 13]
                    dp[i, j] %= MOD
            else:
                x = int(S[ii])
                m = x * 10 ** i % 13
                dp[i, j] = dp[i-1, (13+j-m)%13]
                dp[i, j] %= MOD
    print(int(dp[N-1, 5]))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(S: str):
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(len(S))]
    if S[N-1] != '?':
        dp[0][int(S[N-1])] = 1
    else:
        dp[0] = [1,1,1,1,1,1,1,1,1,1,0,0,0]
    ten = [1]
    for i in range(1, len(S)):
        ten.append(ten[-1] * 10 % 13)
        ii = len(S) - i - 1
        for j in range(13):
            if S[ii] == '?':
                for ll in range(10):
                    kk = ll * ten[i] % 13
                    dp[i][j] += dp[i-1][(13 + j - kk)%13]
                    dp[i][j] %= MOD
            else:
                x = int(S[ii])
                m = x * ten[i] % 13
                dp[i][j] = dp[i-1][(13+j-m)%13]
                dp[i][j] %= MOD
    print(dp[len(S)-1][5])
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

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

import math

def insertionSort(A,n,g,cnt):
	for i in range(g,n):
		v = A[i]
		j = i - g
		while j >= 0 and A[j] > v:
			A[j+g] = A[j]
			j = j - g
			cnt += 1
		A[j+g] = v
	return A,cnt

def shellSort(A,n):
	BASE = 4
	cnt = 0
	#m = n//2 + 1
	#G = [2*i + 1*(i==0) for i in range(m)[::-1]]
	m = int(math.log(n,BASE)) + 1
	G = [BASE**i for i in range(m)[::-1]]
	for g in G:
		A,cnt = insertionSort(A,n,g,cnt)
	return A,m,G,cnt

if __name__ == '__main__':
	
	n = int(input())
	A = []
	[A.append(int(input())) for i in range(n)]
	
	'''
	data = [int(d) for d in data.split('\n')]
	n = data.pop(0)
	A = data[:]
	'''
	
	A,m,G,cnt = shellSort(A,n)
	print(m)
	print(' '.join([str(i) for i in G]))
	print(cnt)
	[print(a) for a in A]

### FIXED CODE ###

def insertionSort(A,n,g,cnt):
	for i in range(g,n):
		v = A[i]
		j = i - g
		while j >= 0 and A[j] > v:
			A[j+g] = A[j]
			j = j - g
			cnt += 1
		A[j+g] = v
	return A,cnt

def shellSort(A,n):
	cnt = 0
	G = [1]
	while G[-1]*3+1 <= n:
		G.append(G[-1]*3 + 1)
	G = G[::-1]
	m = len(G)
	for g in G:
		A,cnt = insertionSort(A,n,g,cnt)
	return A,m,G,cnt

if __name__ == '__main__':
	
	n = int(input())
	A = []
	[A.append(int(input())) for i in range(n)]
	
	'''
	data = [int(d) for d in data.split('\n')]
	n = data.pop(0)
	A = data[:]
	'''
	
	A,m,G,cnt = shellSort(A,n)
	print(m)
	print(' '.join([str(i) for i in G]))
	print(cnt)
	[print(a) for a in A]
### BUGGY CODE ###

#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
# ---- ここまで -----------------------
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)

### FIXED CODE ###

import bisect
s = input().rstrip()
t = input().rstrip()

a_ord = ord("a")
ch_place = [[] for _ in range(26)]
for i, ch in enumerate(s):
    ch_place[ord(ch) - a_ord].append(i)

# print(ch_place)

count = 0
idx = -1 
for ch in t:
    ch_num = ord(ch) - a_ord
    if len(ch_place[ch_num]) == 0:
        print(-1)
        exit()
    place = bisect.bisect_right(ch_place[ch_num], idx)
    # print(ch_place[ch_num], idx, place)
    if place == len(ch_place[ch_num]):
        idx = ch_place[ch_num][0]
        count += 1
    else:
        idx = ch_place[ch_num][place]

# print(count, idx)
print(count * len(s) + idx + 1)
### BUGGY CODE ###

from collections import defaultdict
r,c,k = map(int,input().split())
K = defaultdict(int)
for _ in range(k):
    x,y,z= [int(i) for i in input().split()]
    K[(x,y)] = z


dp = [[0]*(c+1) for _ in range(4)]
 
for i in range(1, r+1):
    for j in range(1, c+1):
        v = K[(i, j)]
        dp[0][j] = max(dp[0][j-1], dp[0][j], dp[1][j], dp[2][j], dp[3][j])
        dp[1][j] = max(dp[1][j-1], dp[0][j]+v) if v>0 else dp[1][j-1]
        dp[2][j] = max(dp[2][j-1], dp[1][j-1]+v) if v>0 else dp[2][j-1]
        dp[3][j] = max(dp[3][j-1], dp[2][j-1]+v) if v>0 else dp[3][j-1]
        
print(max(dp[i][-1] for i in range(4)))

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
H, W, K = map(int, input().split())
B = {}
for _ in range(K):
    r, c, v = map(int, input().split())
    B[(r, c)] = v

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

for i in range(1, H+1):
    for j in range(1, W+1):
        if (i, j) in B:
            v = B[(i, j)]
            dp[0][j] = max(dp[0][j-1], dp[0][j], dp[1][j], dp[2][j], dp[3][j])
            dp[1][j] = max(dp[1][j-1], dp[0][j]+v)
            dp[2][j] = max(dp[2][j-1], dp[1][j-1]+v)
            dp[3][j] = max(dp[3][j-1], dp[2][j-1]+v)
        else:
            dp[0][j] = max(dp[0][j-1], dp[0][j], dp[1][j], dp[2][j], dp[3][j])
            dp[1][j] = dp[1][j-1]
            dp[2][j] = dp[2][j-1]
            dp[3][j] = dp[3][j-1]

print(max(dp[i][-1] for i in range(4)))
### BUGGY CODE ###

def solve():
    from sys import stdin
    f_i = stdin
    
    N = int(f_i.readline())
    
    adj = [[] for i in range(N)]
    for i in range(N - 1):
        A, B = map(int, f_i.readline().split())
        A -= 1
        B -= 1
        adj[A].append(B)
        adj[B].append(A)
    
    mod = 10 ** 9 + 7
    pow2 = [(2 ** i) % mod for i in range(N + 1)]
    
    from sys import setrecursionlimit
    setrecursionlimit(10 ** 6)
    
    ans = 0
    def dfs(node, parent):
        nonlocal ans
        cnt = 1
        for child in adj[node]:
            if child != parent:
                cnt += dfs(child, node)
        
        ans += (pow2[cnt] - 1) * (pow2[N-cnt] - 1)
        ans % mod
        return cnt
    
    dfs(0, None)
    
    ans = (ans - N * pow2[N-1] + pow2[N] - 1) % mod
    ans = ans * pow(pow2[N], mod - 2, mod) % mod
    
    print(ans)

solve()

### FIXED CODE ###

from sys import stdin
f_i = stdin

N = int(f_i.readline())

adj = [[] for i in range(N)]
for i in range(N - 1):
    A, B = map(int, f_i.readline().split())
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)

mod = 10 ** 9 + 7

pow2 = [1] * (N + 1)
for i, j in zip(range(N), range(1, N + 1)):
    pow2[j] = pow2[i] * 2 % mod

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

ans = 0

def dfs(node, parent):
    global ans
    cnt = 1
    
    for child in adj[node]:
        if child != parent:
            cnt += dfs(child, node)
    
    ans += (pow2[cnt] - 1) * (pow2[N-cnt] - 1)
    ans %= mod
    
    return cnt

dfs(0, None)

ans = (ans - N * pow2[N-1] + pow2[N] - 1) % mod
ans = ans * pow(pow2[N], mod - 2, mod) % mod

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

import numpy as np
N, K, Q = list(map(int, input().split()))

vec = np.ones(N)*K

A = []
for _ in range(Q):
    A = int(input())
    vec -= 1
    vec[A-1] += 1

ret = '\n'.join(['Yes' if x > 0 else 'No' for x in vec])
print(ret)

### FIXED CODE ###

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

# vec = [K for _ in range(N)]

vec = [0 for _ in range(N)]

for _ in range(Q):
    A = int(input())
#     for i in range(N):
#         vec[i] -= 1
    vec[A-1] += 1

ret = '\n'.join(['Yes' if K-Q+x > 0 else 'No' for x in vec])
print(ret)
### BUGGY CODE ###

import math

def pri_num(n):
    for i in range(2,math.floor(n**0.5)+1):
        if n%i == 0:
            return 0
    return 1

def like_2017(n1):
    f2 = pri_num((n1+1)//2)
    if f2 == 0:
        return 0
    f1 = pri_num(n1)
    return f1*f2

Q = int(input())
memo = [-1]*(10**5+1)
for _ in range(Q):
    l,r= map(int,input().split())
    cnt = 0
    for i in range(l,r+1,2):
        if i%3 == 0 and i!=3:
            continue
        if i == 1:
            continue
        else:
            if memo[i] == -1:
                memo[i]= like_2017(i)
            cnt += memo[i]
    print(cnt)
    


### FIXED CODE ###

memo =[1]*(10**5+1)
memo[0]=0
memo[1]=0
for i in range(2,len(memo)):
    if memo[i]==0:
        continue
    else:
        for j in range(i*2,len(memo),i):
            memo[j]=0
memo_like2017 = [0]*(10**5+1)
for i in range(3,len(memo),2):
    if memo[i]==1 and memo[(i+1)//2] ==1:
        memo_like2017[i]=1
sum_memo=[0]*(10**5+1)
for i in range(1,len(memo)):
    sum_memo[i] = sum_memo[i-1]+memo_like2017[i]

Q = int(input())
for _ in range(Q):
    l,r = map(int,input().split())
    print(sum_memo[r]-sum_memo[l-1])
### BUGGY CODE ###

import collections

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

cnt = 0

for i in range(N):
    if len(A) > K:
        min_k = min(A, key=A.get)
        cnt += A[min_k]
        A.pop(min_k)
    else:
        break

print(cnt)


### FIXED CODE ###

import collections

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = dict(collections.Counter(A))
A = sorted(A.items(), key=lambda x: x[1], reverse=True)

cnt = 0

for i in range(N):
    if len(A) > K:
        cnt += A[-1][1]
        A.pop()
    else:
        break

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


n = int(input())
for i in range(1,n+1):
    cnt=0

    for x in range(1,n+1):
        for y in range(1,n-x+1):
            for z in range(1,n-x-y+1):
                eq = x**2 + y**2 + z**2 + x*y + y*z + z*x
                if eq == i:
                    cnt+=1
    print(cnt)

### FIXED CODE ###

#! python3
# coding:utf-8
 
def main():
    n = int(input())
    ans = [0 for _ in range(n)]
    for x in range(1,100):
        for y in range(1,100):
            for z in range(1,100):
                eq = x**2 + y**2 + z**2 + x*y + y*z + z*x
                if eq < n+1:
                    ans[eq-1]+=1
    for i in ans:   
        print(i)

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

import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]
n = int(input())
a = list(map(int,input().split()))
ans = np.array(a)
k = 2
for i in range(n, 0, -1):
    if n/k < i:
        for x in range(2, k):
            ans[i-1] += ans[x * i - 1]
        ans[i-1] = ans[i-1] % 2
    else:
        while n/k >= i:
            k += 1
        else:
            for x in range(2, k):
                ans[i-1] += ans[x * i - 1]
            ans[i-1] = ans[i-1] % 2
print(np.sum(ans))
for p in np.ndarray.flatten(np.argwhere(ans) + 1):
    print(p, end=' ')

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = []
k = 2
for i in range(n, 0, -1):
    if n/k < i:
        for x in range(2, k):
            a[i-1] += a[x * i - 1]
        a[i-1] = a[i-1] % 2
    else:
        while n/k >= i:
            k += 1
        else:
            for x in range(2, k):
                a[i-1] += a[x * i - 1]
            a[i-1] = a[i-1] % 2
    if a[i-1] == 1:
        ans.append(i)
print(len(ans))
print(*ans)
### BUGGY CODE ###

import numpy as np

def get_nearest(point, lst):
    """
    概要: リストからある値に最も近い値を返却する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(lst) - point).argmin()
    return lst[idx]

#def get_nearest(point, lst):
#    shortest = 1000000000000000
#    nearest = float("inf")
#    for x in lst:
#        dist = abs(x - point)
#        if dist < shortest:
#            shortest = dist
#            nearest = x
#    return nearest

#def exist_between(a, b, lst):
#    for x in lst:
#        if a <= x and x <= b:
#            return True
#    else:
#        return False

A, B, Q = [int(x) for x in input().split(" ")]
a = []
b = []
for i in range(A):
    a.append(int(input()))
for i in range(B):
    b.append(int(input()))
for i in range(Q):
    q = int(input())
    nearest_a = get_nearest(q, a)
    nearest_b = get_nearest(q, b)
#   print(q, nearest_a, nearest_b)
    
    if abs(nearest_a - q) < abs(nearest_b - q):
        nearer, farer = nearest_a, nearest_b
        nearer_list, farer_list = a, b
    else:
        nearer, farer = nearest_b, nearest_a
        nearer_list, farer_list = b, a

    nearer_first  = abs(q - nearer)
    nearer_first += abs(nearer - get_nearest(nearer, farer_list))

    farer_first  = abs(q - farer)
    farer_first += abs(farer - get_nearest(farer, nearer_list))

    answer = min(nearer_first, farer_first)

    print(answer)

### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = INF
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)