D. Путешествие
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В некоторой стране $$$n + 1$$$ городов, пронумерованных от $$$0$$$ до $$$n$$$. $$$n$$$ дорог соединяют эти города, $$$i$$$-я дорога соединяет города $$$i - 1$$$ и $$$i$$$ ($$$i \in [1, n]$$$).

У каждой дороги есть направление. Направления задаются строкой из $$$n$$$ символов, каждый символ — либо L, либо R. Если $$$i$$$-й символ — L, то $$$i$$$-я дорога сначала направлена из города $$$i$$$ в город $$$i - 1$$$; иначе она направлена из города $$$i - 1$$$ в город $$$i$$$.

Путешественник хочет посетить как можно больше городов этой страны. Сначала он выбирает город, из которого начнет свое путешествие. Каждый день путешественник должен перейти из текущего города в соседний город по дороге, и он может перейти по дороге только в соответствии с ее направлением; то есть, если дорога направлена из города $$$i$$$ в город $$$i + 1$$$, он может перейти из города $$$i$$$ в город $$$i + 1$$$, но не из $$$i + 1$$$ в $$$i$$$. После того как путешественник перемещается в соседний город, все дороги меняют свое направление на противоположное. Если путешественник не может перейти в соседний город, он обязан закончить свое путешествие; также он может закончить путешествие в любой момент, в который захочет.

Цель путешественника — посетить как можно больше городов за одно путешествие (каждый город можно посетить любое количество раз, но только первое посещение считается). Для каждого города $$$i$$$ посчитайте максимальное количество городов, которое путешественник может посетить за одно путешествие, если оно начинается в городе $$$i$$$.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк. В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$). Во второй строке — последовательность $$$s$$$, состоящая из ровно $$$n$$$ символов, каждый из которых — L или R.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n + 1$$$ целое число. $$$i$$$-е число должно быть равно максимальному количеству городов, которое можно посетить за одно путешествие, если это путешествие начинается в $$$i$$$-м городе.

Пример
Входные данные
2
6
LRRRLL
3
LRL
Выходные данные
1 3 2 3 1 3 2
1 4 1 4