Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys


def solve(n: int, m: int, Q: int, s: "List[int]", t: "List[int]", x: "List[int]"):

    def check_pos(target, a, x):
        ret = {}
        a_x = a + x
        a_x.sort()
        idx = 0
        while idx < len(a_x) and a_x[idx] < target[0]:
            dis = target[0] - a_x[idx]
            ret[a_x[idx]] = [dis, [target[0], dis]] # [pos, dis]
            idx += 1
        for i in range(len(target) - 1):
            while idx < len(a_x) and target[i] <= a_x[idx] <= target[i + 1]:
                pos = a_x[idx]
                l = a_x[idx] - target[i]
                r = target[i + 1] - a_x[idx]
                ret[pos] = [
                    min(l, r),
                    [target[i],     l],
                    [target[i + 1], r]
                ]
                idx += 1
        while idx < len(a_x):
            dis = a_x[idx] - target[-1]
            ret[a_x[idx]] = [dis, [target[-1], dis]] # [pos, dis]
            idx += 1
        return ret

    nearest_s = check_pos(s, t, x)
    nearest_t = check_pos(t, s, x)

    for q in x:
        ret = min(
                min([(pos_dis[1] + nearest_t[pos_dis[0]][0]) for pos_dis in nearest_s[q][1:]]),
                min([(pos_dis[1] + nearest_s[pos_dis[0]][0]) for pos_dis in nearest_t[q][1:]]))
        print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    s = [ int(next(tokens)) for _ in range(A) ]  # type: "List[int]"
    t = [ int(next(tokens)) for _ in range(B) ]  # type: "List[int]"
    x = [ int(next(tokens)) for _ in range(Q) ]  # type: "List[int]"
    solve(A, B, Q, s, t, x)

if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, Q: int, s: "List[int]", t: "List[int]", x: "List[int]"):

    def binary_search(ary, val):
        n = len(ary)
        l = -1
        r = n
        while r - l > 1:
            mid = (l + r) // 2
            if ary[mid] >= val:
                r = mid
            else:
                l = mid
        if l == -1:
            return [ary[0]]
        if r == n:
            return [ary[n - 1]]
        return [ary[l], ary[r]]

    for q in x:
        ret = float('inf')
        a_pos = binary_search(s, q)
        b_pos = binary_search(t, q)
        for a in a_pos:
            for b in b_pos:
                ret = min(ret, abs(a - q) + abs(b - a))
                ret = min(ret, abs(b - q) + abs(a - b))
        print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    s = [ int(next(tokens)) for _ in range(A) ]  # type: "List[int]"
    t = [ int(next(tokens)) for _ in range(B) ]  # type: "List[int]"
    x = [ int(next(tokens)) for _ in range(Q) ]  # type: "List[int]"
    solve(A, B, Q, s, t, x)

if __name__ == '__main__':
    main()