Since Hasan was too lazy to write a story for this problem, so we'll say it clear:
Given $N$ Horizontal lines and $M$ Vertical lines, you need to find the Longest plus sign formed by the intersection of exactly one vertical line with one horizontal line.
The length of the plus sign is defined by the length of its shortest side (the minimum length of the segments $[ C, L 1 ]$, $[ C, L 2 ]$, $[ C, L 3 ]$, $[ C, L 4 ]$.
First line of input will be $T$ number of test cases.
Each test case will start with two numbers, $N$ and $M$ the number of Horizontal lines and the number of vertical lines.
Next $N$ lines contain three space separated numbers, $X_1$, $X_2$ and $Y$, the starting and ending $X$ coordinates of the horizontal line, and It's $Y$ coordinate.
Next $M$ lines contain three space separated numbers, $Y_1$, $Y_2$ and $X$, the starting and ending $Y$ coordinates of the horizontal line, and It's $X$ coordinate.
$1 <= N, M <= 10^5$
$1 <= c o o r d i n a t e s <= 10^5$ and all the coordinates are integers.
For each test case print one line, containing the length of the longest plus sign.
## Input
First line of input will be $T$ number of test cases.Each test case will start with two numbers, $N$ and $M$ the number of Horizontal lines and the number of vertical lines.Next $N$ lines contain three space separated numbers, $X_1$, $X_2$ and $Y$, the starting and ending $X$ coordinates of the horizontal line, and It's $Y$ coordinate.Next $M$ lines contain three space separated numbers, $Y_1$, $Y_2$ and $X$, the starting and ending $Y$ coordinates of the horizontal line, and It's $X$ coordinate.$1 <= N, M <= 10^5$$1 <= c o o r d i n a t e s <= 10^5$ and all the coordinates are integers.
## Output
For each test case print one line, containing the length of the longest plus sign.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ \mathcal{H} = \{ (x_{1,i}, x_{2,i}, y_i) \mid i \in \{1, \dots, N\} \} $ be the set of horizontal line segments, where $ x_{1,i} \le x_{2,i} $ and $ y_i $ is the constant $ y $-coordinate.
- Let $ \mathcal{V} = \{ (y_{1,j}, y_{2,j}, x_j) \mid j \in \{1, \dots, M\} \} $ be the set of vertical line segments, where $ y_{1,j} \le y_{2,j} $ and $ x_j $ is the constant $ x $-coordinate.
**Constraints**
1. $ 1 \le T \le \text{unknown} $ (not bounded in input)
2. $ 1 \le N, M \le 10^5 $
3. All coordinates are integers in $ [1, 10^5] $
**Objective**
For each test case, find the maximum value of:
$$
\min\left( \min(x_j - x_{1,i}, x_{2,i} - x_j), \min(y_i - y_{1,j}, y_{2,j} - y_i) \right)
$$
over all pairs $ ((x_{1,i}, x_{2,i}, y_i), (y_{1,j}, y_{2,j}, x_j)) \in \mathcal{H} \times \mathcal{V} $ such that:
- $ x_{1,i} \le x_j \le x_{2,i} $ (vertical line intersects horizontal line in $ x $),
- $ y_{1,j} \le y_i \le y_{2,j} $ (horizontal line intersects vertical line in $ y $).
Output the maximum such value across all valid intersections.