Abracadabra

题意翻译

## 题目描述 $Ploycarpus$分析了一个名为$abracadabra$的字符串，该字符串是用以下的方法构造的： - 第一步时字符串仅包含单个字符$a$ - 在第$k$步中，我们将第$k-1$步中得到的字符串复制两次，并在这两个串中间插入字母表中的第$k$个字符。$Ploycarpus$所使用的字母表包括小写的拉丁字母和阿拉伯数字，总共$36$个，分别为：第$1$个是$a$，第$2$个是$b$，...，第$26$个是$z$，第$27$个是$0$，第$28$个是$1$，...，第$36$个是$9$。 我们来仔细看一看字符串的构造过程。在第$2$步中，$Ploycarpus$将会把字串"a"复制两次，将字符"b"插在中间，得到字串$aba$。第$3$步会变成"abacaba"，第$4$步会变成"abacabadabacaba"。因此，在第$k$步中，字符串会包括$2^k-1$个字符。 $Polycarpus$写下了用以上的方法在$30$步之后得到的字符串然后选择了两个其中的非空子串。你要做的任务是找到两个$Polycarpus$选择的字串的最长公共子串。 一个字符串$s=s_1s_2...s_{|s|}$的子串$s[i...j](1<=i<=j<=|s|$)即为$s_is_{i+1}...s_j$举个例子，字符串$s=$"abacaba的子串$s[2...4]$就是$bac$。字符串本身可以是它的子串。 最长公共子串即为两个字符串 都包含的最长的子串。比如，"contest"和"test"最长公共子串为"test"。可能有多个最长公共子串（不同组成同长度） ## 输入输出格式 ### 输入格式 输入包括一行，四个整数$l_1$，$r_1$，$l_2$，$r_2(1<=l_i<=r_i<=10^9,i=1,2)$ 数字之间有空格，表示第$i$个字符串（只有两个，上面范围写了）的起始和结束位置。字符串中第一个字符的位置视为$1$ ### 输出格式 输出一个数字，最长公共子串的长度，如果没有，请输出$0$。 注：$Ploycarpus$似乎是人名

题目描述

Polycarpus analyzes a string called abracadabra. This string is constructed using the following algorithm: - On the first step the string consists of a single character "a". - On the $ k $ -th step Polycarpus concatenates two copies of the string obtained on the $ (k-1) $ -th step, while inserting the $ k $ -th character of the alphabet between them. Polycarpus uses the alphabet that consists of lowercase Latin letters and digits (a total of 36 characters). The alphabet characters are numbered like this: the 1-st character is "a", the 2-nd — "b", ..., the 26-th — "z", the 27-th — "0", the 28-th — "1", ..., the 36-th — "9". Let's have a closer look at the algorithm. On the second step Polycarpus will concatenate two strings "a" and insert the character "b" between them, resulting in "aba" string. The third step will transform it into "abacaba", and the fourth one - into "abacabadabacaba". Thus, the string constructed on the $ k $ -th step will consist of $ 2^{k}-1 $ characters. Polycarpus wrote down the string he got after 30 steps of the given algorithm and chose two non-empty substrings of it. Your task is to find the length of the longest common substring of the two substrings selected by Polycarpus. A substring $ s[i...\ j] $ ( $ 1<=i<=j<=|s| $ ) of string $ s $ = $ s_{1}s_{2}...\ s_{|s|} $ is a string $ s_{i}s_{i+1}...\ s_{j} $ . For example, substring $ s[2...4] $ of string $ s $ = "abacaba" equals "bac". The string is its own substring. The longest common substring of two strings $ s $ and $ t $ is the longest string that is a substring of both $ s $ and $ t $ . For example, the longest common substring of "contest" and "systemtesting" is string "test". There can be several common substrings of maximum length.

输入输出格式

输入格式

The input consists of a single line containing four integers $ l_{1} $ , $ r_{1} $ , $ l_{2} $ , $ r_{2} $ ( $ 1<=l_{i}<=r_{i}<=10^{9} $ , $ i=1,2 $ ). The numbers are separated by single spaces. $ l_{i} $ and $ r_{i} $ give the indices of the first and the last characters of the $ i $ -th chosen substring, correspondingly ( $ i=1,2 $ ). The characters of string abracadabra are numbered starting from $ 1 $ .

输出格式

Print a single number — the length of the longest common substring of the given strings. If there are no common substrings, print 0.

输入输出样例

输入样例 #1

3 6 1 4

输出样例 #1

2

输入样例 #2

1 1 4 4

输出样例 #2

0

说明

In the first sample the first substring is "acab", the second one is "abac". These two substrings have two longest common substrings "ac" and "ab", but we are only interested in their length — 2. In the second sample the first substring is "a", the second one is "c". These two substrings don't have any common characters, so the length of their longest common substring is 0.