Rusty String
Contest: VK Cup 2017 - Finals
Difficulty rating: 2700
Tags: fft, math, strings

Grigory loves strings. Recently he found a metal strip on a loft. The strip had length n and consisted of letters "V" and "K". Unfortunately, rust has eaten some of the letters so that it's now impossible to understand which letter was written.

Grigory couldn't understand for a long time what these letters remind him of, so he became interested in the following question: if we put a letter "V" or "K" on each unreadable position, which values can the period of the resulting string be equal to?

A period of a string is such an integer d from 1 to the length of the string that if we put the string shifted by d positions to the right on itself, then all overlapping letters coincide. For example, 3 and 5 are periods of "VKKVK".

Input format:
There are several (at least one) test cases in the input. The first line contains single integer — the number of test cases.

There is an empty line before each test case. Each test case is described in two lines: the first line contains single integer n (1 ≤ n ≤ 5·105) — the length of the string, the second line contains the string of length n, consisting of letters "V", "K" and characters "?". The latter means the letter on its position is unreadable.

It is guaranteed that the sum of lengths among all test cases doesn't exceed 5·105.

For hacks you can only use tests with one test case.

Output format:
For each test case print two lines. In the first line print the number of possible periods after we replace each unreadable letter with "V" or "K". In the next line print all these values in increasing order.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first test case from example we can obtain, for example, "VKKVK", which has periods 3 and 5.

In the second test case we can obtain "VVVVVV" which has all periods from 1 to 6.

In the third test case string "KVKV" has periods 2 and 4, and string "KVKK" has periods 3 and 4.

Example input:
3
5
V??VK
6
??????
4
?VK?

Example output:
2
3 5
6
1 2 3 4 5 6
3
2 3 4

Editorial:
Let si is symbol number i from the given string.
Statement: k can be period of string s when if and only if there are no two indices i and j for which $$s_i \neq s_j, s_i \neq?, s_j \neq?, i \bmod k = j \bmod k$$.
Evidence:
Necessity: Let it is not true. Then for any letter fill of omissions such paint i and j will left that si ≠ sj, si ≠ ?, sj ≠ ? and this contradicts the definition of the period.
Adequacy: Let fill omissions with constructive algorithm in a way that string after that is having a period k. Let's look on some remainder of division on k. There are two options. In the first option there are no such i that i gives needed remainder by divide on k and si ≠ ?. Then let fill all positions with such remainder with symbol "V". In the second option there are i such that i gives this remainder by division on k and si ≠ ?. Let fill all positions with this remainder symbol si. Now in all positions with equal remainder by division on k in string stand equal symbols and it means that string has period k.
Let's call a pair indices i and j contradictory, if si ≠ sj, si ≠ ? and sj ≠ ?, then the string has period k if and only if there are no contradictory pair i and j for which |i - j| is divisible by k. This is a direct consequence of the statement proved above.
Let's learn how to search for all such numbers x that there is contradictory pair i and j that i - j = x. Let A — the set of positions, where stand "V", and B — the set of such positions i that sn - i = K. So our task reduced to finding such all possible numbers that it is representable as the sum of a number from A and a number from B.
Let's look on polynomials P(x) = a1x1 + a2x2 + ..., Q(x) = b1x1 + b2x2 + ..., where ai equals to 1, if i can be found in A or 0, otherwise. Similarly for set B and bi. Let's look on P(x) * Q(x). Coefficient at xi is equal to 1 if and only if when i сan be represented in sum of a number from A and a number from B. It is correct because coefficient at xi equals to $$\sum_{j=0}^{i}a_{j}b_{i-j}$$. But ajbi - j ≥ 0 and equals to 1 if and only if when aj = 1 и bi - j = 1, and it means that $$j \in A, (i-j) \in B$$, but j + (i - j) = i. Polynomials can be multiplied with help of Fast Fourier transform, so this part of solution works in O(nlogn).
It is only left to learn how to check that k is a period of string. It can be done in $${\mathcal{O}}\left({\frac{n}{k}}\right)$$, with check all numbers like ik ≤ n. Totally it works in $$\sum_{i=1}^{n} O\left(\frac{n}{k}\right) = O(n \log n)$$. So, all solution works in O(nlogn).