Problem J
Jonglering

Ada Coleman, bartender ved Savoy, omtrent 1920.

Ada vil udvide sit betragtelige repertoire af spektakulære bartenderfærdigheder ved at jonglere med flasker. Det første at lære er siteswap-notationen for jongleringsmønstre, også kendt som Cambridge-notationen.

Notationen beskriver jongleringsmønstre, hvor flasker kastes en ad gangen, skiftevis mellem hænderne, med ét kast per taktslag. Den består af en cifferfølge, hvis $i$te ciffer er $k$, hvis flasken kastet på det $i$te taktslag kastes igen næste gang på taktslaget $i+k$. Hvis Ada fx kaster en enkelt flaske mellem sine hænder, er sekvensen $1111111\cdots $:

Den velkendte kaskade med tre flasker svarer til sekvensen $333\cdots $:

Tre-flaske-mønstret $515151\cdots $ kaldes shower:

Et mere kompliceret mønster med tre flasker beskrives af sekvensen $423423423\cdots $:

Ikke alle ciffersekvenser er gyldige: For eksempel kan en sekvens, der starter med $432$, ikke jongleres, idet de første tre flasker alle skulle kastes på taktslag $5$!

Nogle sekvenser, som eksemplerne ovenfor, er periodiske. Vi kalder den korteste periode af en sekvens, der beskriver et gyldigt jongleringsmønster, for minimal; de minimale former for vores eksempler er $1$, $3$, $51$ og $423$.

Indlæsning

Indlæsnignen består af en ikke-tom streng af cifre mellem $1$ og $9$ med en længde på højst $250\, 000$.

Udskrift

Skriv »VALID«, hvis indlæsningen er en gyldig minimal jongleringssekvens, og »INVALID« ellers.

1

VALID

3

VALID

51

VALID

423

VALID

333

INVALID

42

VALID

423423

INVALID

432

INVALID

9

VALID