403671: GYM101237 H Cyclic String

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 S₁, S₂, ..., S_K 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 S₁, S₂, ..., S_K are strings that are compared lexicographically.

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 K numbers: 1-based starting positions of substrings that form the answer in increasing order.

abcaab
1

4

abacabadaba
5

1 3 5 9 11