Marco ha trovato alcune antiche sequenze in un manoscritto. Ogni sequenza è composta da N pallini pieni o vuoti e rappresenta un brano da suonare al tamburello in N istanti consecutivi di tempo: all'i-esimo istante, il tamburello viene percosso se l'i-esimo pallino è pieno e, invece, non viene percosso se tale pallino è vuoto (1 <= i <= N).
Marco vuole capire se una data sequenza è periodica: in tal caso, vuole estrarne il periodo, ossia il più piccolo segmento iniziale che si ripete nel resto della sequenza. In altre parole, se P è la sequenza di pallini pieni e vuoti che rappresenta il periodo, allora la sequenza in input è periodica se può essere ottenuta concatenando P per due o più volte e tale P deve essere di lunghezza minima.
Per esempio, rappresentando con 1 ogni pallino pieno e con 0 ogni pallino vuoto, la sequenza periodica 101010101010 ha 10 come periodo e la sequenza 1010010100010100101000 ha 10100101000 come periodo. Invece, la sequenza 11011011 non è periodica. Aiutate Marco in questo compito, in modo che possa imparare a suonare velocemente tali brani per tamburello.
Il file input.txt è composto da due righe. La prima riga contiene un intero positivo N, che indica il numero di pallini nella sequenza. La seconda riga contiene una sequenza di interi 0 e 1, separati da uno spazio, dove 1 rappresenta un pallino pieno e 0 un pallino vuoto.
Il file output.txt è composto da una sola riga contenente l'intero 2 se la sequenza in input non è periodica. Altrimenti, se è periodica, la riga contiene la sequenza di 0 e 1, separati da uno spazio, che rappresenta il periodo P della sequenza fornita in input.
| File input.txt | File output.txt |
12 1 0 1 0 1 0 1 0 1 0 1 0 | 1 0 |
| File input.txt | File output.txt |
22 1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 0 | 1 0 1 0 0 1 0 1 0 0 0 |
| File input.txt | File output.txt |
8 1 1 0 1 1 0 1 1 | 2 |