Pozwól mi usłyszeć twój głos, opowiedz mi historie ze swojej podróży —
Zarówno o radosnych, jak i bolesnych wydarzeniach, a także o spotkaniach, które na zawsze zapisały się w twoim sercu.
Treść zadania
Dany jest napis $S$ długości $n$, którego pozycje są numerowane od $1$. Przez $S(i, j)=S_iS_{i+1}\cdots S_j$ oznaczamy podnapis napisu $S$ od znaku na pozycji $i$ do znaku na pozycji $j$.
Jeżeli niepusty napis $B$ jest jednocześnie prefiksem i sufiksem napisu $X$ oraz $|B|<|X|$, to nazywamy $B$ brzegiem napisu $X$, gdzie $|X|$ oznacza długość napisu $X$.
Początkowo znajdujesz się w podnapisie $S(1, n)$. Każdy skok wykonuje się następująco:
- W podnapisie, w którym obecnie się znajdujesz, wybierz podnapis $X$.
- Wybierz brzeg $B$ napisu $X$, spełniający warunek $2|B|\ge |X|$.
- Skocz do podnapisu odpowiadającego wystąpieniu $B$ jako prefiksu lub sufiksu napisu $X$, wybierając dowolną z tych dwóch możliwości.
Na przykład, gdy $S$ to aabaaba i znajdujesz się w $S(1, 7)$, możesz wybrać $X=S(2, 7)=$ abaaba. Jego brzeg aba ma długość równą dokładnie połowie $|X|$, więc możesz skoczyć do $S(2, 4)$ lub $S(5, 7)$.
Dla każdego $1\le i\le n$ wyznacz osobno największą liczbę skoków, które można wykonać, zaczynając w $S(1, n)$ i kończąc w $S(i, i)$. Jeżeli nie da się tam dotrzeć, odpowiedzią jest $-1$. Dozwolone jest niewykonanie żadnego skoku.
Dane zawierają wiele przypadków testowych.
Wejście
Pierwszy wiersz zawiera jedną liczbę całkowitą $T$, oznaczającą liczbę przypadków testowych.
Następnie podawane są kolejno przypadki testowe. Każdy przypadek testowy zajmuje jeden wiersz zawierający napis $S$.
Wyjście
Dla każdego przypadku testowego wypisz jeden wiersz zawierający $n$ liczb całkowitych. Liczba na pozycji $i$ ma oznaczać odpowiedź dla $S(i, i)$ (jeśli nie da się dotrzeć do $S(i, i)$, wypisz -1).
Przykład
Wejście 1
5 abbababbab bbabbaabbabbaaabab babbaaaaabaabaaabaaba baabaabaabaacaabaabaabaacaabaabaabaac bbaabaaaaabbbbbbbababaabaabaabbabababbbabbabbabbba
Wyjście 1
-1 2 2 -1 -1 -1 2 2 -1 -1 3 3 -1 3 3 2 2 3 3 -1 3 3 2 2 2 -1 -1 -1 -1 -1 1 1 4 4 4 4 4 -1 3 3 -1 3 3 3 -1 3 3 -1 -1 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 1 1 2 2 -1 4 4 4 4 4 6 6 6 6 6 6 6 -1 -1 -1 -1 3 3 -1 3 3 -1 3 3 1 1 -1 -1 -1 -1 -1 2 3 3 -1 3 3 -1 3 3 -1 3 3 2 -1
Uwagi
W pierwszym przypadku testowym $S=$ abbababbab, a jego prefiks i sufiks długości $5$ są równe abbab. Można wykonać dwa skoki w następujący sposób:
- Najpierw skocz do $S(1, 5)$, następnie wybierz $S(2, 3)=$ bb i skocz do $S(2, 2)$ lub $S(3, 3)$.
- Najpierw skocz do $S(6, 10)$, następnie wybierz $S(7, 8)=$ bb i skocz do $S(7, 7)$ lub $S(8, 8)$.
Tylko wtedy, gdy pierwszy skok prowadzi do jednego z tych dwóch wystąpień abbab, można wykonać kolejny skok. Ten kolejny skok może prowadzić wyłącznie do pojedynczego znaku, zatem największa liczba skoków dla każdej z tych czterech pozycji wynosi $2$.
Do pozostałych pozycji nie da się dotrzeć za pomocą skoków, więc odpowiedzią jest $-1$.
Przykład 2
Zobacz pliki wind2.in i wind2.ans w załącznikach. Ten przykład spełnia ograniczenia podzadania 3.
Przykład 3
Zobacz pliki wind3.in i wind3.ans w załącznikach. Ten przykład spełnia ograniczenia podzadania 5.
Przykład 4
Zobacz pliki wind4.in i wind4.ans w załącznikach. Ten przykład spełnia ograniczenia podzadania 6.
Przykład 5
Zobacz pliki wind5.in i wind5.ans w załącznikach. Ten przykład spełnia ograniczenia podzadania 8.
Ograniczenia
W tym zadaniu obowiązują odpowiednie zależności między podzadaniami.
| Podzadania | $n\le$ | $\sum n\le$ | Własność szczególna | Punkty |
|---|---|---|---|---|
| $1$ | $18$ | $500$ | Brak | $5$ |
| $2$ | $500$ | $14$ | ||
| $3$ | $5\times 10^3$ | $5\times 10^3$ | $21$ | |
| $4$ | $10^5$ | $10^5$ | $18$ | |
| $5$ | $2\times 10^5$ | $2\times 10^5$ | A | $15$ |
| $6$ | B | $13$ | ||
| $7$ | C | $2$ | ||
| $8$ | Brak | $12$ |
Własność szczególna A: istnieje niepusty napis $P$ taki, że $S$ jest prefiksem nieskończonego napisu okresowego $P^{\infty}$ oraz $|P|\le 10$.
Własność szczególna B: $S$ jest generowany losowo, to znaczy każdy znak napisu $S$ jest wybierany z rozkładem jednostajnym ze zbioru znaków o rozmiarze $\ge 2$.
Własność szczególna C: dla każdego $1\le i<n$ zachodzi $S_i\neq S_{i+1}$.
Dla wszystkich danych zachodzi $1\le n\le 2\times 10^5$, a suma długości napisów we wszystkich przypadkach testowych w jednym pliku wejściowym spełnia $\sum n\le 2\times 10^5$. Napis $S$ zawiera wyłącznie małe litery alfabetu angielskiego.