Problem J
Jonglieren

Ada Coleman hinter ihrer Theke im Savoy, cirka 1920.

Ada, die Barkeeperin, möchte ihre bereits beeindruckenden Showkünste weiter ausbauen, indem sie Jonglage in ihre Vorführung integriert. Ihr erstes Ziel ist es, die sogenannte Siteswap-Notation für Jongliermuster, auch bekannt als Cambridge-Notation, zu erlernen.

Diese Notation dient dazu, Jongliermuster zu beschreiben, bei denen die Flaschen abwechselnd von einer Hand zur anderen geworfen werden, mit einem Wurf pro Beat. Sie besteht aus einer Folge von Ziffern, wobei die $i$-te Ziffer gleich $k$ ist, falls die Flasche, die im $i$-ten Beat geworfen wurde als nächstes auf Beat $i+k$ geworfen wird. Zum Beispiel ist die Folge $1111111...$ das Muster, wenn Ada eine einzelne Flasche zwischen ihren Händen wirft:

Die bekannte 3-Flaschen Kaskade korrespondiert zu der Folge $333\cdots $,

und der 3-Flaschen Shower ist $515151\cdots $:

Ein kompliziertes Muster wird durch die Folge $423423423\cdots $ beschrieben.

Nicht alle Folgen sind hierbei valide: Zum Beispiel die Sequenz, die mit $432$ beginnt, kann nicht jongliert werden. Die drei Flaschen würden alle zu selben Zeit (auf Beat $5$) das nächste Mal geworfen werden.

Einige Folgen sind dabei periodisch. Die kürzeste Periode einer (validen) Folge wird hierbei als minimal bezeichnet. für die zuvor aufgezählten validen Folgen wären das $1$, $3$, $51$ and $423$.

Input

Die Eingabe besteht aus einem nicht-leeren String an Ziffern von $1$ bis $9$, bestehend aus höchstens $250\, 000$ Zeichen.

Output

Gib VALID aus, falls es sich um ein minimales Valides Jongliermuster handelt und INVALID falls nicht.

1

VALID

3

VALID

51

VALID

423

VALID

333

INVALID

42

VALID

423423

INVALID

432

INVALID

9

VALID