Tracy the farmer is looking out at her field of cows. She has ~N~ brown cows and ~M~ black and white cows on a field of size ~10^9~ by ~10^9~. Today, Tracy wants to pick one brown cow and one black and white cow to milk. Her cows are very special - the lesser the distance she has to travel between them, the better the milk they produce will be. As such, she wants to pick two cows such that the distance she has to travel between them is as little as possible.
Tracy also has a very special tractor. Her tractor allows her to magically teleport between either two rows or two columns. She can choose which to teleport between, and she can only use this tractor once.
Given the locations of Tracy's cows, can you output the distance between the two cows she should milk to have the best possible milk?
The first line will contain two integers, ~N (1 \leq N \leq 10^5)~ and ~M (1 \leq M \leq 10^5)~, the number of brown cows and the number of black and white cows Tracy has, respectively.
The next ~N~ lines will contain two integers each, ~x_i (1 \leq x_i \leq 10^9)~ and ~y_i (1 \leq y_i \leq 10^9)~, the ~x~ and ~y~ position of one brown cow on the field.
The next ~M~ lines will contain two integers each, ~x_i (1 \leq x_i \leq 10^9)~ and ~y_i (1 \leq y_i \leq 10^9)~, the ~x~ and ~y~ position of one black and white cow on the field.
Output a single integer, the distance between the two cows Tracy should milk to have the best possible milk.
Subtask 1 [30%]
~N \leq 10^2~
~M \leq 10^2~
Subtask 2 [70%]
No additional constraints.
Sample Input 1
2 1 4 4 1000 2 1 1
Sample Output 1
Explanation for Sample 1
Tracy chooses to move between the second brown cow and first black and white cow. The x-distance between these two cows is ~996~ and the y-distance between these two cows is ~1~. Since she can use her tractor, she uses it to teleport between the two columns. Thus, she only has to travel a distance of ~1~ between the rows, making this the minimum distance.
Sample Input 2
2 2 1 1 1 2 4 4 5 5
Sample Output 2