← 返回题目列表

Codeforces · 1936/B

B. 弹球

中文机器翻译题面 查看原题

有一个长度为 $$$n$$$ 的一维网格。网格的第 $$$i$$$ 个单元格包含字符 $$$s_i$$$,即“<”或“>”。

当弹球被放置在其中一个单元格上时,它会根据以下规则移动:

- 如果弹球在第 $$$i$$$ 个单元格上且 $$$s_i$$$ 为 '<',则弹球在下一秒向左移动一个单元格。如果 $$$s_i$$$ 为“>”,则向右移动一个单元格。
- 弹球移动后,字符 $$$s_i$$$ 被反转(即,如果 $$$s_i$$$ 以前是 '<',则变为 '>',反之亦然)。
- 弹球在离开网格时停止移动:无论是从左边界还是从右边界。

您需要回答 $$$n$$$ 个独立查询。在第 $$$i$$$ 个查询中,弹球将放置在第 $$$i$$$ 个单元格上。请注意,我们总是在初始网格上放置一个弹球。

对于每个查询,计算弹球离开网格需要多少秒。可以证明,弹球总是会在有限的步数内离开网格。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$)。

每个测试用例的第二行包含一个字符串 $$$s_1s_2 \ldots s_{n}$$$,长度为 $$$n$$$,由字符“<”和“>”组成。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。

输出

对于每个测试用例,如果弹球最初放置在第 $$$i$$$ 个单元格上,则对于每个 $$$i$$$ ($$$1 \le i \le n$$$) 输出答案。

示例

输入 #1

3
3
><<
4
<<<<
6
<><<<>

输出 #1

3 6 5 
1 2 3 4 
1 4 7 10 8 1

注意

在第一个测试用例中,$$$i=1$$$ 时弹球的运动如下图所示。弹球需要 $$$3$$$ 秒才能离开网格。

$$$i=2$$$ 时弹球的运动如下图所示。弹球需要 $$$6$$$ 秒才能离开网格。