Антону нравятся шахматы. А еще ему нравится программирование. Неудивительно, что он решил посещать занятия по шахматам и по программированию.
У Антона есть 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.
Антону интересно, сколько времени он сможет отдохнуть между занятиями в лучшем случае. Помогите ему найти это число!
Примечание
В первом примере Антон может заниматься шахматами в отрезок времени (2, 3), а программированием — в отрезок времени (6, 8). Нетрудно заметить, что в этом случае расстояние между отрезками равно 3.
Во втором примере какую бы Антон пару отрезков не выбрал, они будут пересекаться. Поэтому ответ — 0.