H. Cyclic String
time limit per test
4 seconds
memory limit per test
512 megabytes
input
stdin
output
stdout

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.

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