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

import sys
input = sys.stdin.readline
def main():
    h,W = map(int,input().split())
    c = [tuple(input()) for _ in range(h)]
    c = tuple(c)
    ans = 0
    w = [[0 for _ in range(h+1)] for _ in range(h+1)]
    dp = [[0 for _ in range(h+1)] for _ in range(h+1)]
    for j in range(W-1):
        for x in range(h+1):
            w[0][x] = 0
            for z in range(h-x):
                if c[x+z][j] == c[z][j+1]:
                    w[0][x] += 1
        for x in range(1,h+1):
            w[x][0] = 0
            for z in range(h-x):
                if c[z][j] == c[x+z][j+1]:
                    w[x][0] += 1
        for x in range(1,h+1):
            for y in range(1,h+1):
                w[x][y] = w[x-1][y-1]
                if c[h-x][j] == c[h-y][j+1]:
                    w[x][y] -= 1
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 and y == 0:
                    dp[x][y] = 0
                    continue
                if x == 0:
                    dp[x][y] = dp[x][y-1]+w[x][y-1]
                elif y == 0:
                    dp[x][y] = dp[x-1][y]+w[x-1][y]
                else:
                    dp[x][y] = min(dp[x][y-1]+w[x][y-1],dp[x-1][y]+w[x-1][y])
        ans += dp[h][h]
    print(ans)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    h,W = map(int,input().split())
    c = [tuple(input()) for _ in range(h)]
    c = tuple(c)
    ans = 0
    w = [0 for _ in range((h+1)**2)]
    dp = [0 for _ in range((h+1)**2)]
    for j in range(W-1):
        for x in range(h,0,-1):
            for y in range(h,0,-1):
                w[(x-1)*(h+1)+y-1] = w[x*(h+1)+y]
                if c[h-x][j] == c[h-y][j+1]:
                    w[(x-1)*(h+1)+y-1] += 1
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 or y == 0:
                    if x == y:
                        dp[x*h+y] = 0
                    elif x == 0:
                        dp[x*(h+1)+y] = dp[x*(h+1)+y-1]+w[x*(h+1)+y-1]
                    else:
                        dp[x*(h+1)+y] = dp[(x-1)*(h+1)+y]+w[(x-1)*(h+1)+y]
                    continue
                dp[x*(h+1)+y] = min(dp[x*(h+1)+y-1]+w[x*(h+1)+y-1],dp[(x-1)*(h+1)+y]+w[(x-1)*(h+1)+y])
        ans += dp[-1]
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n = int(input().strip())
s=[sorted(input().strip()) for i in range(n)]

c=0
for i in range(n):
    for j in range(i+1,n):
        for k in range(10):
            if s[i][k]!=s[j][k]:
                break
            if k==9:
                c+=1
print(c)

### FIXED CODE ###

n = int(input().strip())

count_by_kw = {}
for i in range(n):
    s=''.join(sorted(input().strip()))
    if s in count_by_kw.keys():
        count_by_kw[s]+=1
    else:
        count_by_kw[s]=1

c=list(count_by_kw.values())
ans=0
for val in c:
    ans+=val*(val-1)//2

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

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

sumli = [0]
sum = 0
acum = 0

for i in ali:
    sum = sum + i
    sumli.append(sum)

while len(sumli)!=0:
    s=sumli[0]
    ss=sumli.count(s)
    acum = acum+(ss*(ss-1))//2
    sumli= [x for x in sumli if x != s]

print(acum)


### FIXED CODE ###

from collections import Counter

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

sumli = [0]
sum = 0
acum = 0

for i in ali:
    sum = sum + i
    sumli.append(sum)

sumc = Counter(sumli)

for j in list(sumc):
    acum = acum+(sumc[j]*(sumc[j]-1))//2

print(acum)
### BUGGY CODE ###

def solve(N):
    if N <= 20:
        for i in range(N):
            print(i, flush=True)
            s = input()
            if s == 'Vacant':
                return

    print(0, flush=True)
    low_sex = input()
    if low_sex == 'Vacant':
        return
    print(N - 1, flush=True)
    high_sex = input()
    if high_sex == 'Vacant':
        return
    high, low = N - 1, 0
    while high - low > 1:
        mid = (high + low) // 2
        print(mid, flush=True)
        mid_sex = input()
        if mid_sex == 'Vacant':
            return

        if (mid - low + 1) % 2 == 1 and low_sex == mid_sex:
            high = mid
            high_sex = mid_sex
        elif (mid - low + 1) % 2 == 0 and low_sex != mid_sex:
            high = mid
            high_sex = mid_sex
        elif (high - mid + 1) % 2 == 0 and high_sex != mid_sex:
            low = mid
            low_sex = mid_sex
        else:
            low = mid
            low_sex = mid_sex


if __name__ == '__main__':
    solve(int(input()))

### FIXED CODE ###

def get_sex(i):
    print(i, flush=True)
    return input()


def solve(N):
    if N <= 19:
        for i in range(N):
            print(i, flush=True)
            s = input()
            if s == 'Vacant':
                exit()

    low_sex = get_sex(0)
    if low_sex == 'Vacant':
        exit()
    high_sex = get_sex(N - 1)
    if high_sex == 'Vacant':
        exit()

    high, low = N - 1, 0
    while high > low:
        mid = (high + low) // 2
        mid_sex = get_sex(mid)
        if mid_sex == 'Vacant':
            exit()

        if (mid - low) % 2 == 1:
            if mid_sex != low_sex:
                low = mid
                low_sex = mid_sex
            else:
                high = mid
                high_sex = mid_sex
        else:
            if mid_sex != low_sex:
                high = mid
                high_sex = mid_sex
            else:
                low = mid
                low_sex = mid_sex


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

a,b,c,k = map(int,input().split())
result = 0

while k > 0:
    if a > 0:
        result+=1
        a-=1
        k-=1
        continue
    elif b > 0:
        b-=1
        k-=1
        continue
    else:
        result-=1
        c-=1
        k-=1
        continue

print(result)

### FIXED CODE ###

a,b,c,k = map(int,input().split())
if a >= k:
    print(k)
elif a < k and b >= k-a:
    print(a)
else:
    print(a-(k-a-b))
### BUGGY CODE ###

import math
n = int(input())
s = input()
count = 0
ans = 1 
for i, x in enumerate(s):
    if (i%2 == 0 and x == "B") or (i%2 == 1 and x == "W"): # B:1(R), W:0(L)
        count += 1
    else:
        ans *= count
        count -= 1
ans *= math.factorial(n)
if count != 0:
    print(0)
else:
    print(ans%(10**9+7))


### FIXED CODE ###

n = int(input())
s = input()
count = 0
ans = 1 
for i, x in enumerate(s):
    if (i%2 == 0 and x == "B") or (i%2 == 1 and x == "W"): # B:1(R), W:0(L)
        count += 1
    else:
        ans *= count
        count -= 1
        ans %= (10**9+7)
if count != 0:
    print(0)
else:
    for i in range(1, n+1):
        ans *= i
        ans %= (10**9+7)
    print(ans)
### BUGGY CODE ###

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

ans = 1
for a in A:
    ans = ans * a

if ans > pow(10, 18):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

if 0 in A:
    print(0)
    exit()
ans = 1
for a in A:
    ans = ans * a
    if ans > pow(10, 18):
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque
from sys import setrecursionlimit

setrecursionlimit(10 ** 8)


def dfs(now):
    seen[now] = True
    for next in branch[now]:
        if seen[next] is False:
            tree[now].append(next)
            dfs(next)
    return tree


N, Q = map(int, input().split())
branch = [set() for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    branch[a - 1].add(b - 1)
    branch[b - 1].add(a - 1)
operation = [list(map(int, input().split())) for _ in range(Q)]

seen = [False] * N
tree = [[] for _ in range(N)]
for i in range(N):
    if seen[i] is False:
        dfs(i)
lst = []
for i in range(N):
    res = []
    tmp_lst = deque([i])
    while tmp_lst:
        now = tmp_lst.pop()
        res.append(now)
        for next in tree[now]:
            tmp_lst.append(next)
    lst.append(res)

score = [0 for _ in range(N)]
for q in operation:
    root, pnt = q
    root -= 1
    for i in lst[root]:
        score[i] += pnt

for ans in score:
    print(ans, end=' ')


### FIXED CODE ###

#!/usr/bin/env python3
from sys import setrecursionlimit

setrecursionlimit(10 ** 8)


def dfs(now):
    seen[now] = True
    score[now] += operation[now]
    for next in branch[now]:
        if seen[next] is False:
            score[next] += score[now]
            dfs(next)


N, Q = map(int, input().split())
branch = [set() for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    branch[a - 1].add(b - 1)
    branch[b - 1].add(a - 1)
operation = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    operation[p - 1] += x

seen = [False] * N
score = [0] * N
for i in range(N):
    if seen[i] is False:
        dfs(i)

for ans in score:
    print(ans, end=' ')
### BUGGY CODE ###

#!/usr/local/bin/python3
# coding: utf-8
n = input()
hairu = input()
kita = hairu.split(" ")
seki = 1

try:
    for c in kita:
        seki = seki * int(c)
    if seki > 10**18:
        print("-1")
    else:
        print(seki)
except:
    print("-1")

### FIXED CODE ###

#!/usr/local/bin/python3
# coding: utf-8
n = input()
hairu = input()
kita = hairu.split(" ")
seki = 1

for c in kita:
    if c == "0":
        kita[0] = "0"

for c in kita:
    seki = seki * int(c)
    if seki > 10**18:
        break

if seki > 10**18:
    print("-1")
else:
    print(seki)
### BUGGY CODE ###

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

a = []
for i in range(q):
    a.append(int(input()))

point = [k] * n

for i in range(q):
    win = a[i - 1]
    point = list(map(lambda x: x - 1, point))
    point[win - 1] += 1

for i in range(n):
    if point[i] <= 0:
        print('No')
    else:
        print('Yes')


### FIXED CODE ###

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

a = []
for i in range(q):
    a.append(int(input()))

point = [k] * n

for i in range(q):
    win = a[i - 1]
    point[win - 1] += 1

point = list(map(lambda x: x - q, point))

for i in range(n):
    if point[i] <= 0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

N = int(input())

A_list = list(map(int, input().split()))

ans = [A_list.index(i+1)+1 for i in range(N)]

for i in range(N):
    print(ans[i], end=" ")

### FIXED CODE ###

import heapq
N = int(input())

A_list = list(map(int, input().split()))

list = [(A_list[i],i+1) for i in range(N)]
heapq.heapify(list)

for i in range(N):
    print(heapq.heappop(list)[1], end=" ")
### BUGGY CODE ###

n = int(input())
s = str(input())
c1 = [False for _ in range(10)]
c2 = [0 for _ in range(1000)]
for i in range(n-2):
  si = int(s[i])
  if c1[si] != True:
    c1[si] = True
    for j in range(i+1,n-1):
      for k in range(j+1,n):
        c2[si+int(s[j])*10+int(s[k])*100] = 1
print(sum(c2))
    
    

### FIXED CODE ###

n = int(input())
s = str(input())
c1 = [False for _ in range(10)]
c2 = [0 for _ in range(1000)]
count = 0
for i in range(n-2):
  si = int(s[i])
  if c1[si] != True:
    c1[si] = True
    c3 = [False for _ in range(10)]
    for j in range(i+1,n-1):
      sj = int(s[j])
      if c3[sj] != True:
        c3[sj] = True
        c4 = [False for _ in range(10)]
        for k in range(j+1,n):
          sk = int(s[k])
          if c4[sk] != True:
            c4[sk] = True
            count += 1
print(count)
### BUGGY CODE ###


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

s_max = 0
for j in range(N - K + 1):
    s = sum(p[j:j+K])

    if s_max < s:
        s_max = s

print((s_max+K)/2)

### FIXED CODE ###


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


s = sum(p[0:K])
s_max = s

for i in range(N-K):
    s = s -p[i] + p[i+K]

    if s_max < s:
        s_max = s

print((s_max+K)/2)
### BUGGY CODE ###

import math
from fractions import gcd

a, b = map(int, input().split())
cd = set()
ans = 0

g = gcd(a, b)

if g == 1:
    cd.add(1)
else:
    for i in range(1, g+1):
        if a % i == 0 and b % i == 0:
            cd.add(i)

for s in cd:
    if s == 1:
        ans += 1
    else:
        for t in range(2, int(math.sqrt(s)) + 1):
            if s % t == 0:
                break
        else:
            ans += 1

print(ans)


### FIXED CODE ###

import math
from fractions import gcd

a, b = map(int, input().split())
cd = set()
ans = set()

'''
g = gcd(a, b)

for i in range(1, g+1):
    if a % i == 0 and b % i == 0:
        cd.add(i)
        '''

i =  1
a_set = set()

for i in range(1, int(math.sqrt(a)) + 1):
    if a % i == 0:
        a_set.add(i)
        a_set.add(a // i)
    i += 1

i = 1
b_set = set()

for i in range(1, int(math.sqrt(b)) + 1):
    if b % i == 0:
        b_set.add(i)
        b_set.add(b // i)
    i += 1

cd = set(a_set) & set(b_set)

for s in sorted(list(cd)):
    if s == 1:
        ans.add(s)
    else:
        for t in sorted(list(ans)):
            if t == 1:
                continue
            elif s % t == 0:
                break
        else:
            ans.add(s)

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

A,B,N= list(map(int, input().split()))
ma=0
for i in range(1,min(N,B)+1):
    a=int(A*i/B)-A*int(i/B)
    if(ma<a):
        ma=a
    if(a>=A):
      break
print(ma)

### FIXED CODE ###

A,B,N= list(map(int, input().split()))
print(int(A*min(B-1,N)/B)-A*int(min(B-1,N)/B))
### BUGGY CODE ###

N,K = input().split(" ")
N = int(N)
K = int(K)
p = input().split(" ")
expected_list = []
max_list = []
for i in range(N):
  sum = 0
  for j in range(int(p[i])+1):
    sum += j
  expected_list.append(float(sum/(int(p[i]))))
  
for i in range(N):
  anan = 0
  for j in range(K):
    try:
      anan += expected_list[i+j]
    except:
      pass
  max_list.append(anan)

print(max(max_list))

### FIXED CODE ###

N,K = input().split(" ")
N = int(N)
K = int(K)
p = input().split(" ")
expected_list = []
max_list = []
for i in range(N):
  expected_list.append((int(p[i])+1)/2)
anan = 0
for j in range(K):
  anan += expected_list[j]
max_list.append(anan)
for i in range(N):
  if i == 0:
    continue
  anan = 0
  try:
    anan = max_list[i-1]-expected_list[i-1]+expected_list[i+K-1]
  except:
    pass
  max_list.append(anan)
  
print(max(max_list))
### BUGGY CODE ###

from bisect import bisect_right
import numpy as np

n = int(input())

top = map(int, input().split())
mid = map(int, input().split())
bot = map(int, input().split())
top = np.array(sorted(top))
mid = np.array(sorted(mid))
bot = np.array(sorted(bot))

ans = 0
for i in top:
    for j in mid[bisect_right(mid,i):]:
        ans += len(bot[bisect_right(bot,j):])

print(ans)

### FIXED CODE ###

from bisect import bisect_right, bisect_left
import numpy as np

n = int(input())

top = map(int, input().split())
mid = map(int, input().split())
bot = map(int, input().split())
top = np.array(sorted(top))
mid = np.array(sorted(mid))
bot = np.array(sorted(bot))

ans = 0
for i in mid:
    top_num = len(top[:bisect_left(top,i)])
    bot_num = len(bot[bisect_right(bot,i):])
    ans += top_num * bot_num

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

import itertools

X, Y, Z, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()] 
B = [int(i) for i in input().split()] 
C = [int(i) for i in input().split()] 

T = [A, B, C]
cand_list = itertools.product(*T)
score = []
for cand in cand_list:
  score.append(sum(cand))

score = sorted(score)[::-1]
for i in range(K):
	print(score[i])

### FIXED CODE ###

import itertools

X, Y, Z, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()] 
B = [int(i) for i in input().split()] 
C = [int(i) for i in input().split()] 

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

D = [a+b for a,b in itertools.product(A[:K], B[:K])]
D.sort(reverse=True)

E = [c+d for c,d in itertools.product(C[:K], D[:K])]
E.sort(reverse=True)

for i in range(K):
    print(E[i])
### BUGGY CODE ###

import itertools

n = int(input())
num_list = input().split()

mod_base = 10 ** 9 + 7

def calc_list(i, num_list):
    sum = 0
    for num in num_list[i+1:]:
        sum += int(num_list[i]) * int(num)
    return sum

sum_num = 0

for i, num_str in enumerate(num_list):
    if i+1 > len(num_list):
        break
    sum_num += calc_list(i, num_list)
    
print(sum_num % mod_base)

### FIXED CODE ###

import itertools

n = int(input())
num_list = input().split()

mod_base = 10 ** 9 + 7

num_list = [int(x) for x in num_list]

sum_list = []
sum_tmp = sum(num_list)
for i in range(len(num_list)):
    sum_list.append(sum_tmp)
    sum_tmp -= num_list[i]

all_sum = 0
for index, num in enumerate(num_list):
    if index + 1 >= len(num_list):
        break
    all_sum += num * sum_list[index+1]

print(all_sum % mod_base)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n, u = na()
d = []
for i in range(u):
    d.append(na())

c = []
for i in range(n):
    c.append(na())

for i in range(n):
    for j in range(n):
        c[i][j] -= 1

fs = []
for i in range(u):
    f = [0]*3
    for j in range(n):
        t = j%3
        for k in range(n):
            f[t] += d[c[j][k]][i]
            t += 1
            if t == 3:
                t = 0
    fs.append(f)

ans = 99999999999999999
for i in range(u):
    for j in range(u):
        for k in range(u):
            if i == j or j == k or k == i: continue

            ans = min(ans, fs[i][0] + fs[j][1] + fs[k][2])
print(ans)


### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n, u = na()
d = []
for i in range(u):
    d.append(na())

c = []
for i in range(n):
    c.append(na())

for i in range(n):
    for j in range(n):
        c[i][j] -= 1

fs = []
for i in range(u):
    f = [0]*3
    for j in range(n):
        t = j%3
        for k in range(n):
            f[t] += d[c[j][k]][i]
            t += 1
            if t == 3:
                t = 0
    fs.append(f)

ans = 99999999999999999
for i in range(u):
    for j in range(u):
        for k in range(u):
            if i == j or j == k or k == i: continue

            ans = min(ans, fs[i][0] + fs[j][1] + fs[k][2])
print(ans)
### BUGGY CODE ###

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

max = 0
for i in range(N-1):
    count = 0
    for j in range(i, N-1):
        if H[j] >= H[j+1]:
            count += 1
        else:
            break
    if count > max:
        max = count

print(max)

### FIXED CODE ###

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

updown = ['-' if H[i+1] <= H[i] else '+' for i in range(N-1)]
count = 0
max = 0
for i in updown:
    if i == '-':
        count += 1
    else:
        if count > max:
            max = count
        count = 0
if count > max:
    max = count
print(max)
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline
INF = 10**9


n = int(input())
edges = [0] * (n-1)
for i in range(n-1):
    edges[i] = tuple(map(int, input().split()))
    

adjacency_list = [[] for i in range(n+1)]
for edge in edges:
    adjacency_list[edge[0]].append(edge[1])
    adjacency_list[edge[1]].append(edge[0])


max_order = max(len(i) for i in adjacency_list)
root = 0
for i in range(0, n+1):
    if len(adjacency_list[i]) == max_order:
        root = i
             

node_history = set()
edge_dict = dict()
node_deque = deque()


node_deque.append(root)
while len(node_deque):
    current_node = node_deque.popleft()
    undef_edges = []
    kinds = {i for i in range(1, max_order + 1)}
    
    for a in adjacency_list[current_node]:
        if a not in node_history:
            node_history.add(a)
            node_deque.append(a)
            
        if current_node < a:
            temp_edge = (current_node, a)
        else:
            temp_edge = (a, current_node)    
        
        if temp_edge in edge_dict.keys():
            kinds.remove(edge_dict[temp_edge])
        else:
            undef_edges.append(temp_edge)
            
    for undef_edge in undef_edges:
        kind = min(kinds)
        edge_dict[undef_edge] = kind
        kinds.remove(kind)


print(max_order)
for e in edges:
    print(edge_dict[e])

### FIXED CODE ###

from collections import deque

def main():
	N, *AB = map(int, open(0).read().split())
	B = AB[1::2]

	E = [[] for _ in range(N + 1)]
	for a, b in zip(*[iter(AB)] * 2):
		E[a].append(b)

	Q = deque([1])
	C = [0] * (N + 1)
	while Q:
		v = Q.popleft()
		c = 0
		for u in E[v]:
			c += 1 + (c + 1 == C[v])
			C[u] = c
			Q.append(u)

	print(max(C))
	for b in B:
		print(C[b])

main()
### BUGGY CODE ###

import copy

n=int(input())
org=[i for i in range(1,10**5)]
org_set=set(org)
edges=[]
colors=[]
for i in range(n-1):
    a,b=map(int,input().split(" "))
    edges.append([a,b])
    colors.append([])
colors.append([])
colors.append([])

ans=[]
for i in edges:
    color_sum=set(colors[i[0]]+colors[i[1]])
    tmp_org=org_set.copy()
    for j in color_sum:
        tmp_org.remove(j)
    org_ls=list(tmp_org)
    colors[i[0]].append(org_ls[0])
    colors[i[1]].append(org_ls[0])
    ans.append(org_ls[0])

print(max(ans))
for i in ans:
    print(i)


### FIXED CODE ###

import copy

n=int(input())
org_set=set([i for i in range(1,10**5)])
edges=[]
relations={}
nodes=[]
for i in range(n-1):
    a,b=map(int,input().split(" "))
    edges.append([a,b])
    relations.setdefault(a,[]).append(b)
    nodes.append([])
nodes.append([])
nodes.append([])

max_color=0
for start in range(1,n+1):
    targets=relations.get(start,[])
    color=1
    for target in targets:
        if color in nodes[start]:
            color+=1
        else:
            pass
        nodes[target].append(color)
        if color>=max_color:
            max_color=color
        color+=1

print(max_color)
for edge in edges:
    print(nodes[edge[1]][0])
### BUGGY CODE ###

n = int(input())
s = input()
count = 0
for i in range(1,n-1):
    for j in range((i+1),n):
        if not s[i-1] == s[j-1]:
            for k in range((j+1),n+1):
                if not j-i == k-j:
                    if not s[i-1] == s[k-1] and not s[j-1] == s[k-1]:
                        count +=1
print(count)

### FIXED CODE ###

n = int(input())
s = input()
all = s.count("R")*s.count("G")*s.count("B")
for x in range(n-1):
    for y in range(1,(n-1-x)//2+1):
        if s[x] != s[x+y] and s[x]!= s[x+2*y]\
        and s[x+y]!=s[x+2*y]:
            all -=1
print(all)
### BUGGY CODE ###

A, B, Q = map(int, input().split())
s, t, x = [], [], []
for i in range(A):
    s.append(int(input()))
for i in range(B):
    t.append(int(input()))
for i in range(Q):
    x.append(int(input()))


def find(target, loc):
    if len(target) > 2:
        if loc < target[len(target)//2]:
            return find(target[:len(target)//2+1], loc)
        else:
            return find(target[len(target)//2:], loc)
    elif len(target) == 2:
        if loc <= sum(target)/2:
            return target[0]
        else:
            return target[1]
    else:
        return target[0]


for x_i in x:
    # s -> t
    move_s = 0
    cur = find(s, x_i)
    move_s += abs(cur-x_i)
    end = find(t, cur)
    move_s += abs(end-cur)

    # t -> s
    move_t = 0
    cur = find(t, x_i)
    move_t += abs(cur-x_i)
    end = find(s, cur)
    move_t += abs(end-cur)

    print(min(move_s, move_t))


### FIXED CODE ###

from bisect import bisect_left

A, B, Q = map(int, input().split())
s, t, x = [], [], []
for i in range(A):
    s.append(int(input()))
for i in range(B):
    t.append(int(input()))
for i in range(Q):
    x.append(int(input()))


for x_i in x:
    s_r_index = bisect_left(s, x_i)
    if s_r_index >= len(s):
        s_r = 1e18
    else:
        s_r = s[s_r_index]

    if s_r_index > 0:
        s_l = s[s_r_index-1]
    else:
        s_l = -1e18

    t_r_index = bisect_left(t, x_i)
    if t_r_index >= len(t):
        t_r = 1e18
    else:
        t_r = t[t_r_index]

    if t_r_index > 0:
        t_l = t[t_r_index-1]
    else:
        t_l = -1e18

    move_length = [abs(x_i-s_l)+abs(s_l-t_l),
                   abs(x_i-s_l)+abs(s_l-t_r),
                   abs(x_i-s_r)+abs(s_r-t_l),
                   abs(x_i-s_r)+abs(s_r-t_r),
                   abs(x_i-t_l)+abs(t_l-s_l),
                   abs(x_i-t_l)+abs(t_l-s_r),
                   abs(x_i-t_r)+abs(t_r-s_l),
                   abs(x_i-t_r)+abs(t_r-s_r)]
    print(min(move_length))