311113: CF1936B. Pinball

B. Pinballtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

There is a one-dimensional grid of length $n$. The $i$-th cell of the grid contains a character $s_i$, which is either '<' or '>'.

When a pinball is placed on one of the cells, it moves according to the following rules:

• If the pinball is on the $i$-th cell and $s_i$ is '<', the pinball moves one cell to the left in the next second. If $s_i$ is '>', it moves one cell to the right.
• After the pinball has moved, the character $s_i$ is inverted (i. e. if $s_i$ used to be '<', it becomes '>', and vice versa).
• The pinball stops moving when it leaves the grid: either from the left border or from the right one.

You need to answer $n$ independent queries. In the $i$-th query, a pinball will be placed on the $i$-th cell. Note that we always place a pinball on the initial grid.

For each query, calculate how many seconds it takes the pinball to leave the grid. It can be shown that the pinball will always leave the grid within a finite number of steps.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 5 \cdot 10^5$).

The second line of each test case contains a string $s_1s_2 \ldots s_{n}$ of length $n$ consisting of characters '<' and '>'.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

Output

For each test case, for each $i$ ($1 \le i \le n$) output the answer if a pinball is initially placed on the $i$-th cell.

ExampleInput

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

Output

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

Note

In the first test case, the movement of the pinball for $i=1$ is shown in the following pictures. It takes the pinball $3$ seconds to leave the grid.

The movement of the pinball for $i=2$ is shown in the following pictures. It takes the pinball $6$ seconds to leave the grid.

题目大意：
这个问题是关于一个一维网格的弹球游戏。网格的长度为 n，每个单元格包含一个字符 s_i，这个字符要么是 '<'，要么是 '>'。当弹球被放置在某个单元格上时，它会根据以下规则移动：
1. 如果弹球在第 i 个单元格上，且 s_i 是 '<'，则弹球在下一秒向左移动一个单元格；如果 s_i 是 '>'，则向右移动一个单元格。
2. 弹球移动后，字符 s_i 会翻转（即如果 s_i 曾经是 '<'，它会变成 '>'，反之亦然）。
3. 弹球停止移动当它离开网格：要么从左边界，要么从右边界。

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

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

输入输出数据格式：
输入：
- 每个测试包含多个测试案例。第一行包含测试案例的数量 t（1 ≤ t ≤ 10^5）。
- 每个测试案例的第一行包含一个整数 n（1 ≤ n ≤ 5 × 10^5）。
- 每个测试案例的第二行包含一个长度为 n 的字符串 s_1s_2...s_n，由 '<' 和 '>' 字符组成。
- 保证所有测试案例的 n 之和不超过 5 × 10^5。

输出：
- 对于每个测试案例，对于每个 i（1 ≤ i ≤ n），输出如果弹球最初放在第 i 个单元格上的答案。

示例：
输入：
```
3
3
>&<
4
<<<<
6
<><<<>>
```
输出：
```
3 6 5
1 2 3 4
1 4 7 10 8 1
```

注意：
- 在第一个测试案例中，当 i=1 时，弹球需要 3 秒钟离开网格。
- 在第一个测试案例中，当 i=2 时，弹球需要 6 秒钟离开网格。题目大意： 这个问题是关于一个一维网格的弹球游戏。网格的长度为 n，每个单元格包含一个字符 s_i，这个字符要么是 '<'，要么是 '>'。当弹球被放置在某个单元格上时，它会根据以下规则移动： 1. 如果弹球在第 i 个单元格上，且 s_i 是 '<'，则弹球在下一秒向左移动一个单元格；如果 s_i 是 '>'，则向右移动一个单元格。 2. 弹球移动后，字符 s_i 会翻转（即如果 s_i 曾经是 '<'，它会变成 '>'，反之亦然）。 3. 弹球停止移动当它离开网格：要么从左边界，要么从右边界。 需要回答 n 个独立的查询。在第 i 个查询中，一个弹球将被放置在第 i 个单元格上。注意，我们总是在初始网格上放置弹球。 对于每个查询，计算弹球离开网格需要多少秒。可以证明，弹球总是在有限步内离开网格。 输入输出数据格式： 输入： - 每个测试包含多个测试案例。第一行包含测试案例的数量 t（1 ≤ t ≤ 10^5）。 - 每个测试案例的第一行包含一个整数 n（1 ≤ n ≤ 5 × 10^5）。 - 每个测试案例的第二行包含一个长度为 n 的字符串 s_1s_2...s_n，由 '<' 和 '>' 字符组成。 - 保证所有测试案例的 n 之和不超过 5 × 10^5。 输出： - 对于每个测试案例，对于每个 i（1 ≤ i ≤ n），输出如果弹球最初放在第 i 个单元格上的答案。 示例： 输入： ``` 3 3 >&< 4 <<<< 6 <><<<>> ``` 输出： ``` 3 6 5 1 2 3 4 1 4 7 10 8 1 ``` 注意： - 在第一个测试案例中，当 i=1 时，弹球需要 3 秒钟离开网格。 - 在第一个测试案例中，当 i=2 时，弹球需要 6 秒钟离开网格。