B. Эртний Берланд-ын дүрс бичиг

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

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

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

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

Поликарпус Берланд-ын дүрс бичиг судлах дуртай байжээ. Нэгэн удаа Поликарпус Берланд-ын эртний 2 зураг олсон бөгөөд тус бүр дээр нь дүрс бичгээс тогтох тойргууд агуулагдаж байв. Бид ямар ч дүрс бичиг нь эхний эсвэл 2-р тойрогт 2 удаа ороогүй болохыг мэдэж байв. Гэхдээ тэдгээрийн тус бүрд нь нэг нэг удаа орсон байж болно.

Поликарпус эдгээр зургуудыг өөрийн зөөврийн компьютер дээрээ хадгалахыг хүссэн боловч нэгэн асуудалтай тулгарчээ. Зөөврийн компьютер дүрс бичиг бүхий тойргуудыг бичихийг зөвшөөрөхгүй байв. Иймд Поликарпус тойрог болгоныг эвдлэх хэрэгтэй болсон бөгөөд уг тойрог дээрх бүх дүрс бичгүүдийг цагийн зүүний дагуу чиглэлд нэг мөрөнд бичихээр болжээ. Эхний тойргоос үүсэх мөрийг бид $a$ гэж тэмдэглэх ба 2-дахь тойргоос үүсэх мөрийг $b$ гэж тэмдэглэнэ.

Дүрс бичиг бүхий тойргуудыг эвдлэх маш олон тооны арга байгаа бөгөөд иймд Поликарпус $b$ тэмдэгт мөр дотор дэд дараалал хэлбэрээр орсон байх $a$ тэмдэгт мөрийн дэд тэмдэгт мөрийн урт нь хамгийн их байх аргыг сонгохоор шийджээ.

Хэрэв эхний болон 2-р тойргуудыг оновчтой байдлаар эвдэлнэ гэж үзвэл Поликарпус-д туслан ийм байх дэд тэмдэгт мөрийн (өөрөөр хэлбэл $b$ тэмдэгт мөр доторх дэд дараалал) боломжит хамгийн их уртыг олж өгнө үү.

$s$ тэмдэгт мөрийн урт гэдэг нь уг тэмдэгт мөр дотор агуулагдах тэмдэгтүүдийн тоог илэрхийлнэ. Хэрэв бид $s$ тэмдэгт мөрийн уртыг $|s|$-ээр тэмдэглэвэл бид уг тэмдэгт мөрийг $s = s_{1}s_{2}... s_{|s|}$ хэлбэртэй бичиж болох юм.

$s$ тэмдэгт мөрийн дэд тэмдэгт мөр гэдэг нь $x = s[a... b] = s_{a}s_{a + 1}... s_{b}$ ($1 ≤ a ≤ b ≤ |s|$) байх хоосон биш тэмдэгт мөрийг хэлнэ. Жишээлбэл "$code$" болон "$force$" нь "$codeforces$" гэсэн тэмдэгт мөрийн дэд тэмдэгт мөрүүд байх бол "$coders$" нь уг тэмдэгт мөрийн дэд тэмдэгт мөр биш юм.

$s$ тэмдэгт мөрийн дэд дараалал гэдэг нь $y = s[p_{1}p_{2}... p_{|y|}] = s_{p_{1}}s_{p_{2}}... s_{p_{|y|}}$ ($1 ≤ p_{1} < p_{2} < ... < p_{|y|} ≤ |s|$) байх хоосон биш тэмдэгт мөрийг хэлнэ. Жишээлбэл "$coders$" гэдэг нь "$codeforces$" гэсэн тэмдэгт мөрийн дэд дараалал юм.

Оролт

Эхний мөрөнд 2 бүхэл тоо $l_{a}$ болон $l_{b}$ ($1 ≤ l_{a}, l_{b} ≤ 1000000$) өгөгдөх ба эдгээр нь харгалзан эхний болон 2-р тойрог доторх дүрс бичгийн тоог илэрхийлнэ.

Берландын дүрс бичгүүдийг шифрлэх нь ихээхэн хүнд учраас доор өгөгдөх бүх бүхэл тоонууд нь $1$-ээс $10^{6}$ хүртэлх бүхэл тоонууд байна.

2-дахь мөрөнд $l_{a}$ ширхэг бүхэл тоонууд өгөгдөх ба эдгээр нь дүрс бичгүүдийн аль нэгээс нь эхлэн цагийн зүүний дагуу чиглэлд өгөгдсөн эхний зураг дахь дүрс бичгүүдийг илэрхийлнэ.

3-дахь мөрөнд $l_{b}$ ширхэг бүхэл тоонууд өгөгдөх ба эдгээр нь дүрс бичгүүдийн аль нэгээс нь эхлэн цагийн зүүний дагуу чиглэлд өгөгдсөн 2-р зураг дахь дүрс бичгүүдийг илэрхийлнэ.

Мөн эхний тойрог нь ямар нэгэн дүрс бичгийг 2 удаа агуулаагүй байна. 2-р тойргийн хувьд ч мөн адил уг чанар биелж байх юм.

Гаралт

Ерөнхий дэд тэмдэгт мөр буюу дэд дарааллын боломжит хамгийн их уртыг илэрхийлэх ганц тоог хэвлэнэ үү. Хэрэв тойргуудыг эвдлэх ямар ч аргын хувьд уг дэд тэмдэгт мөр буюу дэд дараалал нь оршин байхгүй байвал 0 гэж хэвлэнэ үү.

Орчуулсан: Баатархүү

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

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

Тэмдэглэл

Эхний жишээнд Поликарпус 5 болон 1 гэсэн дүрс бичгүүдээс тогтох тэмдэгт мөрийг сонгох бөгөөд 2-дахь жишээнд 1, 3 болон 5 гэсэн дүрс бичгүүдээс тогтох тэмдэгт мөрийг сонгоно.

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