Surprising String

Interview

Time limit2sMemory limit128 MB

Summary

For each string, check for every gap size whether all pairs of letters at that fixed distance are distinct, and report if the string is 'surprising'.

Level: Easy3 of 10
Topics: String, Brute force, Implementation
Solved: No attempts yet

Problem

A string S made only of uppercase English letters is given. For an integer D, a D-pair of S is formed by writing in order the two letters at positions i and i + D + 1; exactly D letters lie between them.

If the length of the string is N, then D is defined from 0 through N - 2. For a fixed D, S is D-unique if all of its D-pairs are distinct. If S is D-unique for every possible D, then S is a surprising string.

Given several strings, determine whether each string is surprising.

Input

Each line contains one string made only of uppercase English letters. The length of each string is at most 80. The last line contains a single *, which must not be processed. The input has at most 101 lines including the final line.

Output

For each input string S, print one line. If S is surprising, print S is surprising. Otherwise, print S is NOT surprising.

Examples1

Example 1

Input

ZGBG
X
EE
AAB
AABA
AABB
BCBABCC
*

Expected output

ZGBG is surprising.
X is surprising.
EE is surprising.
AAB is surprising.
AABA is surprising.
AABB is NOT surprising.
BCBABCC is NOT surprising.