Problem:
 Score : 400 points    Problem Statement Along a road running in an east-west direction, there are A shrines and B temples.
The i -th shrine from the west is located at a distance of s_i meters from the west end of the road, and the i -th temple from the west is located at a distance of t_i meters from the west end of the road.  Answer the following Q queries:   Query i ( 1 \leq i \leq Q ): If we start from a point at a distance of x_i meters from the west end of the road and freely travel along the road, what is the minimum distance that needs to be traveled in order to visit one shrine and one temple? (It is allowed to pass by more shrines and temples than required.)       Constraints  1 \leq A, B \leq 10^5  1 \leq Q \leq 10^5  1 \leq s_1 < s_2 < ... < s_A \leq 10^{10}  1 \leq t_1 < t_2 < ... < t_B \leq 10^{10}  1 \leq x_i \leq 10^{10}  s_1, ..., s_A, t_1, ..., t_B, x_1, ..., x_Q are all different.  All values in input are integers.         Input Input is given from Standard Input in the following format:  A  B  Q  s_1  :  s_A  t_1  :  t_B  x_1  :  x_Q       Output Print Q lines. The i -th line should contain the answer to the i -th query.        Sample Input 1 2 3 4
100
600
400
900
1000
150
2000
899
799      Sample Output 1 350
1400
301
399  There are two shrines and three temples. The shrines are located at distances of 100, 600 meters from the west end of the road, and the temples are located at distances of 400, 900, 1000 meters from the west end of the road.   Query 1 : If we start from a point at a distance of 150 meters from the west end of the road, the optimal move is first to walk 50 meters west to visit a shrine, then to walk 300 meters east to visit a temple.  Query 2 : If we start from a point at a distance of 2000 meters from the west end of the road, the optimal move is first to walk 1000 meters west to visit a temple, then to walk 400 meters west to visit a shrine. We will pass by another temple on the way, but it is fine.  Query 3 : If we start from a point at a distance of 899 meters from the west end of the road, the optimal move is first to walk 1 meter east to visit a temple, then to walk 300 meters west to visit a shrine.  Query 4 : If we start from a point at a distance of 799 meters from the west end of the road, the optimal move is first to walk 199 meters west to visit a shrine, then to walk 200 meters west to visit a temple.        Sample Input 2 1 1 3
1
10000000000
2
9999999999
5000000000      Sample Output 2 10000000000
10000000000
14999999998  The road is quite long, and we may need to travel a distance that does not fit into a 32 -bit integer.

Solution (Python):

import sys
from bisect import bisect_left, bisect_right
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
from functools import reduce
from random import shuffle
sys.setrecursionlimit(200000)





input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()


class RBNode:
    def __init__(self, val, is_red=True, parent=None, left=None, right=None):
        self.val = val
        self.parent = parent
        self.left = left
        self.right = right
        self.color = is_red


class RBTree:
    def __init__(self):
        self.root = None

    def left_rotate(self, node):
        
        right_node = node.right
        if right_node is None:
            return
        else:
            
            node.right = right_node.left
            if right_node.left is not None:
                right_node.left.parent = node
            right_node.parent = node.parent
            
            if node.parent is None:
                self.root = right_node
            elif node is node.parent.left:
                node.parent.left = right_node
            else:
                node.parent.right = right_node
            right_node.left = node
            node.parent = right_node

    def right_rotate(self, node):
        
        left_node = node.left
        if left_node is None:
            return
        else:
            
            node.left = left_node.right
            if left_node.right is not None:
                left_node.right.parent = node
            left_node.parent = node.parent
            
            if node.parent is None:
                self.root = left_node
            elif node is node.parent.left:
                node.parent.left = left_node
            else:
                node.parent.right = left_node
            left_node.right = node
            node.parent = left_node

    def insert(self, node):
        
        root = self.root
        insert_node_parent = None
        
        while root is not None:
            insert_node_parent = root
            if insert_node_parent.val < node.val:
                root = root.right
            else:
                root = root.left
        
        node.parent = insert_node_parent
        if insert_node_parent is None:
            
            self.root = node
        elif insert_node_parent.val > node.val:
            
            insert_node_parent.left = node
        else:
            insert_node_parent.right = node
        node.left = None
        node.right = None
        node.color = 1
        
        self.fix_insert(node)

    def fix_insert(self, node):
        
        if node.parent is None:
            node.color = 0
            self.root = node
            return
            
        
        while node.parent and node.parent.color == 1:
            if node.parent is node.parent.parent.left:
                uncle_node = node.parent.parent.right
                if uncle_node and uncle_node.color == 1:
                    
                    
                    
                    node.parent.color = 0
                    node.parent.parent.right.color = 0
                    node.parent.parent.color = 1
                    node = node.parent.parent
                    continue
                elif node is node.parent.right:
                    
                    
                    
                    node = node.parent
                    self.left_rotate(node)
                
                
                node.parent.color = 0
                node.parent.parent.color = 1
                self.right_rotate(node.parent.parent)
            else:
                uncle_node = node.parent.parent.left
                if uncle_node and uncle_node.color == 1:
                    
                    
                    
                    node.parent.color = 0
                    node.parent.parent.left.color = 0
                    node.parent.parent.color = 1
                    node = node.parent.parent
                    continue
                elif node is node.parent.left:
                    
                    
                    
                    node = node.parent
                    self.right_rotate(node)
                
                
                node.parent.color = 0
                node.parent.parent.color = 1
                self.left_rotate(node.parent.parent)
        self.root.color = 0

    def transplant(self, node_u, node_v):
        """
        replace u with v
        :param node_u: replaced node
        :param node_v:
        :return: None
        """
        if node_u.parent is None:
            self.root = node_v
        elif node_u is node_u.parent.left:
            node_u.parent.left = node_v
        elif node_u is node_u.parent.right:
            node_u.parent.right = node_v
        
        if node_v:
            node_v.parent = node_u.parent

    def find(self, key):
        node = self.root
        while node is not None:
            if node.val < key:
                node = node.right
            elif node.val > key:
                node = node.left
            else:
                return node

    def maximum(self, node):
        """
        find the max node when node regard as a root node
        :param node:
        :return: max node
        """
        temp_node = node
        while temp_node.right:
            temp_node = temp_node.right
        return temp_node

    def minimum(self, node):
        """
        find the minimum node when node regard as a root node
        :param node:
        :return: minimum node
        """
        temp_node = node
        while temp_node.left:
            temp_node = temp_node.left
        return temp_node

    def search_higher(self, key, key_higher=None):
        node = self.root
        if node.val is None:
            return key_higher
        ans = key_higher
        while node is not None:
            if node.val > key:
                ans = min(ans, node.val)
                node = node.left
            elif node.val <= key:
                node = node.right
        return ans

    def search_lower(self, key, key_lower=None):
        node = self.root
        if node.val is None:
            return key_lower
        ans = key_lower
        while node is not None:
            if node.val < key:
                ans = max(ans, node.val)
                node = node.right
            elif node.val >= key:
                node = node.left
        return ans

    def delete(self, node):
        
        node_color = node.color
        if node.left is None:
            temp_node = node.right
            self.transplant(node, node.right)
        elif node.right is None:
            temp_node = node.left
            self.transplant(node, node.left)
        else:
            
            node_min = self.minimum(node.right)
            node_color = node_min.color
            temp_node = node_min.right
            
            if node_min.parent != node:
                self.transplant(node_min, node_min.right)
                node_min.right = node.right
                node_min.right.parent = node_min
            self.transplant(node, node_min)
            node_min.left = node.left
            node_min.left.parent = node_min
            node_min.color = node.color
        
        if node_color == 0:
            self.delete_fixup(temp_node)

    def delete_fixup(self, node):
        
        while node != self.root and node.color == 0:
            
            if node == node.parent.left:
                
                node_brother = node.parent.right

                
                
                if node_brother.color == 1:
                    node_brother.color = 0
                    node.parent.color = 1
                    self.left_rotate(node.parent)
                    node_brother = node.parent.right

                
                if (node_brother.left is None or node_brother.left.color == 0) and (
                        node_brother.right is None or node_brother.right.color == 0):
                    node_brother.color = 1
                    node = node.parent
                else:

                    
                    if node_brother.right is None or node_brother.right.color == 0:
                        node_brother.color = 1
                        node_brother.left.color = 0
                        self.right_rotate(node_brother)
                        node_brother = node.parent.right

                    
                    node_brother.color = node.parent.color
                    node.parent.color = 0
                    node_brother.right.color = 0
                    self.left_rotate(node.parent)
                node = self.root
                break
            else:
                node_brother = node.parent.left
                if node_brother.color == 1:
                    node_brother.color = 0
                    node.parent.color = 1
                    self.left_rotate(node.parent)
                    node_brother = node.parent.right
                if (node_brother.left is None or node_brother.left.color == 0) and (
                        node_brother.right is None or node_brother.right.color == 0):
                    node_brother.color = 1
                    node = node.parent
                else:
                    if node_brother.left is None or node_brother.left.color == 0:
                        node_brother.color = 1
                        node_brother.right.color = 0
                        self.left_rotate(node_brother)
                        node_brother = node.parent.left
                    node_brother.color = node.parent.color
                    node.parent.color = 0
                    node_brother.left.color = 0
                    self.right_rotate(node.parent)
                node = self.root
                break
        node.color = 0

    def output(self):
        res = []
        if not self.root:
            print()
        que = deque()
        root = self.root
        que.append(root)
        while que:
            root = que.popleft()
            if root.parent:
                res.append({'parent': root.parent.val, 'val': root.val, 'color': root.color})
            else:
                res.append({'val': root.val, 'color': root.color})
            if root.left is not None:
                que.append(root.left)
            if root.right is not None:
                que.append(root.right)
        print(*res, sep="\n")
        return



def main():
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    rb1 = RBTree()
    a, b, q = map(int, input().split())

    rb2 = RBTree()
    for i in range(a):
        s = ii()
        rb1.insert(RBNode(s))
    for i in range(b):
        t = ii()
        rb2.insert(RBNode(t))
    
    
    for i in range(q):
        x = ii()
        s1 = rb1.search_lower(x, -10**18)
        s2 = rb1.search_higher(x, 10**18)
        t1 = rb2.search_lower(x, -10**18)
        t2 = rb2.search_higher(x, 10**18)
        
        res = 10**18
        for S in [s1, s2]:
            for T in [t1, t2]:
                d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
                res = min(res, d1, d2)
        print(res)




if __name__ == '__main__':
    main()

Solution (Python):
import bisect
A, B, Q = map(int, input().split())
ss = []
for i in range(A):
  s = int(input())
  ss.append(s)
ts = []
for i in range(B):
  t = int(input())
  ts.append(t)

for i in range(Q):
  x = int(input())
  Is = bisect.bisect_left(ss, x)
  It = bisect.bisect_left(ts, x)
  ss2 = ss[Is-1 if Is > 0 else Is:Is+1]
  ts2 = ts[It-1 if It > 0 else It:It+1]
  
  rs = []
  for s in ss2:
    for t in ts2:
      r = abs(s-x)+abs(t-s)
      rs.append(r)
      r = abs(t-x)+abs(s-t)
      rs.append(r)
  r = min(rs)
  print(r)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))



from bisect import bisect_left, bisect_right

A,B,Q = II()
s = [I() for _ in range(A)]
t = [I() for _ in range(B)]
x = [I() for _ in range(Q)]

for i in range(Q):
    val = float('inf')
    a = bisect_left(s,x[i])
    if a<=A-1:
        b = bisect_left(t,s[a])
        if b<=B-1:
            val = min(val, abs(x[i]-s[a]) + abs(s[a]-t[b]))
        if b>=1:
            val = min(val, abs(x[i]-s[a]) + abs(s[a]-t[b-1]))
    if a>=1:
        b = bisect_left(t,s[a-1])
        if b<=B-1:
            val = min(val, abs(x[i]-s[a-1]) + abs(s[a-1]-t[b]))
        if b>=1:
            val = min(val, abs(x[i]-s[a-1]) + abs(s[a-1]-t[b-1]))

    b = bisect_left(t,x[i])
    if b<=B-1:
        a = bisect_left(s,t[b])
        if a<=A-1:
            val = min(val, abs(x[i]-t[b]) + abs(t[b]-s[a]))
        if a>=1:
            val = min(val, abs(x[i]-t[b]) + abs(t[b]-s[a-1]))
    if b>=1:
        a = bisect_left(s,t[b-1])
        if a<=A-1:
            val = min(val, abs(x[i]-t[b-1]) + abs(t[b-1]-s[a]))
        if a>=1:
            val = min(val, abs(x[i]-t[b-1]) + abs(t[b-1]-s[a-1]))
    
    print(val)

Solution (Python):
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 i 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(d1, d2, res)
  print(res)

Solution (Python):
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 i 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(d1, d2, res)
  print(res)

Solution (Python):
INF = float('inf')
from bisect import bisect_left
a, b, q = map(int, input().split())
s = [int(input()) for _ in range(a)]
t = [int(input()) for _ in range(b)]
def f(x, s, t):
  result = INF
  i = bisect_left(s, x)
  if i > 0:
    j = bisect_left(t, s[i - 1])
    if j > 0:
      result = min(result, (x - s[i - 1]) + (s[i - 1] - t[j - 1]))
    if j < len(t):
      result = min(result, (x - s[i - 1]) + (t[j] - s[i - 1]))
  if i < len(s):
    j = bisect_left(t, s[i])
    if j > 0:
      result = min(result, (s[i] - x) + (s[i] - t[j - 1]))
    if j < len(t):
      result = min(result, (s[i] - x) + (t[j] - s[i]))
  return result
for i in range(q):
  x = int(input())
  print(min(f(x, s, t), f(x, t, s)))

Solution (Python):
from bisect import bisect_left
a, b, q = map(int, input().split())
s = [int(input()) for _ in range(a)]
t = [int(input()) for _ in range(b)]
def f(x, s, t):
  result = float('inf')
  i = bisect_left(s, x)
  if i > 0:
    j = bisect_left(t, s[i - 1])
    if j > 0:
      result = min(result, (x - s[i - 1]) + (s[i - 1] - t[j - 1]))
    if j < len(t):
      result = min(result, (x - s[i - 1]) + (t[j] - s[i - 1]))
  if i < len(s):
    j = bisect_left(t, s[i])
    if j > 0:
      result = min(result, (s[i] - x) + (s[i] - t[j - 1]))
    if j < len(t):
      result = min(result, (s[i] - x) + (t[j] - s[i]))
  return result
for i in range(q):
  x = int(input())
  print(min(f(x, s, t), f(x, t, s)))

Solution (Python):
import bisect
a, b, q = map(int, input().split())
inf = 10**18
lst1 = [-inf] + [(int(input())) for i in range(a)] + [inf]
lst2 = [-inf] + [(int(input())) for i in range(b)] + [inf]
left = 0
for i in range(q):
    x = int(input())
    j = bisect.bisect_right(lst1, x)
    k = bisect.bisect_right(lst2, x)
    res = inf
    for s in [lst1[j-1], lst1[j]]:
        for t in [lst2[k-1], lst2[k]]:
            ans1 = abs(x-s) + abs(s-t)
            ans2 = abs(x-t) + abs(t-s)
            res = min(res, ans1, ans2)
    print(res)

Solution (Python):
import bisect


def resolve():
    A, B, Q = map(int, input().split())
    INF = 10 ** 18
    s = [-INF] + list(int(input()) for _ in range(A)) + [INF]
    t = [-INF] + list(int(input()) for _ 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)


if __name__ == "__main__":
    resolve()

Solution (Python):
from bisect import bisect_left
INF = 10**18
A, B, Q = map(int, input().split())
als = [int(input()) for i in range(A)]
bls = [int(input()) for i in range(B)]
als = [-INF]+als+[INF]
bls = [-INF]+bls+[INF]

for i in range(Q):
  x = int(input())
  ai = bisect_left(als,x)
  bi = bisect_left(bls,x)
  res = INF
  for S in [als[ai], als[ai-1]]:
    for T in [bls[bi], bls[bi-1]]:
      d1, d2 = abs(S-x)+abs(T-S), abs(T-x)+abs(S-T)
      res = min(res,d1,d2)
  print(res)

Solution (Python):
from bisect import bisect

INF = 10**24

A, B, Q = map(int, input().split())
S, T, X = [[int(input()) for _ in range(m)] for m in [A, B, Q]]

S = [-INF] + S + [INF]
T = [-INF] + T + [INF]

for x in X:
    s_i = bisect(S, x)
    t_i = bisect(T, x)
    points = [S[s_i-1], S[s_i], T[t_i-1], T[t_i]]
    min_cost = INF
    for j, p_j in enumerate(points):
        for k, p_k in enumerate(points):
            if j//2 == k//2:
                continue
            cost = abs(p_j-x) + abs(p_k-p_j)
            min_cost = min(min_cost, cost)
    print(min_cost)

Solution (Python):
import bisect

a,b,q = map(int,input().split())
s = [0] * a
t = [0] * b
ans = []

for i in range(a):
    s[i] = int(input())
for j in range(b):
    t[j] = int(input())
for x in range(q):
    x = int(input())
    shr = bisect.bisect_left(s,x)
    if shr == 0:
        shrr = shr
    elif shr == a:
        shr = a - 1
        shrr = a - 1
    else:
        shrr = shr - 1
    
    tem = bisect.bisect_left(t,x)
    if tem == 0:
        temm = tem
    elif tem == b:
        tem = b - 1
        temm = b - 1
    else:
        temm = tem - 1
    
    can = []
    l = [[shr,tem],[shr,temm],[shrr,tem],[shrr,temm]]
    
    for i in range(4):
        can.append(min(abs(s[l[i][0]]-x)+abs(t[l[i][1]]-s[l[i][0]]),abs(t[l[i][1]]-x)+abs(s[l[i][0]]-t[l[i][1]])))
    
    ans.append(min(can))

for p in ans:
    print(p)

Solution (Python):
import bisect

a,b,q = map(int,input().split())
s = [0] * a
t = [0] * b
ans = []

for i in range(a):
    s[i] = int(input())
for j in range(b):
    t[j] = int(input())
for x in range(q):
    x = int(input())
    shr = bisect.bisect_left(s,x)
    if shr == 0:
        shrr = shr
    elif shr == a:
        shr = a - 1
        shrr = a - 1
    else:
        shrr = shr - 1
    
    tem = bisect.bisect_left(t,x)
    if tem == 0:
        temm = tem
    elif tem == b:
        tem = b - 1
        temm = b - 1
    else:
        temm = tem - 1
    
    can = []
    l = [[shr,tem],[shr,temm],[shrr,tem],[shrr,temm]]
    
    for i in range(4):
        can.append(min(abs(s[l[i][0]]-x)+abs(t[l[i][1]]-s[l[i][0]]),abs(t[l[i][1]]-x)+abs(s[l[i][0]]-t[l[i][1]])))
    
    ans.append(min(can))

for p in ans:
    print(p)

Solution (Python):
import sys
input = sys.stdin.readline

import bisect

INF = 1e+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=[int(input()) for _ in range(Q)]

for i in range(Q):
    a,b=bisect.bisect_right(s,x[i]), bisect.bisect_right(t,x[i])
    ans = INF
    for j in [s[a-1], s[a]]:
        for k in [t[b-1], t[b]]:
            d1 = abs(j-x[i])+abs(j-k)
            d2 = abs(k-x[i])+abs(j-k)
            ans = min(ans, d1, d2)
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

import bisect

INF = 1e+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 = [int(input()) for _ in range(Q)]

for i in range(Q):
    a,b= bisect.bisect_right(s,x[i]), bisect.bisect_right(t,x[i])
    ans = INF
    for S in [s[a-1], s[a]]:
        for T in [t[b-1], t[b]]:
            d1 = abs(S-x[i])+abs(S-T)
            d2 = abs(T-x[i])+abs(S-T)
            ans = min(ans, d1, d2)
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

import bisect

INF = 1e+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 = [int(input()) for _ in range(Q)]

for i in range(Q):
    a,b= bisect.bisect_right(s,x[i]), bisect.bisect_right(t,x[i])
    ans = INF
    for S in [s[a-1], s[a]]:
        for T in [t[b-1], t[b]]:
            d1 = abs(S-x[i])+abs(S-T)
            d2 = abs(T-x[i])+abs(S-T)
            ans = min(ans, d1, d2)
    print(ans)

Solution (Python):
def main():
    from bisect import bisect_left,bisect
    import sys
    input = sys.stdin.readline
    A,B,Q = map(int, input().split())
    S = [int(input()) for i in range(A)]
    T = [int(input()) for i in range(B)]
    X = [int(input()) for i in range(Q)]
    
    for i in X:
        ans = float("inf")
        j = min(bisect(S,i),A-1)
        k = min(bisect(T,i),B-1)
        l = [min(bisect(T,S[j]),B-1), min(bisect(T,S[j-1]),B-1)]
        r = [min(bisect(S,T[k]),A-1), min(bisect(S,T[k-1]),A-1)]
        for p in range(2):
            for q in range(2):
                tmp = abs(S[j-p] - i) + abs(T[l[p]-q] - S[j-p])
                if tmp < ans:
                    ans = tmp
                tmp = abs(T[k-p] - i) + abs(S[r[p]-q] - T[k-p])
                if tmp < ans:
                    ans = tmp
        print(ans)
    
    
    
    
main()

Solution (Python):
def main():
    A, B, Q = map(int, input().split())
    S = [float("-inf")]
    T = [float("-inf")]
    X = []
    for _ in range(A): S.append(int(input()))
    for _ in range(B): T.append(int(input()))
    for i in range(Q): X.append([int(input()), i])
    S.append(float("inf"))
    T.append(float("inf"))
    X.sort(key = lambda x: x[0])
    A = len(S)
    B = len(T)

    ans = []
    i, j = 0, 0
    for k in range(Q):
        min_d = float('inf')
        x, l = X[k]
        while i < A and S[i] < x: i += 1
        while j < B and T[j] < x: j += 1

        if i-1 < A and j-1 < B:
            min_d = min(min_d, max(x-S[i-1], x-T[j-1]))
        if i < A and j < B:
            min_d = min(min_d, max(S[i]-x, T[j]-x))
        if i < A and j-1 < B:
            min_d = min(min_d, S[i]-T[j-1] + min(S[i]-x, x-T[j-1]))
        if i-1 < A and j < B:
            min_d = min(min_d, T[j]-S[i-1] + min(T[j]-x, x-S[i-1]))

        ans.append([l, min_d])
    ans.sort(key = lambda x: x[0])
    return [a for _, a in ans]


if __name__ == '__main__':
    output = main()
    for a in output:
        print(a)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect_left

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

A, B, Q = MAP()
s = [-INF]+[INT() for _ in range(A)]+[INF]
t = [-INF]+[INT() for _ in range(B)]+[INF]
x = [INT() for _ in range(Q)]

for q in x:
	b, d = bisect_left(s, q), bisect_left(t, q)
	res = INF
	for S in [s[b-1], s[b]]:
		for T in [t[d-1], t[d]]:
			d1, d2 = abs(S-q) + abs(T-S), abs(T-q) + abs(S-T)
			res = min(res, d1, d2)
	print(res)

Solution (Python):
from bisect import bisect_left, bisect_right
INF = 10**12
A, B, Q = map(int, input().split())
shrines = [-INF] + [int(input()) for _ in range(A)] + [INF]
temples = [-INF] + [int(input()) for _ in range(B)] + [INF]
for _ in range(Q):
  query = int(input())
  sh_pos = bisect_left(shrines, query)
  te_pos = bisect_left(temples, query)
  ans = INF
  for s in shrines[sh_pos-1:sh_pos+1]:
    for t in temples[te_pos-1:te_pos+1]:
      dis = min(abs(s-query)+abs(s-t),abs(t-query)+abs(t-s))
      ans = min(ans, dis)
  print(ans)

Solution (Python):
import bisect

SList = []
TList = []
QList = []
minpos = -1*(10**10)
maxpos = 10*(10**10)

def ans(x):
    index = bisect.bisect_left(SList,x)
    s = [SList[index-1],SList[index]]

    index = bisect.bisect_left(TList,x)
    t = [TList[index-1],TList[index]]

    min1 = abs(x-s[0])+abs(t[0]-s[0])
    diff = abs(x-s[0])+abs(t[1]-s[0])
    if diff < min1:
        min1 = diff
    diff = abs(x-s[1])+abs(t[0]-s[1])
    if diff < min1:
        min1 = diff
    diff = abs(x-s[1])+abs(t[1]-s[1])
    if diff < min1:
        min1 = diff
    diff = abs(x-t[0])+abs(s[0]-t[0])
    if diff < min1:
        min1 = diff
    diff = abs(x-t[0])+abs(s[1]-t[0])
    if diff < min1:
        min1 = diff
    diff = abs(x-t[1])+abs(s[0]-t[1])
    if diff < min1:
        min1 = diff
    diff = abs(x-t[1])+abs(s[1]-t[1])
    if diff < min1:
        min1 = diff
    return min1

A,B,Q = map(int,input().split())
for _ in range(A):
    SList.append(int(input()))
for _ in range(B):
    TList.append(int(input()))
for _ in range(Q):
    QList.append(int(input()))

SList.insert(0,minpos)
SList.append(maxpos)
TList.insert(0,minpos*2)
TList.append(maxpos*2)
for q in QList:
    print(ans(q))

Solution (Python):
import bisect
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 i in range(Q):
  ans = []
  sin = bisect.bisect_left(S, X[i])
  if sin == 0:
    s1,s2 = S[sin], -(10**12)
  elif sin == A:
    s1,s2 = (10**12),S[sin-1]
  else:
    s1,s2 = S[sin],S[sin-1]
  tin = bisect.bisect_left(T, X[i])
  if tin == 0:
    t1,t2 = T[tin], -(10**12)
  elif tin == B:
    t1,t2 = (10**12),T[tin-1]
  else:
    t1,t2 = T[tin],T[tin-1]
  for j in [s1,s2]:
    for k in [t1,t2]:
      for l in [0,1]:
        if l ==0:
          ans.append(abs(j-X[i])+abs(k-j))
        else:
          ans.append(abs(k-X[i])+abs(j-k)) 
          
  print(min(ans))

Solution (Python):
import bisect


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

Solution (Python):
from bisect import bisect_left
from itertools import product
I = lambda n: [int(input()) for _ in range(n)]
def f(S, x):
    p = bisect_left(S, x)
    return [S[p-1], S[p]]
g = lambda x, s, t: abs(x-s)+abs(s-t)
INF = 10**11
a, b, q = map(int, input().split())
S, T, X = [-INF]+I(a)+[INF], [-INF]+I(b)+[INF], I(q)
for x in X:
    min_ = INF
    for s, t in product(f(S, x), f(T, x)):
        min_ = min(min_, g(x, s, t), g(x, t, s))
    print(min_)

Solution (Python):
import bisect
from itertools import product
I = lambda n: [int(input()) for _ in range(n)]
def f(S, x):
    p = bisect.bisect_left(S, x)
    return [S[p-1], S[p]]
g = lambda x, s, t: abs(x-s)+abs(s-t)
INF = 10**11
a, b, q = map(int, input().split())
S, T, X = [-INF]+I(a)+[INF], [-INF]+I(b)+[INF], I(q)
for x in X:
    min_ = INF
    for s, t in product(f(S, x), f(T, x)):
        min_ = min(min_, g(x, s, t), g(x, t, s))
    print(min_)

Solution (Python):
import bisect
from itertools import product
I = lambda n: [int(input()) for _ in range(n)]
def f(S, x):
    p = bisect.bisect_left(S, x)
    return [S[p-1], S[p]]
g = lambda x, s, t: abs(x-s)+abs(s-t)
INF = 10**11
a, b, q = map(int, input().split())
S, T, X = [-INF]+I(a)+[INF], [-INF]+I(b)+[INF], I(q)
for x in X:
    min_ = INF
    for s, t in product(f(S, x), f(T, x)):
        min_ = min(min_, g(x, s, t), g(x, t, s))
    print(min_)