Soju

Two rival companies, IC and PC, share the soju market in Korea. Soju is a well-known Korean distilled liquor that goes well with Korean cuisine. The two companies have an agreement about where their branches may sit: every IC branch must lie to the west of every PC branch. In other words, all IC branches have a smaller $x$-coordinate than any PC branch.

At the beginning of each month the companies check whether the agreement still holds. To do so they want the distance of the closest pair of branches, one from each company. The distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is defined as $|x_1 - x_2| + |y_1 - y_2|$.

Figure 1. Blue disks are IC branches and red squares are PC branches. The distance of a closest pair between them is 5.

You are given two sets of points, $I$ and $P$, representing the branches of IC and PC respectively. Every point in $I$ has a smaller $x$-coordinate than any point in $P$. Write a program that computes the minimum distance over all pairs $(i, p)$ with $i \in I$ and $p \in P$.

Your program reads from standard input. The first line contains the number of test cases $T$. The first line of each test case contains an integer $n$, the number of points in $I$ ($1 \le n \le 100000$). Each of the following $n$ lines contains the $x$-coordinate and $y$-coordinate of one point of $I$. The next line contains an integer $m$, the number of points in $P$ ($1 \le m \le 100000$). Each of the following $m$ lines contains the $x$-coordinate and $y$-coordinate of one point of $P$. All coordinates are integers between $-10^6$ and $10^6$ inclusive. Note that every point of $I$ has a smaller $x$-coordinate than any point of $P$.

Your program writes to standard output. Print exactly one line for each test case. Each line contains a single integer, the distance of a closest pair of points, one from $I$ and one from $P$.