E. Lazy Fouad
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Fouad has just moved to a new city that contains $$$n$$$ houses and $$$m$$$ schools. In this problem, the city is represented as an infinite $$$2D$$$ plane, with both the schools and the houses represented as lattice points$$$^\dagger$$$ on this plane. Being a lazy person, Fouad wants to choose exactly one house and exactly one school in such a way that minimizes the Manhattan distance$$$^\ddagger$$$ between them. Please help him calculate the minimum Manhattan distance between any of the $$$n$$$ houses and any of the $$$m$$$ schools.

$$$^\dagger$$$ A lattice point is a point $$$p = (x, y)$$$ with integer coordinates $$$x$$$ and $$$y$$$.

$$$^\ddagger$$$ The Manhattan distance between two points $$$p_1 = (x_1, y_1)$$$ and $$$p_2 = (x_2, y_2)$$$ is equal to: $$$$$$d(p_1, p_2) = |x_1 - x_2| + |y_1 - y_2|$$$$$$

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^3)$$$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ $$$(1 \le n, m \le 2 \cdot 10^5)$$$ — the number of houses and schools respectively.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ $$$(1 \le a_i, b_i \le 10^{18})$$$ — the coordinates of the $$$i$$$-th house.

Rhe $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$c_i$$$ and $$$d_i$$$ $$$(1 \le c_i, d_i \le 10^{18})$$$ — the coordinates of the $$$i$$$-th school.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the minimum Manhattan distance between any of the $$$n$$$ houses and any of the $$$m$$$ schools.

Example
Input
1
3 2
4 4
1 1
3 4
2 2
1 5
Output
2
Note

Explanation of the example:

The above figure illustrates the first test case in the example, where $$$H_i$$$ denotes the $$$i$$$-th house and $$$S_i$$$ denotes the $$$i$$$-th school.

There are $$$6$$$ possible pairs for Fouad to choose from:

  1. $$$d(H_1, S_1) = |4 - 2| + |4 - 2| = 4$$$.
  2. $$$d(H_1, S_2) = |4 - 1| + |4 - 5| = 4$$$.
  3. $$$d(H_2, S_1) = |1 - 2| + |1 - 2| = 2$$$.
  4. $$$d(H_2, S_2) = |1 - 1| + |1 - 5| = 4$$$.
  5. $$$d(H_3, S_1) = |3 - 2| + |4 - 2| = 3$$$.
  6. $$$d(H_3, S_2) = |3 - 1| + |4 - 5| = 3$$$.

Therefore, the answer is $$$\min(\{4, 4, 2, 4, 3, 3\}) = 2$$$.