Printing Plate

Time limit1sMemory limit256 MB

Summary

Find the shortest plate that, pressed at every aligned position, leaves each fixed stripe in its own pure color.

Level: Medium6 of 10
Topics: Binary search, Sliding window, String
Solved: No attempts yet

Problem

A printing works in Byteotia took a large order for striped wallpaper. One sheet of wallpaper is a row of $n$ colored vertical stripes of equal width. The customer fixed the color of some stripes in advance and left the color of the remaining stripes to the printer.

The wallpaper is printed with a plate that prints several consecutive stripes at once. Each stripe of the plate has its own color, and the plate may be shorter than the wallpaper. If the plate has length $k$ , it is pressed at all $n - k + 1$ positions where its stripes line up exactly with stripes of the wallpaper, and every stripe of the plate is printed each time. One stripe of the wallpaper can therefore be printed more than once. If a stripe is printed in different colors, its final color is a mixture of those colors.

The printer wants the shortest plate that can print the whole wallpaper. A stripe whose color the customer fixed must come out in a pure color, with no other color mixed in. In other words, at every position of the plate that covers such a stripe, the plate stripe landing on it must have exactly the fixed color.

Input

The first line contains a string that describes the wallpaper. The string is made of uppercase Latin letters and asterisks (*). Different letters mean different stripe colors, and an asterisk means a stripe whose color the customer did not fix. The length $n$ of the string satisfies $1 \le n \le 1000000$ .

Output

Print one line with the minimum length $k$ of a plate that can print the requested wallpaper.

Note

If the wallpaper is the seven-stripe pattern A*B*B*A, the plate ABBBBA of length 6 prints it.

Examples5

Example 1
Input
```
A*B*B*A
```
Expected output
```
6
```
Example 2
Input
```
A
```
Expected output
```
1
```
Example 3
Input
```
*
```
Expected output
```
1
```
Example 4
Input
```
AAAAAAA
```
Expected output
```
1
```
Example 5
Input
```
AB
```
Expected output
```
2
```