410282: GYM103999 K Iuli

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);

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

On each of the next $$$t$$$ lines there will be a string $$$s$$$ $$$(|s|<=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$$$.

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.

• 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$$$.

1
aaaaaa

1 2 3 6 

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