Castles

The country ICPCIA has a river called the "River of Castles". Long ago, ICPCIA was split into two kingdoms, Westeria and Eastania, divided by this river, which flows from the northwest to the southeast. Both kingdoms competitively built many castles for defense and attack along their own bank of the river.

The castles on each bank are arranged so that their $x$-coordinates strictly increase while their $y$-coordinates strictly decrease. Formally, let $S = \{s_1, s_2, \dots, s_n\}$ be the castles of Westeria and $T = \{t_1, t_2, \dots, t_m\}$ the castles of Eastania. If $(x_i, y_i)$ is the coordinate of $s_i$ and $(u_i, v_i)$ is the coordinate of $t_i$, then $x_i < x_j$ and $y_i > y_j$ whenever $i < j$, and likewise $u_i < u_j$ and $v_i > v_j$ whenever $i < j$.

The Ministry of Culture and Tourism of ICPCIA now wants to build a beautiful bridge that connects one castle on each bank. The bridge is either I-shaped (a single horizontal or vertical segment) or L-shaped (one horizontal segment plus one vertical segment), so its length equals the Manhattan distance between the two castles it connects. To make the bridge as short as possible, they look for the closest pair of castles on opposite banks. The distance between castles $s_i$ and $t_j$ is $|x_i - u_j| + |y_i - v_j|$.

Given the two sets of castles, write a program that finds the distance between the closest pair of castles on opposite banks.

The first line contains the number of test cases $T$.

Each test case consists of three lines. The first line contains two integers $n$ and $m$ ($1 \le n, m \le 200000$): the number of castles on the west bank and on the east bank, respectively. The second line contains $2n$ integers $x_1\ y_1\ x_2\ y_2\ \dots\ x_n\ y_n$, where $(x_i, y_i)$ is the $i$-th west-bank castle and $x_i < x_j$, $y_i > y_j$ whenever $i < j$. The third line contains $2m$ integers $u_1\ v_1\ u_2\ v_2\ \dots\ u_m\ v_m$, where $(u_i, v_i)$ is the $i$-th east-bank castle and $u_i < u_j$, $v_i > v_j$ whenever $i < j$.

You may assume there always exists an $x$-monotone increasing and $y$-monotone decreasing path that separates the two sets of castles. All coordinates are integers between $-10^9$ and $10^9$, inclusive.

For each test case, print a single line containing the distance between the closest pair of castles on opposite banks.