C. Абракадабра
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Поликарп исследует строку, которую он называет абракадабра. Эта строка строится по следующему алгоритму:

  • На первом шаге строка состоит из одного символа «a».
  • На k-oм шаге Поликарп соединяет две копии строки, полученной на k - 1 шаге, а между ними вставляет k-й символ алфавита. Поликарп использует алфавит, состоящий из строчных латинских букв и цифр (всего 36 символов). Символы алфавита нумеруются следующим образом: 1-й символ — «a», 2-й — «b», ..., 26-й — «z», 27-й — «0», 28-й — «1», ..., 36-й — «9».

Рассмотрим алгоритм подробнее. На втором шаге Поликарп соединит две строки «a», вставив посередине символ «b», и получит строку «aba». На третьем шаге получится строка «abacaba», а на четвертом — «abacabadabacaba». Таким образом, строка, полученная на k-ом шаге, будет состоять из 2k - 1 символов.

Поликарп записал строку, полученную после 30 шагов данного алгоритма, и выбрал из нее две непустые подстроки. Ваша задача состоит в том, чтобы найти длину наибольшей общей подстроки двух подстрок, выбранных Поликарпом.

Подстрокой s[i... j] (1 ≤ i ≤ j ≤ |s|) строки s = s1s2... s|s| называется строка, равная sisi + 1... sj. Например, подстрока s[2...4] строки s = «abacaba» равна «bac». Сама строка является своей подстрокой.

Наибольшей общей подстрокой двух строк s и t называется самая длинная строка, которая является подстрокой как s, так и t. Например, наибольшей общей подстрокой «contest» и «systemtesting» является строка «test». Общих подстрок наибольшей длины может существовать несколько.

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

Входные данные состоят из одной строки, которая содержит четыре целых числа l1, r1, l2, r2 (1 ≤ li ≤ ri ≤ 109, i = 1, 2). Числа разделены единичными пробелами. Значения li и ri задают индексы первого и последнего символов i-ой выбранной подстроки, соответственно (i = 1, 2). Символы строки абракадабра нумеруются с 1.

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

Выведите единственное число — длину наибольшей общей подстроки заданных подстрок. Если общих подстрок нет, выведите 0.

Примеры
Входные данные
3 6 1 4
Выходные данные
2
Входные данные
1 1 4 4
Выходные данные
0
Примечание

В первом тесте первая подстрока равна «acab», вторая — «abac». У этих двух подстрок есть две наибольшие общие подстроки «ac» и «ab», нас же интересует только их длина — 2.

Во втором тесте первая подстрока равна «a», вторая — «c». У этих двух подстрок нет ни одного общего символа, поэтому длина наибольшей общей подстроки — 0.