B. Антон и занятия
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Антону нравятся шахматы. А еще ему нравится программирование. Неудивительно, что он решил посещать занятия по шахматам и по программированию.

У Антона есть 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.

Антону интересно, сколько времени он сможет отдохнуть между занятиями в лучшем случае. Помогите ему найти это число!

Входные данные

В первой строке входных данных записано целое число n (1 ≤ n ≤ 200 000) — количество отрезков времени, когда Антон может заниматься шахматами.

В каждой из следующих 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-й отрезок времени, когда Антон может заниматься программированием.

Выходные данные

Выведите одно целое число — максимально возможное расстояние между отрезками.

Примеры
Входные данные
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
Примечание

В первом примере Антон может заниматься шахматами в отрезок времени (2, 3), а программированием — в отрезок времени (6, 8). Нетрудно заметить, что в этом случае расстояние между отрезками равно 3.

Во втором примере какую бы Антон пару отрезков не выбрал, они будут пересекаться. Поэтому ответ — 0.