Problem J
Juggling

Ada Coleman bartending at the Savoy, circa 1920.

Ada the bartender wants to enhance her already impressive range of showmanship by incorporating juggling into her act. The first thing to learn is the siteswap notation for juggling patterns, also known as Cambridge notation.

The notation describes juggling patterns in which balls are thrown one at a time, alternating between hands, with one throw per beat. It consists of a sequence of nonzero digits, where the $i$th digit is $k$ if the bottle thrown at the $i$th beat is thrown again next at beat $i+k$. For example, if Ada throws a single bottle between her hands, the sequence is $1111111\cdots $:

The well-known cascade with three bottles corresponds to the sequence $333\cdots $,

and the three-ball shower is $515151\cdots $:

A more complicated three-ball pattern is described by the sequence $423423423\cdots $.

Not all digit sequences are valid: For example, a sequence starting with $432$ can’t be juggled—the first three balls would all have to be thrown at time $5$!

Some sequences, such as the above examples, are periodic. We call the shortest period of a sequence describing a valid juggling pattern minimal; the minimal forms of our examples are $1$, $3$, $51$ and $423$.

Input

Input consists of a nonempty string of digits between $1$ and $9$ of length at most $250\, 000$.

Output

Output VALID if the output is a valid minimal juggling pattern, and INVALID if not.

1

VALID

3

VALID

51

VALID

423

VALID

333

INVALID

42

VALID

423423

INVALID

432

INVALID

9

VALID