В некоторой стране \(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\).
Выходные данные
Для каждого набора входных данных выведите \(n + 1\) целое число. \(i\)-е число должно быть равно максимальному количеству городов, которое можно посетить за одно путешествие, если это путешествие начинается в \(i\)-м городе.