Problem Description

Xiao P and Xiao B like playing games. They found skip. skip told them about the following game:

• There is a string $S$ consisting of lowercase letters. When the game starts, it is the string $S_0$ given by skip. The game scores points for Xiao P and Xiao B, and initially both of their scores are $0$.
• Xiao P and Xiao B take turns operating on this string, with Xiao P moving first. On each turn, the current player can do the following:
  • Choose a non-empty prefix of $S$ (it may be $S$ itself), gain points equal to the number of occurrences of this prefix in $S$, and then delete this prefix from $S$.
• If after some operation $S$ becomes empty, the game ends.

To help you better understand the rules, consider the following example:

• Initially, $S_0 = ababa$.
• Xiao P chooses the prefix $a$ of $ababa$, gains 3 points, and $S$ becomes $baba$.
• Xiao B chooses the prefix $ba$ of $baba$, gains 2 points, and $S$ becomes $ba$.
• Xiao P chooses $ba$, gains 1 point, the string becomes empty, and the game ends. Finally, Xiao P gets 4 points and Xiao B gets 2 points.

Xiao P wants to maximize (Xiao P's score minus Xiao B's score), while Xiao B wants to minimize this value. They want to know, assuming both players are perfectly smart, what the final value of (Xiao P's score minus Xiao B's score) will be.

Input Format

Read from standard input.

The input contains only one line: a string $S_0$ consisting of lowercase letters.

Output Format

Write to standard output.

Output one integer, representing the value of (Xiao P's score minus Xiao B's score) when the game ends, assuming both players are perfectly smart.

ababa

2

Hint

Sample 1 Explanation

The optimal strategies of Xiao P and Xiao B are the strategy given in the problem description.

Subtasks

Let $n$ be the length of the string $S$. For all testdata, $1 \le n \le 10^6$, and the string $S$ consists of lowercase letters.

Translated by ChatGPT 5