B. Пинбол
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана полоска из $$$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$$$ ($$$1 \le i \le 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$$$ секунд, чтобы покинуть полоску.