Problem Description

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, 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.

Input Format

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

Output Format

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

ababa

3

bbababaabaaabaaaab

23

Hint

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