AT_scpc2026_div2_j DETOX

#### 表示言語 / / $ N $ students, numbered from $ 1 $ to $ N $ , are seated in a circle in numerical order. Each student wears a name tag marked with either `O` or `X`. Each student can see the name tags of $ N-1 $ students, **excluding their own**. No three or more students sitting next to each other have name tags with the same letter, and all students are aware of this fact. The game continues until every student has correctly guessed the letter on their own name tag. The rules of the game are as follows: - In each round, all students who are certain of the letter on their name tag raise their hands at the same time. - Once all students have confirmed which students raised their hands in this round, the next round begins. During the game, no student may exchange name tags with others, remove their name tag, or change the letter on their name tag. You are given $ T $ test cases. For each test case, determine in which round each student will raise their hand for the first time.

The input is given from Standard Input in the following format: > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ Each test case is given in the following format: > $ N $ $ S $

Output $ N $ non-negative integers, separated by spaces, on a single line for each test case. The $ i $ th integer, $ r_i $ , indicates the $ r_i $ th round in which student $ i $ first raises their hand. If there is a student who cannot raise their hand no matter how long the game continues, output `-1` instead.

### Sample Explanation 1 In the first test case, four students are seated in a circle, each wearing a name tag labeled `X`, `O`, `X`, and `O`, respectively. In the first round, Student $ 2 $ observes that both Student $ 1 $ and Student $ 3 $ are wearing name tags labeled `X`. If Student $ 2 $ were wearing a badge marked with `X`, then Students $ 2 $ , $ 3 $ , and $ 4 $ would all be wearing badges marked with `X`, which contradicts the rule that three students sitting consecutively cannot all have badges marked with the same character. Therefore, Student $ 2 $ cannot be wearing a name tag marked with an `X` and can be certain that they are wearing a name tag marked with an `O`, so they raise their hand in the first round. The other students also raise their hands in the first round based on the same reasoning. ### Constraints - $ 1 \le T \le 100\,000 $ - $ 3 \le N \le 100\,000 $ - $ S $ is a string of length $ N $ consisting only of `O` and `X`. - The $ i $ th character of $ S $ is the character written on the name tag of the $ i $ th student. - None of the three students sitting consecutively are wearing name tags with the same characters written on them. - The sum of $ N $ over all test cases is at most $ 300\,000 $ . - All input numbers are integers.