题目描述

Anton很喜欢下棋，同时又很喜欢编程。难怪，他会想去参加棋艺班和编程班！

一共有n个棋艺班，m个编程班。第i个棋艺班的时间用$(l_{1,i},r_{1,i})$表示，第i个编程班的时间用$(l_{2,i},r_{2,i})$表示。

Anton需要在全部的棋艺班和编程班中间恰好各选一个。他想要在两个班之间有休息的时间，所以对于所有可能的选择，他希望两个时间段的距离（即他的休息时间）最大。

两个时间段$(l_1,r_1)$和$(l_2,r_2)$的距离是这样定义的：对于$l_1\le i\le r_1$，$l_2\le j\le r_2$，距离就是$|i-j|$的最小值。如果两个时间段相交，那么他们的距离当然就是$0$。

Anton很想知道，他的休息时间最大是多少。帮帮他解决这个问题吧！

输入格式

第一行一个整数n。

第2~n+1行，每行两个数$l_{1,i}$和$r_{1,i}$。

第n+2行一个整数m。

接下来mmm行，每行两个数$l_{2,i}$和$r_{2,i}$。

保证$1<=n,m<=200000$。对于输入中的所有$x$，保证$1<=x<=10^9$。

输出格式

一个整数，表示Anton的最大休息时间。

样例

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

3

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

0