## https://yukicoder.me/problems/no/3072 from collections import deque MAX_INT = 10 ** 18 def main(): N, Ka, Kb = map(int, input().split()) A = list(map(int, input().split())) B = list(map(int, input().split())) Q = int(input()) st = [] for _ in range(Q): s, t = map(int, input().split()) st.append((s - 1, t - 1)) # A -> Bを使うパターン b_set = set([b - 1 for b in B]) array_a = [MAX_INT] * (N + 2) queue = deque() array_a[N] = 0 for a in A: array_a[a - 1] = 0 queue.append(a - 1) while len(queue) > 0: x = queue.popleft() if x < N: for dx in (-1, 1): new_x = dx + x if 0 <= new_x < N: if array_a[new_x] > array_a[x] + 1: array_a[new_x] = array_a[x] + 1 queue.append(new_x) if x in b_set: if array_a[N + 1] > array_a[x]: array_a[N + 1] = array_a[x] queue.appendleft(N + 1) else: for b in b_set: if array_a[b] > array_a[x]: array_a[b] = array_a[x] queue.appendleft(b) # B -> Aを使うパターン a_set = set([a - 1 for a in A]) array_b = [MAX_INT] * (N + 2) queue = deque() array_b[N + 1] = 0 for b in B: array_b[b - 1] = 0 queue.append(b - 1) while len(queue) > 0: x = queue.popleft() if x < N: for dx in (-1, 1): new_x = dx + x if 0 <= new_x < N: if array_b[new_x] > array_b[x] + 1: array_b[new_x] = array_b[x] + 1 queue.append(new_x) if x in a_set: if array_b[N] > array_b[x]: array_b[N] = array_b[x] queue.appendleft(N) else: for a in a_set: if array_b[a] > array_b[x]: array_b[a] = array_b[x] queue.appendleft(a) # Aに乗るパターン array_a1 = [MAX_INT] * (N + 2) queue = deque() array_a1[N] = 0 for a in A: array_a1[a - 1] = 0 queue.append(a - 1) while len(queue) > 0: x = queue.popleft() for dx in (-1, 1): new_x = dx + x if 0 <= new_x < N: if array_a1[new_x] > array_a1[x] + 1: array_a1[new_x] = array_a1[x] + 1 queue.append(new_x) # Bに乗るパターン array_b1 = [MAX_INT] * (N + 2) queue = deque() array_b1[N + 1] = 0 for b in B: array_b1[b - 1] = 0 queue.append(b - 1) while len(queue) > 0: x = queue.popleft() for dx in (-1, 1): new_x = dx + x if 0 <= new_x < N: if array_b1[new_x] > array_b1[x] + 1: array_b1[new_x] = array_b1[x] + 1 queue.append(new_x) for s, t in st: answer = abs(s - t) answer = min(array_a1[s] + array_a[t], answer ) answer = min(array_b1[s] + array_b[t], answer ) print(answer) if __name__ == "__main__": main()