Танд хоосон биш шулуун $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'$ тэмдэгт мөрийг хэвлэ.