E. Төвөгтэй, ухаалаг нууц үг

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

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

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

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

Бидний түүхийн баатар хаан Копа залуу насандаа хангалттай аюулгүй биш байсан хувийн мэдээллээ өөрөө ч хандаж чадахааргүй болгохоор шийдсэн. Иймээс тэр төвөгтэй ба ухаалаг нууц үг (дараа нь тэр нууц үгээ сондгой урттай палиндром гэдгийг мэдсэн) зохиож өөрийн бүх мэдээллээ үүнийгээ ашиглан кодлосон.

Копа нууц үгээ мартахаас айж байгаа учир нууц үгээ цаасан дээр бичихээр шийдсэн. Тэр нууц үгийг ийм байдлаар хадгалах нь найдваргүй гэдгийг мэдэх ба нууц үгээ дараах аргаар шифрлэхээр болсон: тэр нууц үгийнхээ эхлэл болон сүүлээс $x$ тэмдэгт таслаж авна ($x$ нь $0$ байж болно мөн $2x$ нь нууц үгийн уртаас илэрхий богино байна). Тэр нууц үгээ гурван хэсэг болгон хуваасан. Харгалзан угтвар, гол, дагавар гэж нэрлэе, угтвар болон дагавар нь хоёулаа ижил урттай ба гол нь үргэлж сондгой урттай байна. Копа энэ гурван хэсгийг ашиглан $A + угтвар + B + гол + C + дагавар$ тэмдэгт мөр үүсгэсэн ба энд $A$, $B$ ба $C$ (хоосон байж болно) нь Копагийн зохиосон тэмдэгт мөрүүд юм. Харин «$ + $» нь залгана гэсэн үг.

Олон жил өнгөрсөн ба хаан Копа өчигдөрхөн шифрлэгдсэн нууц үгээ бичсэн цаасаа олсон. Копа нууц үгээ $A$, $B$, $C$ тэмдэгт мөрүүд шигээ таг мартсан. Тиймээс тэр таныг Копа өөрөө зохиож, шифрлэж, бичсэн байж болох боломжит хамгийн урт урттай нууц үгийг олохыг хүсч байна.

Оролт

Оролтонд Латин жижиг үсгүүдээс бүрдсэн $1$-с $10^{5}$ хүртэлх урттай нэг ширхэг тэмдэгт мөр байна.

Гаралт

Эхний мөрөнд бүхэл тоон утга $k$ байх ёстой. Энэ нь таны хариулт дахь нууц үгийн хоосон биш хэсгүүдийн хэмжээ байна (). Дараагийн $k$ мөр бүрт хоёр бүхэл тоон утга $x_{i}$ ба $l_{i}$ байх ба нууц үгийн харгалзах хэсгийн эхлэл болон урт юм. Хос тоонуудыг $x_{i}$-н өсөх дарааллаар хэвлэнэ үү. Хос тоонуудыг хооронд нь зайгаар тусгаарлана.

Эхлэх байрлал $x_{i}$ нь $1$-c оролтын тэмдэгт мөрийн урт хүртэлх бүхэл тоон утга байна. Бүх $l_{i}$ нь эерэг байх ёстой учир нь та зөвхөн хоосон биш хэсгүүдийг хэвлэж байгаа. Гол хэсэг сондгой урттай байх ёстой.

Хэрвээ хэд хэдэн шийдэл байвал алийг нь ч хэвлэж болно. Таны зорилго бол $l_{i}$-н нийлбэрийг хамгийн их байлгах болохоос $k$-г хамгийн их байлгах биш гэдгийг сана.

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

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

Оролт
abacaba
Гаралт
1
1 7
Оролт
axbya
Гаралт
3
1 1
2 1
5 1
Оролт
xabyczba
Гаралт
3
2 2
4 1
7 2
Сэтгэгдлүүдийг ачааллаж байна...