Function String

Interview

Time limit1sMemory limit1024 MB

Summary

Evaluate a prefix-notation string of f, g, and x, where x is 0, g adds 1, and f takes the smaller of two sub-strings, or print -1 if the string is malformed.

Level: Easy3 of 10
Topics: String, Stack
Solved: No attempts yet

Problem

A function string that evaluates to a single integer is defined as follows.

x is a function string. The string above evaluates to $0$ .
If S is a function string, then gS is also a function string. The string above evaluates to the value of S plus $1$ .
If S and T are function strings, then fST is also a function string. The string above evaluates to the smaller of the values that S and T evaluate to.

Input

The first line contains a string $S$ consisting only of f, g, and x. $(1 \leq |S| \leq 1\,000\,000)$

Output

On the first line, print the value of the string if it is a function string. Otherwise, print -1.

Examples3

Example 1
Input
```
fggxgx
```
Expected output
```
1
```
Example 2
Input
```
xxx
```
Expected output
```
-1
```
Example 3
Input
```
gggx
```
Expected output
```
3
```