D. Rusty String

Grigory 爱好字符串。最近他在阁楼上发现了一条金属条，其长度为 $n$，由字母 "_V_" 和 "_K_" 组成。不幸的是，锈蚀损坏了一些字母，现在无法分辨原来写的是哪个字母。 Grigory 长时间思考这些字母让他想起了什么，于是他产生了以下问题：如果我们在每个不可读的位置填入 "_V_" 或 "_K_"，那么所得字符串的周期可能取哪些值？ 一个字符串的周期是指一个整数 $d$（从 $1$ 到字符串长度），使得将该字符串向右平移 $d$ 个位置后与原字符串重叠时，所有重叠位置的字母完全一致。例如，$3$ 和 $5$ 都是字符串 "_VKKVK_" 的周期。 输入包含多个（至少一个）测试用例。第一行包含一个整数 —— 测试用例的数量。 每个测试用例前有一行空行。每个测试用例由两行描述：第一行包含一个整数 $n$（$1 ≤ n ≤ 5·10^5$）—— 字符串的长度；第二行包含一个长度为 $n$ 的字符串，由字母 "_V_"、"_K_" 和字符 "_?_" 组成，其中 "_?_" 表示该位置的字母不可读。 保证所有测试用例的字符串长度总和不超过 $5·10^5$。 *对于 Hack*，你只能使用包含一个测试用例的测试数据。 对于每个测试用例，输出两行。第一行输出在将每个不可读字母替换为 "_V_" 或 "_K_" 后，可能的周期数量；第二行按升序输出所有这些周期值。 在示例的第一个测试用例中，我们可以得到例如 "_VKKVK_"，其周期为 $3$ 和 $5$。 在第二个测试用例中，我们可以得到 "_VVVVVV_"，其周期为从 $1$ 到 $6$ 的所有整数。 在第三个测试用例中，字符串 "_KVKV_" 的周期为 $2$ 和 $4$，而字符串 "_KVKK_" 的周期为 $3$ 和 $4$。 ## Input 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 #cf_span[n] (#cf_span[1 ≤ n ≤ 5·105]) — the length of the string, the second line contains the string of length #cf_span[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 #cf_span[5·105].*For hacks* you can only use tests with one test case. ## Output 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. [samples] ## Note In the first test case from example we can obtain, for example, "_VKKVK_", which has periods #cf_span[3] and #cf_span[5].In the second test case we can obtain "_VVVVVV_" which has all periods from #cf_span[1] to #cf_span[6].In the third test case string "_KVKV_" has periods #cf_span[2] and #cf_span[4], and string "_KVKK_" has periods #cf_span[3] and #cf_span[4].

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the length of the string. Let $ S = s_1 s_2 \dots s_n $ be a string over alphabet $ \{V, K, ?\} $, where $ ? $ denotes an unknown character. Let $ \Sigma = \{V, K\} $. For each position $ i $ with $ s_i = ? $, assign $ s_i \in \Sigma $ arbitrarily. Let $ \mathcal{S} $ be the set of all possible strings obtained by replacing each $ ? $ with $ V $ or $ K $. For a string $ T \in \mathcal{S} $, define its period set $ P(T) = \{ d \in \mathbb{Z}^+ \mid 1 \le d \le n \text{ and } T[i] = T[i + d] \text{ for all } i \text{ such that } 1 \le i \le n - d \} $. **Constraints** 1. $ 1 \le n \le 5 \cdot 10^5 $ 2. The total sum of $ n $ across all test cases $ \le 5 \cdot 10^5 $ 3. Each $ s_i \in \{V, K, ?\} $ **Objective** For each test case, compute the set $ \mathcal{P} = \bigcup_{T \in \mathcal{S}} P(T) $, i.e., all integers $ d \in [1, n] $ such that there exists at least one completion $ T \in \mathcal{S} $ for which $ d $ is a period of $ T $. Output $ |\mathcal{P}| $ and the elements of $ \mathcal{P} $ in increasing order.