C. Абракадабра

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Поликарпус $abracadabra$ гэж нэрлэгдэх тэмдэгт мөрийг шинжлэдэг. Энэ тэмдэгт мөр нь дараах алгоритмыг ашиглан үүсгэгддэг:

  • Эхний алхам дээр тэмдэгт мөр нэг тэмдэгт "$a$"-с бүтнэ.
  • $k$-р алхам дээр Поликарпус $(k - 1)$-р алхамд гарсан тэмдэгт мөрийн хоёр хуулбарыг хооронд нь цагаан толгойн $k$-р үсгийг голд нь оруулж залгадаг. Поликарпус Латин цагаан толгойн үсгүүд болон цифрүүдээс бүрдэх цагаан толгойг ашигладаг (нийт 36 тэмдэгт). Цагаан толгойн тэмдэгтүүд дараах байдлаар дугаарлагдана: 1-р тэмдэгт нь "$a$", 2-р тэмдэгт нь "$b$", ..., 26-р тэмдэгт нь "$z$", 27-р тэмдэгт нь "$0$", 28-р тэмдэгт нь "$1$", ..., 36-р тэмдэгт нь "$9$".

Алгоритмыг илүү ойроос харцгаая. Хоёр дахь алхамд Поликарпус хоёр "$a$" тэмдэгт мөрүүдийг залгах ба голд нь "$b$" тэмдгийг нэмэх ба үр дүнд нь "$aba$" тэмдэгт мөр гарна. Гуравдугаар алхамд үүнийг "$abacaba$" болгох ба дөрөвдүгээр алхамд "$abacabadabacaba$" болгоно. Ингээд $k$-р алхамд үүссэн тэмдэгт мөр нь $2^{k} - 1$ тэмдэгтээс бүрдэнэ.

Поликарпус өгөгдсөн алгоритмын 30 алхмын дараах тэмдэгт мөрийг бичсэн ба хоосон биш хоёр дэд тэмдэгт мөр сонгосон. Таны ажил бол Поликарпусийн сонгосон хоёр дэд тэмдэгт мөрүүдийн хамгийн урт ерөнхий дэд тэмдэгт мөрийн уртыг олох юм.

$s$ = $s_{1}s_{2}... s_{|s|}$ тэмдэгт мөрийн $s[i... j]$ ($1 ≤ i ≤ j ≤ |s|$) дэд тэмдэгт мөр нь $s_{i}s_{i + 1}... s_{j}$ тэмдэгт мөр байна. Жишээлбэл $s$ = "$abacaba$" тэмдэгт мөрийн $s[2...4]$ дэд тэмдэгт мөр нь "$bac$" байна. Тэмдэгт мөр нь өөрийнхөө дэд тэмдэгт мөр байна.

$s$ ба $t$ хоёр дэд тэмдэгт мөрүүдийн хамгийн урт ерөнхий дэд тэмдэгт мөр гэдэг нь $s$ ба $t$ хоёрын хоёулангийнх нь дэд тэмдэгт мөр байх хамгийн урт тэмдэгт мөр юм. Жишээлбэл "$contest$" ба "$systemtesting$" хоёрын хамгийн урт ерөнхий дэд тэмдэгт мөр нь "$test$" байна. Хамгийн урт урттай хэд хэдэн ерөнхий дэд мөрүүд байж болно.

Оролт

Оролтын эхний мөрөнд дөрвөн бүхэл тоон утга $l_{1}$, $r_{1}$, $l_{2}$, $r_{2}$ ($1 ≤ l_{i} ≤ r_{i} ≤ 10^{9}$, $i = 1, 2$) байна. Тоонууд зайгаар тусгаарлагдана. $l_{i}$ ба $r_{i}$ нь $i$-р сонгогдсон дэд тэмдэгт мөрийн эхний болон сүүлийн тэмдэгтүүдийн индексүүдийг өгнө харгалзан ($i = 1, 2$). $abracadabra$ тэмдэгт мөрийн тэмдэгтүүд нь $1$-с эхлэн дугаарлагдана.

Гаралт

Өгөгдсөн тэмдэгт мөрүүдийн хамгийн урт ерөнхий дэд тэмдэгт мөрийн урт болох нэг тоог хэвлэ. Хэрвээ ерөнхий дэд тэмдэгт мөрүүд байхгүй бол 0-г хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
3 6 1 4
Гаралт
2
Оролт
1 1 4 4
Гаралт
0

Тэмдэглэл

Эхний жишээн дээр эхний дэд тэмдэг мөр "$acab$", хоёр дахь нь "$abac$". Энэ хоёр дэд тэмдэгт мөрүүдийн хувьд хоёр хамгийн урт ерөнхий дэд тэмдэгт мөр буюу "$ac$" ба "$ab$" байх боловч бид зөвхөн уртыг нь л сонирхож байгаа. Ингээд хариу 2 юм.

Хоёр дахь жишээн дээр эхний дэд тэмдэгт мөр "$a$" ба хоёр дахь нь "$c$". Энэ хоёр дэд тэмдэгт мөрүүд нь ямар ч ерөнхий тэмдэгтгүй ба тэдний хамгийн урт ерөнхий дэд тэмдэгт мөрийн урт 0 байна.

Сэтгэгдлүүдийг ачааллаж байна...