Diluc 与 Kaeya

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给你一个字符串 $S$，其中只包含 'K' 或 'D' 两种字符，要求划分这个字符串使得各部分的 $n(D):n(K)$ 相同，其中 $n(D)$ 表示 $S$ 中字符 'D' 出现的个数，最大化划分后形成的组数。

求出 $S$ 的所有前缀中的上述答案。

一个非空字符串的比例记为 $a:b$，其中 $a$、$b$ 分别是 D、K 的出现次数，二者可以有一个为 $0$。比例 $a:b$ 与 $c:d$ 相同，当且仅当 $a\times d=b\times c$。

输入格式

第一行一个整数 $T$，代表测试组数。

接下来每一组第一行一个整数 $n$，代表字符串 $S$ 的长度，第二行一个字符串 $S$。

输出格式

一共输出 $T$ 行，对于每组数据，输出 $S$ 的所有前缀的答案。

样例输入 1

5
3
DDK
6
DDDDDD
4
DKDK
1
D
9
DKDKDDDDK

样例输出 1

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

数据范围

对于所有数据，$1\le T\le1000$，$1\le n\le5\times10^5$，字符串只含 D 与 K；所有测试用例中 $n$ 的总和不超过 $5\times10^5$。