E. Шулууныг хуваах

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

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

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

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

Танд хоосон биш шулуун $s$ ба бүхэл тоон утга $k$ өгөгдсөн. Дараах үйлдэл шулуун дээр яг нэг удаа хийгдэнэ:

  • Шулуун хамгийн ихдээ $k$ ширхэг хоосон биш дэд тэмдэгт мөрүүдэд хуваагдах буюу тэмдэгт мөр $s$ нь $s = t_{1} + t_{2} + ... + t_{m}$, $1 ≤ m ≤ k$ тэмдэгт мөрүүдийн хэлхээ хэлбэрээр илэрхийлэгдэнэ гэсэн үг.
  • $t_{i}$ тэмдэгт мөрүүдийн зарим нь $t_{i}^{r}$ тэмдэгт мөрүүдээр солигдох буюу тэдний утга нь баруунаас зүүнрүү шилжинэ.
  • Шулуунууд эргээд өмнөх дарааллаараа залгагдаж бид $t'_{i}$ нь $t_{i}$ эсвэл $t_{i}^{r}$-тэй тэнцүү байх $s' = t'_{1}t'_{2}... t'_{m}$ тэмдэгт мөртэй болно.

Таны ажил бол $s$ тэмдэгт мөрд өгөгдсөн үйлдлийг хийгээд гарч болох аль болох цагаан толгойн өсөх дарааллаар эрэмбэлэгдсэн байх тэмдэгт мөрийг тодорхойлох юм.

Оролт

Оролтын эхний мөрөнд $s$ ($1 ≤ |s| ≤ 5 000 000$) тэмдэгт мөр байх ба Англи цагаан толгойн жижиг үсгүүдээс бүрдэнэ. Хоёр дахь мөрөнд бүхэл тоон утга $k$ ($1 ≤ k ≤ |s|$) байх ба байж болох хамгийн их хуваагдсан хэсгийн тоо.

Гаралт

Тодорхойлогдсон үйлдлийг хийгээд гарч болох аль болох цагаан толгойн өсөх дарааллаар эрэмбэлэгдсэн байх $s'$ тэмдэгт мөрийг хэвлэ.

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

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

Оролт
aba
2
Гаралт
aab
Оролт
aaaabacaba
2
Гаралт
aaaaabacab
Оролт
bababa
1
Гаралт
ababab
Оролт
abacabadabacaba
4
Гаралт
aababacabacabad
Сэтгэгдлүүдийг ачааллаж байна...