K. Iuli
time limit per test
0.8 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

It is the first day of school and you are in Computer Science class. Your best friend Iuli has a new challenge for you.

He hands you a string consisting of lowercase english characters and asks you to find the length of all its periods.

A period of a string is a prefix of it which has the property that the string can be written as a concatenation of that prefix with itself for a finite number of times.

For example, the periods of $$$aaaaaa$$$ are $$$a, aa, aaa, aaaaaa$$$.

Due to the high ammount of input and output data, it is recommended to code in C++, use streams and the following instructions before reading the input for speedup:

ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
Input

On the first line there will be an integer $$$t \lt =20$$$, the number of testcases.

On each of the next $$$t$$$ lines there will be a string $$$s$$$ $$$(|s| \lt =10^6)$$$ containing lowercase letters of the english alphabet.

The sum of lengths of all strings in the input will not exceed $$$2\cdot10^7$$$.

Output

The output will consist of $$$t$$$ lines.

On line $$$i$$$ there will be a list of integers signifying the periods of the $$$i^{th}$$$ string in the input. The numbers on each line will be sorted increasingly and will have a single space between them.

Scoring
  • for $$$30$$$ points, it is guaranteed that the sum of lengths of all strings in the input will not exceed $$$10^4$$$
  • for another $$$40$$$ points, it is guaranteed that the sum of lengths of all strings in the input will not exceed $$$5\cdot10^6$$$
  • for the last $$$30$$$ points, the sum of lengths of all strings in the input will not exceed $$$2\cdot10^7$$$.
Example
Input
1
aaaaaa
Output
1 2 3 6
Note

The periods of $$$aaaaaa$$$ are $$$a, aa, aaa, aaaaaa$$$ which have lengths $$$1, 2, 3, 6$$$