Transform to a Uniform String

You are given a string s consisting only of the characters a and b. Your task is to determine whether it is possible to transform s into a string where all characters are identical (all a's or all b's) by removing at most one contiguous substring from it.

More formally, let the input string be s of length n. You are allowed to remove a substring s[i...j] (where 0 ≤ i ≤ j < n) at most once. After removal, the remaining parts, when concatenated, should form a string that has all identical characters. The challenge is to determine whether such a removal is possible.

In terms of transitions, you can think of it using the following concept: A transition happens when adjacent characters differ, i.e. when s[i] != s[i-1]. The removal operation will eliminate at most two transitions. In other words, if the total number of transitions is at most 2 (i.e. \leq 2), then the answer is True; otherwise, it is False.

Note that if the string is already uniform (i.e. all characters are the same), the answer is naturally True.

Example:

• For s = "aaabbb", the answer is True.
• For s = "abab", the answer is False.

inputFormat

The input is provided via stdin and consists of a single line containing the string s (only characters a and b are present in the string).

Constraints:

• 1 ≤ |s| ≤ 10⁵

outputFormat

Output to stdout a single line with either True or False. Print True if it is possible to obtain a uniform string by removing at most one contiguous substring, otherwise print False.

## sample

aaabbb

True