403671: GYM101237 H Cyclic String

Memory Limit:512 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Cyclic Stringtime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

You are given N characters written on a circle. Let us split this circle in K places so that no character is cut apart and no two cuts pass through the same place. After this operation K strings S1, S2, ..., SK are formed by reading characters on each part clockwise.

Your task is to find such a way of splitting that is minimal possible. Note that S1, S2, ..., SK are strings that are compared lexicographically.

Input

The first line contains N lowercase English letters (1 ≤ N ≤ 2000), which are the characters written on circle in clockwise order.

The second line contains the integer K (1 ≤ K ≤ |S|).

Output

Output K numbers: 1-based starting positions of substrings that form the answer in increasing order.

ExamplesInput
abcaab
1
Output
4
Input
abacabadaba
5
Output
1 3 5 9 11

加入题单

上一题 下一题 算法标签: