가속기

거대한 입자 가속기를 건설하려고 한다. 이 가속기는 많은 다리(bridge)를 포함하는 커다란 전기 회로로 볼 수 있으며, 다리들은 전선으로 연결해야 한다. 다리에는 빨간 다리와 파란 다리가 있고, 각 빨간 다리는 정확히 하나의 파란 다리와 전선으로 연결되어야 한다. 목표는 빨간 다리와 파란 다리를 잇는 전선의 총 길이를 최소로 만드는 것이다.

좀 더 정확히 말하면, 가속기는 하나의 원이고 원 위의 빨간 점과 파란 점이 각각 빨간 다리와 파란 다리를 나타낸다. 빨간 점의 개수는 파란 점의 개수보다 많지 않으며, 모든 점의 위치는 서로 다르다. 각 빨간 점은 전선으로 파란 점 하나에 연결되어야 하고, 서로 다른 두 빨간 점이 같은 파란 점에 연결될 수는 없다. 전선의 길이는 두 점을 잇는 두 호(arc) 중 더 짧은 호의 길이이며, 목표는 이렇게 짝지어진 모든 쌍에 대한 호 길이의 합을 최소화하는 것이다.

편의상 원의 둘레는 $n$이고, 인접한 두 위치 사이의 호 길이가 $1$이 되도록 원 위의 $n$개의 위치만 생각한다. 위치는 시계 방향으로 $0, 1, \dots, n - 1$로 번호를 매긴다. 모든 빨간 점과 파란 점은 이 위치들 중 하나에 놓이므로 그 위치는 $\{0, 1, \dots, n - 1\}$ 중 한 정수이고, 임의의 빨간 점과 파란 점 사이의 거리는 항상 정수이다. 예를 들어 그림 1은 위치가 12개인 원 위의 빨간 점 3개와 파란 점 3개를 보여 준다. 최적의 연결에서는 위치 1, 3, 9의 빨간 점이 각각 위치 5, 4, 10의 파란 점과 연결되어 호 길이의 합이 최소인 6이 된다.

그림 1.

원 위의 빨간 점과 파란 점이 주어질 때, 짝지어진 쌍 사이의 더 짧은 호 길이의 합이 최소가 되도록 빨간 점을 파란 점에 연결하는 프로그램을 작성하시오.

입력은 표준 입력으로 주어진다. 첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 세 줄로 이루어진다.

첫째 줄에는 세 정수 $n$, $a$, $b$가 주어진다 ($1 \le n \le 1{,}000{,}000$, $1 \le a \le b \le 1{,}000{,}000$, $2 \le a + b \le n$). 여기서 $n$은 원 위의 위치의 수, $a$는 빨간 점의 수, $b$는 파란 점의 수이다.

둘째 줄에는 빨간 점의 위치를 나타내는 $a$개의 정수 $x_1 < x_2 < \dots < x_a$가 증가하는 순서로 주어진다.

셋째 줄에는 파란 점의 위치를 나타내는 $b$개의 정수 $y_1 < y_2 < \dots < y_b$가 증가하는 순서로 주어진다.

모든 $x_i$와 $y_j$는 $0 \le x_i, y_j \le n - 1$을 만족하고, 이들은 모두 서로 다르다. 같은 줄의 정수는 공백 하나로 구분된다.

표준 출력으로 답을 출력한다. 각 테스트 케이스마다 짝지어진 빨간 점과 파란 점 사이의 더 짧은 호 길이의 합의 최솟값을 한 줄에 출력한다.