Description
Megumin finally opened the old ruin, and inside she found a spell book that explains how to measure the power of a spell. According to the book, the letter with the largest ASCII code becomes the core of the spell, with power equal to the square of its ASCII code. The letters to the left of the core add their power to it, while the letters to the right of the core subtract their power from it. Given a spell consisting of lowercase English letters, help Megumin compute its power , defined recursively as follows:
- denotes the length of , and denotes the ASCII code of character . When , is the ASCII code of the only character in .
- is the character in with the largest ASCII code. If several characters share the largest ASCII code, is the leftmost one (the one with the smallest index).
- and are obtained by splitting at :
- is the substring to the left of .
- is the substring to the right of .
- Neither nor contains itself, and either of them may be empty.
For example, if the spell is , the letter with the largest ASCII code is n, which appears at indices 2 and 4 (0-indexed). is the leftmost one, at index 2:
P("banana") = P("ba") + ASCII('n')^2 - P("ana")
P("ba") = P("") + ASCII('b')^2 - P("a") = 0 + 9604 - 9409 = 195
P("ana") = P("a") + ASCII('n')^2 - P("a") = 9409 + 12100 - 9409 = 12100
P("banana") = 195 + 12100 - 12100 = 195
Input
A single line containing the string .
Constraints
- consists only of lowercase English letters (
a–z).
Subtasks
- Subtask 1 (Testcase 1-5): All characters in are distinct.
- Subtask 2 (Testcase 6-10): No additional constraints.
Output
Output a single integer, the power . Note that the answer may be negative.