9016번 - Castles 다국어채점 준비 중

The country ICPCIA has a river called “river of castles”. In the past, ICPCIA was divided into two kingdoms called Westeria and Eastania. Two kingdoms were separated by the river which runs in the direction from northwest to southeast. Both kingdoms had competitively built many castles for defense and attack along the riverside. All castles of each side of the river are located with an x-monotone increasing and y-monotone decreasing feature. In other words, let S = {s₁, s₂, … , s_n} be the castles of Westeria and T = {t₁, t₂, … , t_m} the castles of Eastania. Let (x_i, y_i) (resp. (u_i, v_i)) be the coordinates of s_i (resp. t_i). Then x_i < x_j and y_i > y_j if i < j. Also, u_i < u_j and v_i > v_j if i < j.

Now, the Ministry of Culture and Tourism of ICPCIA decided to build a beautiful bridge connecting two castles on the opposite side of the river. The bridge will be an I-shape(a horizontal segment or a vertical segment) or an L-shape(both of a horizontal segment and a vertical segment). They want to find the location of the bridge such that its length is as small as possible. So, they try to find the closest pair of castles on the opposite side. The distance between two castles s_i and t_j is computed by |x_i - u_j| + |y_i - v_j|.

Given the information of two sets of castles, write a program to find the distance between the closest castles on the opposite side of the river.

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case consists of three lines. The first line of each test case contains two integers. The first integer, n, is the number of castles in the west side of the river, and the integer, m, is the number of castles in the east side of it, where 1 ≤ n, m ≤ 200,000. The second line of each test case contains 2n integers x₁, y₁, x₂, y₂, …, x_n, y_n , where (x_i, y_i) is the coordinate of the i-th castle in the west side of the river and x_i < x_j and y_i > y_j if i < j. The last line of each test case contains 2m integers u₁, v₁, u₂, v₂, …, u_m, v_m , where (u_i, v_i) is the coordinate of the i-th castle in the east side of the river and u_i < u_j and v_i > v_j if i < j. You may assume that there exists an x-monotone increasing and y-monotone decreasing path which separates two sets of castles. All integers representing the coordinates of castles are between -10⁹ and 10⁹, inclusive.

Your program is to write to standard output. Print exactly one line for each test case. The line should contain the distance between the closest castles on the opposite side of the river.