Перед домом Элис есть песчаная дорожка.
Днем по дорожке ходят люди, каждый их шаг оставляет на дорожке след. Элис не может определить, в каком порядке были оставлены следы, но она может разобрать, оставлен ли каждый след левой или правой ногой. Также она уверена, что все люди ходят, наступая попеременно то левой, то правой ногой.
Например, предположим, что один человек пошел по тропинке и оставил какие-то следы. Пусть следы имеют вид RRLRL в порядке следования по дорожке ('R' обозначает правую ногу, а 'L' обозначает левую ногу). Можно подумать, что это какая-то странная последовательность следов. Но на самом деле, некоторые следы остаются от ходьбы задом наперед!
Есть несколько возможных последовательностей шагов, после которых могли остаться такие следы, например 1 → 3 → 2 → 5 → 4 или 2 → 3 → 4 → 5 → 1 (мы считаем, что расстояние между двумя последовательными шагами может быть произвольным). В двух примерах, приведенных выше, было сделано 2 шага назад и 1 шаг назад соответственно.
Элис заинтересовали эти следы. Каждый раз, когда по дорожке проходит человека, она делает фотографию всех его следов, а затем стирает их все, таким образом, каждый следующий человек оставляет новый набор следов. Мы знаем, что люди ходят, наступая попеременно то правой, то левой ногой, но мы не знаем, с какой ноги делается первый шаг.
Элис хочет знать минимальное возможное количество шагов назад, сделанных человеком, оставившим данную последовательность следов. Пожалуйста, помогите Элис посчитать его. Также вам надо составить возможный вариант последовательности шагов для получения наблюдаемой картины.
В единственной строке записана строка S (1 ≤ |S| ≤ 100 000), содержащая все следы в порядке следования по дорожке от её начала до её конца.
Гарантируется, что есть как минимум одна подходящая последовательность шагов.
Надо вывести 2 строки.
В первой строке должно быть записано число, обозначающее минимальное количество шагов назад.
Во второй строке должна быть записана перестановка целых чисел от 1 до |S|. Эта перестановка должна обозначать порядок, в котором оставлялись следы.
Если существует несколько правильных ответов, разрешается вывести любой из них.
RRLRL
1
2 5 1 3 4
RLRLRLRLR
0
1 2 3 4 5 6 7 8 9
RRRRRLLLL
4
4 9 3 8 2 7 1 6 5
В первом примере один из возможных порядков таков: 2 → 5 → 1 → 3 → 4, из них только шаг 5 → 1 является шагом задом наперед, так что ответ равен 1.
Во втором примере один из возможных порядков — просто пройти по всем следам в порядке следования во вводе, таким образом не будет произведено ни одного шага назад.
В третьем примере в любом случае будет произведено 4 шага назад, так как каждый шаг от L к R будет шагом назад.
