P6114 [Template] Lyndon Decomposition

This is a template problem. Given a string $s$ consisting of lowercase English letters, split it into several parts $s = s_1 s_2 s_3 \cdots s_m$, such that each $s_i$ is a [Lyndon Word](https://en.wikipedia.org/wiki/Lyndon_word), and $\forall 1 \le i < m: s_i \ge s_{i+1}$. Output the positions of the right endpoints of the lengths of the strings from $s_1$ to $s_m$. The positions are numbered from $1$ to $n$. A string $s$ is a $\text{Lyndon Word}$ if and only if $s$ is the smallest string among all its suffixes. To reduce the output size, you only need to output the XOR of all right endpoints.

One line containing a string $s$ of length $n$, consisting only of lowercase English letters.

One line containing an integer, representing the XOR of all right endpoints.

The answer for the first sample is `2 4 5`. The answer for the second sample is `1 2 4 6 9 13 18`. - For $20\%$ of the testdata, $1 \le n \le 1000$ is guaranteed. - For $100\%$ of the testdata, $1 \le n \le 5 \times 10^6 + 1$ is guaranteed. Translated by ChatGPT 5