В некоторой стране $$$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$$$.