Abdelaziz likes to rickroll Ali. That is, he sends Ali links that lead to Rick Astley's music video Never Gonna Give you up. Ali is tired of being rickrolled over and over, so he decided to memorize the URL of rickroll links. However, that's not going to stop Abdelaziz from trying.

To trick Ali into opening his rickrolls, Abdelaziz is going to sneakily put the rickroll links together with a list containing other normal links. Let's represent a rickroll with the uppercase letter $R$ and a normal link with the uppercase letter $N$. The list will be a string containing only the letters $R$ and $N$.

To make sure Ali doesn't notice, the list has to satisfy the following conditions:

1. The first link in the list cannot be a rickroll.

2. No two rickrolls are allowed to be in a row. e.g. $NRR$ is not allowed.

3. The number of normal links between two rickrolls has to at least double every time. Formally, let the number of normal links between two consecutive rickrolls, $R_1$ and $R_2$, such that there are no rickrolls between $R_1$ and $R_2$, be $n$. The number of normal links between $R_2$ and the next rickroll has to be $\geq$ $2n$.

Abdelaziz would like to rickroll Ali as much as possible, so he wants to increase the number of rickroll links in his list. He can do that by replacing a normal link with a rickroll. Can you help him with that?

Given a string s consisting only of the uppercase letters $N$ and $R$ representing Abdelaziz's list, find the maximum possible number of rickrolls that you can add by replacing normal links, without Ali noticing. Note that you're not allowed to remove existing rickrolls, or change their positions.

The first and only line of the input contains a single string $s$ consisting only of the uppercase letters $N$ and $R$, $2 \leq |s| \leq 2‌⋅10^5$. It is guaranteed that the string represents a valid list (i.e. Ali cannot notice the rickrolls in the input string) and that it starts with $NR$.

The first line of the output should contain a single integer, the maximum number of extra rickrolls that you can put in the list. The second line should contain a string of length $|s|$, representing the new list.

If there are multiple answers, print any of them.