Polycarpus 分析了一个名为 abracadabra 的字符串。该字符串是使用以下算法构造的:
- 第一步,字符串由单个字符“a”组成。
- 在第 k 个步骤中,Polycarpus 连接在第 (k - 1) 步骤中获得的字符串的两个副本,同时在它们之间插入字母表的第 k 个字符。 Polycarpus 使用由小写拉丁字母和数字组成的字母表(总共 36 个字符)。字母字符的编号如下:第 1 个字符是“a”,第 2 个字符是“b”,...,第 26 个字符是“z”,第 27 个字符是“0”,第 28 个字符是“1”,...,第 36 个字符是“9”。
让我们仔细看看该算法。第二步,Polycarpus 将连接两个字符串“a”并在它们之间插入字符“b”,从而生成“aba”字符串。第三步将其转换为“abacaba”,第四步将其转换为“abacabadabacaba”。因此,第 k 步构建的字符串将由 2k - 1 个字符组成。
Polycarpus 写下了给定算法 30 步后得到的字符串,并选择了其中的两个非空子字符串。你的任务是找出 Polycarpus 选择的两个子串中最长公共子串的长度。
字符串 s = s1s2... s|s| 的子串 s[i... j] (1 ≤ i ≤ j ≤ |s|)是一个字符串 sisi + 1... sj。例如,字符串 s = "abacaba" 的子字符串 s[2...4] 等于 "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)。字符串 abracadabra 的字符从 1 开始编号。
输出
打印单个数字 — 给定字符串的最长公共子字符串的长度。如果没有公共子串,则打印0。
示例
输入 #1
3 6 1 4
输出 #1
2
输入 #2
1 1 4 4
输出 #2
0
注意
在第一个示例中,第一个子字符串是“acab”,第二个子字符串是“abac”。这两个子串有两个最长的公共子串“ac”和“ab”,但我们只对它们的长度感兴趣——2。
在第二个示例中,第一个子字符串是“a”,第二个子字符串是“c”。这两个子串没有任何公共字符,因此它们的最长公共子串的长度为0。