← 返回题目列表

Codeforces · 827/E

E. 生锈的绳子

中文机器翻译题面 查看原题

格里戈里喜欢弦乐。最近他在阁楼上发现了一条金属条。该条带的长度为n,由字母“V”和“K”组成。不幸的是,锈蚀已经腐蚀了一些字母,因此现在无法理解写的是哪一个字母。

格里戈里很长一段时间都无法理解这些字母让他想起了什么,于是他对以下问题产生了兴趣:如果我们在每个不可读的位置上放置一个字母“V”或“K”,得到的字符串的周期可以等于哪些值?

字符串的周期是从 1 到字符串长度的整数 d,如果我们将字符串向右移动 d 个位置,则所有重叠的字母都会重合。例如,3和5是“VKKVK”​​的周期。

输入

输入中有多个(至少一个)测试用例。第一行包含单个整数——测试用例的数量。

每个测试用例之前都有一个空行。每个测试用例由两行描述:第一行包含单个整数 n (1 ≤ n ≤ 5·105) - 字符串的长度,第二行包含长度为 n 的字符串,由字母“V”、“K”和字符“?”组成。后者意味着其位置上的字母不可读。

保证所有测试用例的长度之和不超过5·105。

对于 hacks,您只能使用一个测试用例进行测试。

输出

对于每个测试用例,打印两行。在第一行中,在我们用“V”或“K”替换每个不可读的字母后,打印可能的句点数。在下一行中按升序打印所有这些值。

示例

输入 #1

3
5
V??VK
6
??????
4
?VK?

输出 #1

2
3 5
6
1 2 3 4 5 6
3
2 3 4

注意

在示例的第一个测试用例中,我们可以获得例如“VKKVK”,它具有周期 3 和 5。

在第二个测试用例中,我们可以获得“VVVVVV”,它具有从 1 到 6 的所有周期。

在第三个测试用例中,字符串“KVKV”具有周期 2 和 4,字符串“KVKK”具有周期 3 和 4。