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

import sys
sys.setrecursionlimit(4100000)

def main():
    H, W = map(int, input().split())
    S = list(input() for _ in range(H))
    visited = [[float('inf')] * W for _ in range(H)]
    dh = [0,1]
    dw = [1,0]
    if S[0][0] == '#':
        visited[0][0] = 1
        pre = False
    else:
        visited[0][0] = 0
        pre = True
    
    def dfs(h,w,visited,pre):
        if h == H - 1 and w == W - 1:
            return

        for i in range(2):
            nh = h + dh[i]
            nw = w + dw[i]

            if 0 <= nh < H and 0 <= nw < W:
                if S[nh][nw] == '.':
                    visited[nh][nw] = min(visited[nh][nw], visited[h][w])
                    dfs(nh,nw,visited,True)
                else:
                    if pre:
                        visited[nh][nw] = min(visited[nh][nw], visited[h][w] + 1)
                        dfs(nh,nw,visited,False)
                    else:
                        visited[nh][nw] = min(visited[nh][nw], visited[h][w])
                        dfs(nh,nw,visited,False)

    dfs(0,0,visited,pre)
    print(visited[H-1][W-1])

        



if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)
from collections import deque

def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    visited = [[float('inf')] * W for _ in range(H)]
    if S[0][0] == '#':
        visited[0][0] = 1
    else:
        visited[0][0] = 0
    
    for h in range(H):
        for w in range(W):
            if h + 1 > H - 1 and w + 1 > W - 1:
                continue
            if S[h][w] == '.':
                if h + 1 > H - 1:
                    if S[h][w + 1] == '.':
                        visited[h][w+1] = min(visited[h][w], visited[h][w+1])
                    else:
                        visited[h][w+1] = min(visited[h][w] + 1,visited[h][w+1])
                elif w + 1 > W - 1:
                    if S[h+1][w] == '.':
                        visited[h+1][w] = min(visited[h][w],visited[h+1][w])
                    else:
                        visited[h+1][w] = min(visited[h][w] + 1,visited[h+1][w])
                else:
                    if S[h + 1][w] == '.':
                        visited[h+1][w] = min(visited[h][w],visited[h+1][w])
                    else:
                        visited[h+1][w] = min(visited[h][w] + 1,visited[h+1][w])

                    if S[h][w + 1] == '.':
                        visited[h][w+1] = min(visited[h][w],visited[h][w+1])
                    else:
                        visited[h][w+1] = min(visited[h][w] + 1,visited[h][w+1])

            else:
                if h + 1 > H - 1:
                    visited[h][w+1] = min(visited[h][w],visited[h][w+1])
                elif w + 1 > W - 1:
                    visited[h+1][w] = min(visited[h][w],visited[h+1][w])
                else:
                    visited[h][w+1] = min(visited[h][w],visited[h][w+1])
                    visited[h+1][w] = min(visited[h][w],visited[h+1][w])

    print(visited[H-1][W-1])


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

import numpy as np

N, M= (int(i) for i in input().split())
A = [int(i) for i in input().split()]

B = [0] * M
C = [0] * M

for i in range(M):
    B[i], C[i] = map(int, input().split())
np_A = np.array(A)

for i in range(M):
  if np.min(np_A) <= C[i]:
    for j in range(B[i]):
      A_min_index_np = np.argmin(np_A)
      np_A[A_min_index_np] = C[i]

print(np.sum(np_A))


### FIXED CODE ###

N, M= (int(i) for i in input().split())
A = [int(i) for i in input().split()]
BC = [list(map(int, input().split())) for _ in range(M)]
count = 0

BC = sorted(BC, key=lambda x: x[1],reverse=True)
min_A = min(A)

for B,C in BC:
  if min_A >= C and count > N:
    break
  else:
    l = min(B, N-count)
    for i in range(l):
      count+=1
      A.append(C)

A.sort()

ans = sum(A[count:len(A)])

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

x,y,z,k=map(int,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)
if k<x: a=a[:k]
if k<y: b=b[:k]
if k<z: c=c[:k]
d=[]
ans=[]
for i in a:
    for j in b:
        d.append(i+j)
d.sort(reverse=True)
if k<len(d): d=d[:k]
for i in c:
    for j in d:
        ans.append(i+j)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])


### FIXED CODE ###

x,y,z,k=map(int,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)
if k>x: a=a[:k]
if k>y: b=b[:k]
if k>z: c=c[:k]
d=[]
ans=[]
for i in a:
    for j in b:
        d.append(i+j)
d.sort(reverse=True)
if len(d)>k: d=d[:k]
for i in c:
    for j in d:
        ans.append(i+j)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
cnt = 0
import math
for i in A[:len(A)]:
	for j in A[A.index(i)+1:]:
		if i == j:
			cnt = 1
			break
if cnt == 0:
	print('YES')
else:
	print('NO')

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
cnt = 0
from collections import Counter
B=Counter(A)
C=B.most_common()
if C[0][1] <= 1:
	print('YES')
else:
	print('NO')
### BUGGY CODE ###

#A,B,C,D=map(int,input().split(" "))

N=int(input())

S=[]

for i in range(N):
  a=input()
  if a in S:
    a=0
  else:
    S.append(a)
ans=len(S)
  
print(ans)

### FIXED CODE ###

#A,B,C,D=map(int,input().split(" "))

N=int(input())

S=[]
ans=0

for i in range(N):
  S.append(input())

ans = len(list(set(S)))

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

K = int(input())
import math

def gcd_three(a, b, c):
    r = math.gcd(a, b)
    if( r == 1 ):
        return 1
    else:
        return math.gcd(r, c)
sum = 0

for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            sum += gcd_three(a,b,c)
print(sum)

### FIXED CODE ###

K = int(input())
import math
def gcd_three(a, b, c):
    r = math.gcd(a, b)
    if( r == 1 ):
        return 1
    else:
        return math.gcd(r, c)
sum = 0
if(K>2):
    for a in range(1, K-1):
        for b in range(a+1, K):
            for c in range(b+1, K+1):
                sum += gcd_three(a,b,c)*6
for a in range(1, K):
    for b in range(a+1, K+1):
        sum += math.gcd(a,b)*6
sum += K*(K+1)//2
print(sum)
### BUGGY CODE ###

class UnionFind1:
    def __init__(self, size):
        self.table = [-1 for _ in xrange(size)]

    def find(self, x):
        while self.table[x] >= 0: x = self.table[x]
        return x

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] >= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False
    
    def union_bad(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] > self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

uf=UnionFind1(100001)

n = input()
cities = [map(int,raw_input().split(" "))+[i] for i in range(n)]

cities_x = sorted(cities, key=lambda a:a[0])
cities_y = sorted(cities, key=lambda a:a[1])

road = [[cities_x[i+1][0]-cities_x[i][0],cities_x[i][2],cities_x[i+1][2]] for i in range(n-1)]
road +=[[cities_y[i+1][1]-cities_y[i][1],cities_y[i][2],cities_y[i+1][2]] for i in range(n-1)]

sum = 0
for (cost,i,j) in sorted(road):
    if(uf.find(i)!=uf.find(j)):
        uf.union(i,j)
        sum += cost

print sum


### FIXED CODE ###

class UnionFind3:
    def __init__(self, size):
        self.table = [-1 for _ in xrange(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

uf=UnionFind3(100001)

n = input()
cities = [map(int,raw_input().split(" "))+[i] for i in range(n)]

cities_x = sorted(cities, key=lambda a:a[0])
cities_y = sorted(cities, key=lambda a:a[1])

road = [[cities_x[i+1][0]-cities_x[i][0],cities_x[i][2],cities_x[i+1][2]] for i in range(n-1)]
road +=[[cities_y[i+1][1]-cities_y[i][1],cities_y[i][2],cities_y[i+1][2]] for i in range(n-1)]

sum = 0
for (cost,i,j) in sorted(road):
    if(uf.find(i)!=uf.find(j)):
        uf.union(i,j)
        sum += cost

print sum
### BUGGY CODE ###

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

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, K: int, A: "List[int]"):

    A = deque(A)
    a = deque()

    p = 1
    for i in range(K):
        t=A.popleft()
        p*=t
        a.append(t)
    
    for i in range(K, N):
        t = A.popleft()
        c = a.popleft()
        if t > c: print(YES)
        else: print(NO)
        a.append(t)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, K: int, A: "List[int]"):

    A = deque(A)
    a = deque()

    p = 1
    for i in range(K):
        t=A.popleft()
        a.append(t)
    
    for i in range(K, N):
        t = A.popleft()
        c = a.popleft()
        if t > c: print(YES)
        else: print(NO)
        a.append(t)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

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

import sys,collections as cl
import fractions
from functools import reduce
import copy
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


n = int(input())


a = l()
su = 0

aa = copy.copy(a)
for i in range(n):
	aa.pop(i)
	s = gcd_list(aa)
	su = max(su,s)
	aa = copy.copy(a)
print(su)


### FIXED CODE ###

import sys,collections as cl
import fractions
from functools import reduce
import copy
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a

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

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

n = int(input())

a = l()

m = gcd_list(a[1:])
m = max(m,gcd_list(a[:n-1]))
aa = [a[0]]
aaa = [a[-1]]
for i in range(n-1):
	aa.append(gcd(aa[-1],a[i+1]))
	aaa.append(gcd(aaa[-1],a[-(i+1)]))

for i in range(n-1):
	m = max(m,gcd(aa[i],aaa[-(i+2)]))
print(m)
### BUGGY CODE ###

def main():
    h, w, k = map(int, raw_input().split())
    c = [map(int, raw_input().strip()) for _ in xrange(h)]
    def go(a):
        if not res:
            return 0
        return go(a) * 2 + res
    ans = 0
    for ii in xrange(h):
        for jj in xrange(w):
            a = [c[i][:] for i in xrange(h)]
            a[ii][jj] = 0
            r = 0
            e = 1
            while 1:
                for j in xrange(w):
                    st = [a[i][j] for i in xrange(h) if a[i][j]]
                    for i in xrange(h):
                        a[i][j] = 0
                    i = -1
                    for x in reversed(st):
                        a[i][j] = x
                        i -= 1
                res = 0
                for i in xrange(h):
                    j = 0
                    while j < w:
                        t = j + 1
                        while t < w and a[i][j] == a[i][t]:
                            t += 1
                        if t - j >= k:
                            for j in xrange(j, t):
                                res += a[i][j]
                                a[i][j] = 0
                        j = t
                if not res:
                    break
                r += res * e
                e *= 2
            if ans < r:
                ans = r
    print ans
main()


### FIXED CODE ###

def main():
    h, w, k = map(int, raw_input().split())
    c = [map(int, raw_input().strip()) for _ in xrange(h)]
    def go(a):
        if not res:
            return 0
        return go(a) * 2 + res
    ans = 0
    for ii in xrange(h):
        for jj in xrange(w):
            a = [c[i][:] for i in xrange(h)]
            a[ii][jj] = 0
            r = 0
            e = 1
            while 1:
                for j in xrange(w):
                    st = [a[i][j] for i in xrange(h) if a[i][j]]
                    for i in xrange(h):
                        a[i][j] = 0
                    i = -1
                    for x in reversed(st):
                        a[i][j] = x
                        i -= 1
                res = 0
                for i in xrange(h):
                    j = 0
                    while j < w:
                        t = j + 1
                        while t < w and a[i][j] == a[i][t]:
                            t += 1
                        if t - j >= k:
                            for j in xrange(j, t):
                                res += a[i][j]
                                a[i][j] = 0
                        j = t
                if not res:
                    break
                r += res * e
                e *= 2
            if ans < r:
                ans = r
    print ans
main()
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
L = 0
R = max(A)
while R-L > 1:
    X = (L+R)/2
    m = 0
    for i in range(N):
        c = A[i]/X
        if c == int(c):
            m += int(c) - 1
        else:
            m += int(c)
    if m <= K:
        R = int(X)+1
    else:
        L = int(X)
print(int(R))

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
L = 0
R = max(A)
while R-L > 0.001:
    X = (L+R)/2
    m = 0
    for i in range(N):
        c = A[i]/X
        if c == int(c):
            m += int(c) - 1
        else:
            m += int(c)
    if m <= K:
        R = X
    else:
        L = X
if int(R) - int(L) == 0:
    print(int(R)+1)
else:
    print(int(R))
### BUGGY CODE ###

def scoredown(n):
    return n-1

N, K, q=map(int, input().split())
a=[int(input()) for i in range(q)]
score=[K]*N

for i in range(q):
    score=list(map(scoredown, score))
    score[a[i]-1]+=1

for i in range(N):
    if score[i]<=0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

N, K, q=map(int, input().split())
score=[0]*N

for i in range(q):
    tmp=int(input())
    score[tmp-1]+=1

for i in range(N):
    if K-(q-score[i])>0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n=int(input())

list=[]

for i in range(1,n+1):
    a=n%i
    if a == 0:
        if(i<n/i):
            list.append([i,int(n/i)])
        else:
            list.append([int(n/i),i])
            if len(list) == 1:
                ans=(list[-1][0]-1)+(list[-1][1]-1)
                break
            if list[-1]==list[-2]:
                ans=(list[-1][0]-1)+(list[-1][1]-1)
print(ans)

### FIXED CODE ###

import math

n = int(input())

for i in range(int(math.sqrt(n)), 0, -1):
  if n % i == 0:
    print(int(i + n / i - 2))
    break
### BUGGY CODE ###

# coding: utf-8
import itertools
N, M, Q = map(int,input().split())
L = list(itertools.combinations_with_replacement(range(1, M + 1), N))
D = []
for i in range(Q):
    D.append(list(map(int,input().split())))

#print(L)
#全てのA

ans = 0
for A in L:
    tmp = 0
    for i in range(Q):
        a = D[i][0]
        b = D[i][1]
        c = D[i][2]
        d = D[i][3]
        if A[b-1] - A[a-1] == c:
            tmp += d
        
        ans = max(ans,tmp)

print(ans)

### FIXED CODE ###

# coding: utf-8
import itertools
N, M, Q = map(int,input().split())
L = list(itertools.combinations_with_replacement(range(1, M + 1), N))
D = []
for i in range(Q):
    D.append(list(map(int,input().split())))

#print(l)
#全てのA

ans = 0
for A in L:
    tmp = 0
    for i in range(Q):
        a = D[i][0]
        b = D[i][1]
        c = D[i][2]
        d = D[i][3]
        if A[b-1] - A[a-1] == c:
            tmp += d
        
        ans = max(ans,tmp)

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

h, w = map(int, input().split())

grid = [[True] * (w + 2)]
for _ in range(h):
    grid.append([True] + [x == '#' for x in input()] + [True])
grid.append([True] * (w + 2))

q = []

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if grid[i][j] is True:
            q.append((i, j))

cnt = 0
while q:
    qq = []
    for i, j in q:
        if not grid[i + 1][j]:
            grid[i + 1][j] = True
            qq.append((i + 1, j))
        if not grid[i - 1][j]:
            grid[i - 1][j] = True
            qq.append((i - 1, j))
        if not grid[i][j + 1]:
            grid[i][j + 1] = True
            qq.append((i, j + 1))
        if not grid[i][j - 1]:
            grid[i][j - 1] = True
            qq.append((i, j - 1))

    cnt += 1
    q = qq

print(cnt - 1)


### FIXED CODE ###

h, w = map(int, input().split())

grid = [[True] * (w + 2)]
for _ in range(h):
    grid.append([True] + [x == '#' for x in input()] + [True])
grid.append([True] * (w + 2))

q = []

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if grid[i][j] is True:
            q.append((i, j))

cnt = 0
while q:
    qq = []
    for i, j in q:
        if not grid[i + 1][j]:
            grid[i + 1][j] = True
            qq.append((i + 1, j))
        if not grid[i - 1][j]:
            grid[i - 1][j] = True
            qq.append((i - 1, j))
        if not grid[i][j + 1]:
            grid[i][j + 1] = True
            qq.append((i, j + 1))
        if not grid[i][j - 1]:
            grid[i][j - 1] = True
            qq.append((i, j - 1))

    cnt += 1
    q = qq

print(cnt - 1)
### BUGGY CODE ###

n = int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())

for i in range(n):
    print(max(a[:i]+a[i+1:]))

### FIXED CODE ###

n = int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())

b = sorted(a)
for x in a:
    print( b[-2] if x == b[-1] else b[-1] )
### BUGGY CODE ###

import sys, heapq, bisect, math, fractions
from collections import deque
from collections import Counter
from collections import OrderedDict

N = int(input())

left = 0
right = N - 1
mid = 0

print(left, flush=True)
l = input()
if l == "Vacant":
    exit()
    
print(right, flush=True)
r = input()
if r == "Vacant":
    exit()

while left + 1 != right:
    mid = (right + left) // 2
    print(mid, flush=True)
    m = input()
    if m == "Vacant":
        exit()
        
    if ((mid - left) % 2 == 0 and l != m) or ((mid - left) % 2 == 1 and l == m):
        right = mid
    else:
        left = mid

### FIXED CODE ###

import sys, heapq, bisect, math, fractions
from collections import deque
from collections import Counter
from collections import OrderedDict

N = int(input())

left = 0
right = N - 1
mid = 0

print(left, flush=True)
l = input()
if l == "Vacant":
    exit()
    
print(right, flush=True)
r = input()
if r == "Vacant":
    exit()

while left + 1 != right:
    mid = (right + left) // 2
    print(mid, flush=True)
    m = input()
    if m == "Vacant":
        exit()
        
    if ((mid - left) % 2 == 0 and l != m) or ((mid - left) % 2 == 1 and l == m):
        right = mid
        r = m
    else:
        left = mid
        l = m
### BUGGY CODE ###

N = int(input())
s = ["".join(sorted(input())) for i in range(N)]

#print(s)

#出現文字列
sdict = {}

ans = 0

for i in range(N):

    s_i = str(s[i])

    if s_i in sdict:
        #組み合わせが増えるので
        sdict[s_i]+= 1
        continue

    for j in range(i+1,N):
        sdict[s_i] = 1

for i in sdict.values():
    ans += i*(i-1)//2

print(ans)


### FIXED CODE ###

N = int(input())
s = ["".join(sorted(input())) for i in range(N)]

#print(s)

#出現文字列
sdict = {}

for i in range(N):

    s_i = str(s[i])

    if s_i in sdict:
        #組み合わせが増えるので
        sdict[s_i]+= 1
        continue

    else:
        sdict[s_i] = 1

ans = 0
for i in sdict.values():
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

import bisect

a,b,q = map(int,input().split())
s = [-10**11] + [int(input()) for i in range(a)] + [10**11]
t = [-10**11] + [int(input()) for i in range(b)] + [10**11]



for i in range(q):
    x = int(input())
    xs = bisect.bisect_right(s,x)
    xt = bisect.bisect_right(t,x)
    ss = [x-s[xs-1],s[xs]-x]
    tt = [x-t[xt-1],t[xt]-x]
    print(min(max(ss[0],tt[0]), max(ss[1],tt[1]), ss[0]*2+tt[1], ss[1]*2+tt[0], tt[0]*2+ss[1], tt[1]*2+ss[0]))


### FIXED CODE ###

import bisect

a,b,q = map(int,input().split())
s = [-10**11] + [int(input()) for i in range(a)] + [10**11]
t = [-10**11] + [int(input()) for i in range(b)] + [10**11]



for i in range(q):
    x = int(input())
    xs = bisect.bisect_right(s,x)
    xt = bisect.bisect_right(t,x)
    ss = [x-s[xs-1],s[xs]-x]
    tt = [x-t[xt-1],t[xt]-x]
    print(min(max(ss[0],tt[0]), max(ss[1],tt[1]), ss[0]*2+tt[1], ss[1]*2+tt[0], tt[0]*2+ss[1], tt[1]*2+ss[0]))