Lyndon Word Partition

This is a template problem.

You are given a string \( s \) consisting of lowercase English letters. You need to split \( s \) into several parts \( s=s_1s_2s_3\cdots s_m \) such that every \( s_i \) is a Lyndon Word and \( s_i \ge s_{i+1} \) for all \( 1\le i < m \). A string \( s \) is called a Lyndon Word if and only if it is the smallest among all of its suffixes in lexicographical order.

For each part, define its end position as the index of its last character (positions are numbered from 1 to \( n \)). To reduce the output size, you only need to output the bitwise XOR of all these end positions.

Note: The factorization into Lyndon words in non-increasing order is unique due to the Chen–Fox–Lyndon theorem.

Input/Output Format: See below.

inputFormat

The input consists of a single line containing the string \( s \) composed only of lowercase English letters.

\( 1 \leq |s| \leq 10^6 \)

outputFormat

Output a single integer, which is the XOR of all the right endpoint positions of the Lyndon word factors of \( s \).

sample

a

1