CF785B - Anton and Classes

安东喜欢下棋。他还喜欢编程。难怪他决定参加国际象棋课和编程课。

安东有 n 种上国际象棋课的方案，第 i 种方案由一段时间 (l1, i, r1, i) 给出。他还有 m 种上编程课的方案，第 i 种方案由一段时间 (l2, i, r2, i) 给出。

安东需要从 n 个可能的时间段中选择一个上国际象棋课的时间段，以及从 m 个可能的时间段中选择一个上编程课的时间段。他想在课间休息一下，因此他想从所有可能的时间段中选择一个时间段之间的距离最大的时间段。

周期 (l1, r1) 和 (l2, r2) 之间的距离是第一个周期中的点与第二个周期中的点之间的最小可能距离，即最小可能的 |i - j|，其中 l1 ≤i ≤r1 且 l2 ≤j ≤r2。具体来说，当周期相交时，它们之间的距离为 0。

Anton 想知道在最佳情况下他在课间休息的时间。帮助 Anton 找到这个数字！

输入

输入的第一行包含一个整数 n (1 ≤n ≤200 000) — Anton 可以参加国际象棋课程的时间段数。

输入的以下 n 行中的每一行包含两个整数 l1, i 和 r1, i (1 ≤ l1, i ≤ r1, i ≤ 109) — 安东可以参加国际象棋课程的时间段的第 i 个变量。

输入的以下行包含一个整数 m (1 ≤ m ≤ 200 000) — 安东可以参加编程课程的时间段数。

输入的以下 m 行中的每一行包含两个整数 l2, i 和 r2, i (1 ≤ l2, i ≤ r2, i ≤ 109) — 安东可以参加编程课程的时间段的第 i 个变量。

输出

输出一个整数 — 时间段之间的最大可能距离。

理解成2个数组，就是每个数组右端点的最小值，跟左端点的最大值求出来。

B的最大左-A的最小右

A的最大左-B的最小右。

比较这两个值，求较大值即可。