← 返回题目列表

Codeforces · 785/B

B. 安东和班级

中文机器翻译题面 查看原题

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

Anton 在参加国际象棋课时有 n 个变体,第 i 个变体由一段时间 (l1, i, r1, i) 给出。当他参加编程课时,他也有 m 个变体,第 i 个变体由一段时间 (l2, i, r2, i) 给出。

Anton 需要准确地选择他将参加国际象棋课程的 n 个可能的时间段之一以及他将参加编程课程的 m 个可能的时间段之一。他希望在课间休息,因此他想从所有可能的时段中选择时段之间距离最大的时段。

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

安东想知道在最好的情况下他在课间休息多长时间。帮助安东找到这个号码!

输入

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

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

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

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

输出

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

示例

输入 #1

3
1 5
2 6
2 3
2
2 4
6 8

输出 #1

3

输入 #2

3
1 5
2 6
3 7
2
2 4
1 4

输出 #2

0

注意

在第一个样本中,Anton 可以在 (2, 3) 期间参加国际象棋课程,并在 (6, 8) 期间参加编程课程。不难看出,在这种情况下,周期之间的距离将等于 3。

在第二个样本中,如果他选择任何一对句点,它们就会相交。所以答案是0。