594E орчуулах · Codeforces.mn

# Шулууныг хуваах
Танд хоосон биш шулуун $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