Zigzag

Interview

Time limit5sMemory limit1024 MB

Summary

Given a string of P and G moves, check whether it is the greedy zigzag under the diagonal of some fraction p/q, and print that fraction in lowest terms or NIE.

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

Problem

Bajtosia has a favorite fraction $p/q$ , where $p$ and $q$ are positive integers. The fraction does not have to be in lowest terms, so it can be $1/2$ , $4/8$ , or $6/4$ .

On grid paper, Bajtosia drew a rectangle with height $p$ and width $q$ along the grid lines. Inside it, she drew a diagonal from the lower left corner to the upper right corner. Then, starting again from the lower left corner and ending at the upper right corner, she drew a zigzag below the diagonal. The pencil moves only right or up along the grid lines. The zigzag always goes as high as possible, but it never crosses the diagonal (it may touch it). In other words, Bajtosia always draws a segment up if that does not cross the diagonal. If an upward segment would cross the diagonal, she draws a segment to the right instead.

The pictures above show the case where Bajtosia's fraction is $2/3$ . The rectangle on the left has height 2 and width 3. The middle picture has the diagonal drawn as a dashed line. The picture on the right shows the matching zigzag.

Bajtosia is embarrassed to show you her drawing and won't even tell you her fraction until she is sure she drew it correctly. So she only gives you the pencil moves she made, starting from the lower left corner of the rectangle, as a string of characters: P for a segment to the right and G for a segment up.

Write a program that reads the description of the zigzag and decides whether Bajtosia's drawing is correct. If it is, the program must find the lowest-terms form of Bajtosia's fraction and print it.

Input

The first and only line of input contains a non-empty string made only of the letters P and G, describing the zigzag. The string contains at least one P and at least one G.

The length of the string does not exceed 1,000,000 characters.

Output

If the string is not a valid drawing of any fraction, print only one word: NIE.

Otherwise, print one line with two integers, the numerator and the denominator of Bajtosia's fraction, separated by / with no spaces.

The fraction must be printed in lowest terms, even if the original fraction was not.

Examples5

Example 1
Input
```
PPGPG
```
Expected output
```
2/3
```
Example 2
Input
```
PPGPPGPG
```
Expected output
```
3/5
```
Example 3
Input
```
PPGPPGPPGPPG
```
Expected output
```
1/2
```
Example 4
Input
```
PGGG
```
Expected output
```
3/1
```
Example 5
Input
```
PPGPPGGP
```
Expected output
```
NIE
```