题目描述

泽泽不但喜欢看拳击比赛，而且也喜欢下围棋和编程，所以他决定参加围棋和编程兴趣班。

围棋兴趣班共有 $n$ 个时间段选择，第 $i$ 个时间段排在（$L_i\sim R_i$）。编程兴趣班也有 $m$ 个时间段选择，第 $i$ 个时间段排在（$A_i\sim B_i$）。他必须要选择一个围棋班和一个编程班的时间段，但他希望选的这两个班中间的休息时间越长越好。

例如，他选了这两个时间段（$L_1\sim R_1$）和（$A_1\sim B_1$），假设（$L_1\sim R_1$）这节课在前面，（$A_1\sim B_1$）这节课在后面，那么，泽泽在中间休息的时间是 $A_1-R_1$。特别说明，当两节课上课时间有冲突，泽泽在中间休息时间为 $0$。

泽泽想算一算他所选的两节兴趣课之间，能休息的时间最长是多少？请你帮助泽泽找一找，算一算。

输入

第一行输入一个整数 $n$，表示围棋兴趣班可选择的时间段。

下列 $n$ 行，每行都输入两个整数 $L_i$ 和 $R_i$，分别表示泽泽参加第 $i$ 个围棋班的起止时间。

下面一行输入的一个整数 $m$，表示编程兴趣班可选择的时间段。

下列 $m$ 行，每行都输入两个整数 $A_i$ 和 $B_i$，分别表示泽泽参加第 $i$ 个编程班的起止时间。

输出

输出一个整数，表示两个时间段之间的最长休息时间（如果所有时间段都有冲突，则输出 $0$）。

样例

样例输入

样例输入 $1$

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

样例输入 $2$

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

样例输出

样例输出 $1$

3

样例输出 $2$

0

样例解释

样例 $1$，泽泽可以在这段时间（$2,3$）参加围棋班，并在另一段时间（$6,8$）参加编程班。不难算出，在这种情况下，他中间休息的时间是最长的 $6-3=3$。

样例 $2$，他选择任何一段时间，两个兴趣班上课的时间都有冲突，所以答案是 $0$。

数据范围

对于 $60\%$ 的数据，保证 $1\le n\le10000,1\le m\le10000$

对于 $100\%$的数据，保证 $1\le n\le200000,1\le m\le200000,1\le L_i\le R_i\le1000000000,1\le A_i\le B_i\le1000000000$

---

错误信息

========[test8.out]=========
Expected						      |	Yours
116							      |	120
==============================
time_space_table:
/sample.in:AC mem=2340k time=4ms
/test0.in:AC mem=2340k time=9ms
/test1.in:AC mem=2340k time=8ms
/test2.in:AC mem=2340k time=2ms
/test3.in:AC mem=2340k time=0ms
/test4.in:AC mem=2340k time=2ms
/test5.in:AC mem=2340k time=34ms
/test6.in:AC mem=2340k time=22ms
/test7.in:AC mem=2340k time=1ms
/test8.in:WA mem=2340k time=2ms
/test9.in:AC mem=2340k time=1ms

错误代码

# include <bits/stdc++.h>

# define old_six \
	ios::sync_with_stdio (0);\
	\
	cin.tie (0);\
	\
	cout.tie (0);

# define ffor(i,name) \
	for (auto i = name.begin (); i != name.end (); i ++)

# define iter(type) \
	type :: iterator

# define reg register

# define inl inline

using namespace std;

typedef long long ll;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

int n, m, x, y, maxl, maxa, minr = 1e9, minb = 1e9;

int main () {

	old_six

	cin >> n;

	while (n --)
		cin >> x >> y, maxl = max (maxl, x), minr = min (minr, y);

	cin >> m;

	while (m --)
		cin >> x >> y, maxa = max (maxa, x), minb = min (minb, y);
//	cout << maxl << ' ' << maxa << '\n' << minb << ' ' << minr << '\n';
	cout << max ({0, maxl - minb, maxa - minr});

	return 0;

}