성

ICPCIA라는 나라에는 "성들의 강"이라고 불리는 강이 있다. 먼 옛날 ICPCIA는 이 강을 경계로 웨스테리아(Westeria)와 이스타니아(Eastania)라는 두 왕국으로 나뉘어 있었다. 강은 북서쪽에서 남동쪽 방향으로 흐르며, 두 왕국은 각자의 강변을 따라 방어와 공격을 위한 성을 경쟁적으로 지었다.

각 강변의 성들은 $x$좌표가 엄격하게 증가하고 $y$좌표가 엄격하게 감소하도록 배치되어 있다. 즉, 웨스테리아의 성을 $S = \{s_1, s_2, \dots, s_n\}$, 이스타니아의 성을 $T = \{t_1, t_2, \dots, t_m\}$이라 하고 $s_i$의 좌표를 $(x_i, y_i)$, $t_i$의 좌표를 $(u_i, v_i)$라 하면, $i < j$일 때 항상 $x_i < x_j$이고 $y_i > y_j$이며, 마찬가지로 $u_i < u_j$이고 $v_i > v_j$이다.

ICPCIA 문화관광부는 서로 다른 강변에 있는 성 두 개를 잇는 아름다운 다리를 놓으려 한다. 다리는 I자 모양(수평 또는 수직 선분 하나)이거나 L자 모양(수평 선분 하나와 수직 선분 하나)이므로, 그 길이는 두 성 사이의 맨해튼 거리와 같다. 다리를 가능한 한 짧게 만들기 위해, 서로 다른 강변에 있는 가장 가까운 성 쌍을 찾으려 한다. 성 $s_i$와 $t_j$ 사이의 거리는 $|x_i - u_j| + |y_i - v_j|$로 계산한다.

두 성 집합의 정보가 주어질 때, 서로 다른 강변에 있는 가장 가까운 두 성 사이의 거리를 구하는 프로그램을 작성하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스는 세 줄로 이루어진다. 첫째 줄에는 두 정수 $n$과 $m$이 주어지며($1 \le n, m \le 200000$), 각각 서쪽 강변과 동쪽 강변에 있는 성의 개수이다. 둘째 줄에는 $2n$개의 정수 $x_1\ y_1\ x_2\ y_2\ \dots\ x_n\ y_n$이 주어지는데, $(x_i, y_i)$는 서쪽 강변의 $i$번째 성이고 $i < j$일 때 $x_i < x_j$, $y_i > y_j$이다. 셋째 줄에는 $2m$개의 정수 $u_1\ v_1\ u_2\ v_2\ \dots\ u_m\ v_m$이 주어지는데, $(u_i, v_i)$는 동쪽 강변의 $i$번째 성이고 $i < j$일 때 $u_i < u_j$, $v_i > v_j$이다.

두 성 집합을 분리하는, $x$에 대해 증가하고 $y$에 대해 감소하는 단조 경로가 항상 존재한다고 가정해도 된다. 모든 좌표는 $-10^9$ 이상 $10^9$ 이하의 정수이다.

각 테스트 케이스마다 서로 다른 강변에 있는 가장 가까운 두 성 사이의 거리를 한 줄에 하나씩 출력한다.