### 问题描述 小明是一个聪明的领袖，他带领着一支由 $n$ 名士兵组成的队伍，每个士兵都面向左或右。在行进的过程中，小明希望知道队伍的价值，他定义队伍的价值为每个士兵所看到的同伴数量之和。例如，在队伍排列为 LRRLL 的情况下，队伍的价值为 $0+3+2+3+4=12$，其中第二个士兵向右看到了三个同伴，第三个士兵向右看到了两个同伴，第四个士兵向右看到了三个同伴，第五个士兵向右看到了四个同伴。 小明现在希望知道，在改变队伍中至多 $k$ 名士兵的朝向的情况下，队伍的价值最大可以达到多少。请你帮助小明解决这个问题。 ### 输入格式 第一行包含一个整数 $t$，表示测试用例的数量。 对于每个测试用例，第一行包含一个整数 $n$，表示队伍的长度。 第二行是一个长度为 $n$ 的字符串，表示队伍中每个士兵的面向，其中 L 表示向左，R 表示向右。 ### 输出格式 对于每个测试用例，输出一行 $n$ 个非负整数，第 $i$ 个整数表示最多改变 $i$ 名士兵的朝向后，队伍的最大价值。 ### 样例输入 ```txt 2 3 LLR 5 LRRLL ``` ### 样例输出 ```txt 3 5 5 16 16 16 16 16 ``` ### 样例说明 在第一个测试用例中： + $k=1$：改变 $1$ 个士兵的方向，使线变成 $RLR$。整条线的价值为 $2+1+0=3$。 + $k=2$：改变 $2$ 个士兵的方向，使线变成 $RLL$。整条线的价值为 $2+1+2=5$。 + $k=3$：改变 $2$ 个士兵的方向，使线变成 $RLL$。整条线的价值为 $2+1+2=5$。 在第二个测试案例中，对于所有的 $𝑘$ 从 $1$ 到 $5$，最好只改变第一个士兵的方向（即 $RRRLL$ ）。 ### 评测数据规模 对于 $100$% 的评测数据，$1\leq t \leq 5, 1\leq n \leq 10^5$。