AT_scpc2026_div2_j DETOX

/ / 有 $N$ 个学生，编号为 $1$ 到 $N$，按编号顺序围成一圈坐着。每个学生佩戴一个写有字母 `O` 或 `X` 的姓名牌。每个学生可以看到除了自己之外的 $N-1$ 个学生的姓名牌。没有连续的三个或更多的学生姓名牌上写着相同的字母，并且所有学生都知道这个事实。 游戏持续进行，直到所有学生都正确猜出自己姓名牌上的字母。游戏规则如下： - 每一轮，所有已经能够确定自己姓名牌上字母的学生会同时举手。 - 在每轮结束后，所有学生都会确认本轮中有哪些学生举手，然后进入下一轮。 在游戏过程中，任何学生都不能与他人交换姓名牌、摘下姓名牌或更改姓名牌上的字母。 现在给出 $T$ 个测试用例。对于每个测试用例，请判断每位学生最早会在第几轮举手。

输入由标准输入给出，格式如下： > $T$ $case_1$ $case_2$ $\vdots$ $case_T$ 每个测试用例格式如下： > $N$ $S$

对于每个测试用例，输出 $N$ 个非负整数，用空格隔开，位于一行。第 $i$ 个整数 $r_i$ 表示第 $i$ 位学生最早会在第 $r_i$ 轮举手。如果存在某个学生无论游戏进行多久都无法举手，请输出 `-1`。

### 样例说明 1 在第一个测试用例中，4 个学生坐成一圈，各自的姓名牌上分别标有 `X`、`O`、`X`、`O`。 在第一轮中，学生 $2$ 观察到学生 $1$ 与学生 $3$ 都佩戴了写有 `X` 的姓名牌。如果学生 $2$ 佩戴的也是 `X`，那么学生 $2$、$3$ 和 $4$ 就会连续三个学生都佩戴 `X`，这与题目规则（三个及以上连续的学生不能佩戴相同字母的牌）相矛盾。 因此，学生 $2$ 不可能佩戴 `X`，他可以确定自己佩戴的一定是 `O`，所以在第一轮举手。其他学生也会用类似的推理在第一轮内举手。 ### 数据范围与限制 - $1 \le T \le 100\,000$ - $3 \le N \le 100\,000$ - $S$ 是长度为 $N$ 的仅由 `O` 和 `X` 组成的字符串。 - $S$ 的第 $i$ 个字符表示第 $i$ 位学生姓名牌上的字母。 - 没有任何连续的三个学生姓名牌上写着相同字母。 - 所有测试用例中 $N$ 的总和不超过 $300\,000$。 - 所有输入均为整数。 由 ChatGPT 5 翻译