Uolevi recently created a new programming language. The programming language has only the following three functions for manipulating strings:

new (c) - takes a character $c$ and creates a string that consists of a single character $c$.

expand (S, c) - takes a string $S$ and a character $c$ and creates the string $ScS$.

reverse (S) - reverses the string $S$.

Your task is to find out if a given string could have been created using Uolevi's programming language.

Input

The only line of input contains one string of length $n$. The string consists of lowercase english letters.

Output

Output 10-4 if the string could have been created by Uolevi's programming language and QAQ otherwise.

Constraints

• $1 \le n \le 2000$

Examples

Input:

abacaba

Output:

10-4

Input:

uolevi

Output:

QAQ