AT_scpc2026_div3_e 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 \leq T \leq 100\,000$ - $3 \leq N \leq 100\,000$ - $S$ 是长度为 $N$ 且仅包含 `O` 和 `X` 的字符串。 - $S$ 的第 $i$ 个字符为第 $i$ 位学生名牌上的字母。 - 不存在连续三位或以上学生名牌上的字母完全相同的情况。 - 所有测试数据的 $N$ 之和不超过 $300\,000$。 - 所有输入均为整数。 由 ChatGPT 5 翻译