Handshakes

Time limit1sMemory limit128 MB

Summary

Given a row of L/R facing people who flip and shake hands each second when an R stands left of an L, compute total seconds until stabilization and total handshakes, or report it never ends.

Level: Medium7 of 10
Topics: Simulation, Greedy, Math
Solved: No attempts yet

Problem

Before a sports contest, all participants stand in a single row. Each of them faces either to the left or to the right.

Every second, all pairs of neighbouring participants who are currently facing each other shake hands, and then both of them turn around to face the other way. Concretely, whenever a right-facing participant stands immediately to the left of a left-facing participant, that pair is facing each other and shakes hands (the handshake together with the turn takes exactly one second). All facing pairs act at the same time during that second, and every participant who is not part of a facing pair keeps their orientation. In the next second new pairs may face each other, so more handshakes and turns follow, and so on.

The contest starts once the handshaking has ended — if it ever ends. Determine how long the handshaking lasts and how many handshakes happen in total.

Input

A single line containing a string made of the characters L and R. Each character describes one participant in row order: L is a participant facing left at the start, and R is a participant facing right at the start. The length of the string is at most 100000.

Output

Print two integers separated by a single space: the number of seconds until the handshaking stops, followed by the total number of handshakes made. If the handshaking never stops, print NEVEREND instead.

Examples5

Example 1
Input
```
RLLRLRR
```
Expected output
```
3 4
```
Example 2
Input
```
RL
```
Expected output
```
1 1
```
Example 3
Input
```
LR
```
Expected output
```
0 0
```
Example 4
Input
```
LLRR
```
Expected output
```
0 0
```
Example 5
Input
```
RRLL
```
Expected output
```
3 4
```