Special

Time limit0.4sMemory limit1024 MB

Summary

Find the longest substring with all distinct characters and print its length, start index, and the substring itself, preferring the rightmost one.

Level: Easy3 of 10
Topics: Sliding window, String, Two pointers, Hash map
Solved: No attempts yet

Problem

You are given a string $s$ made of standard printable characters (lowercase and uppercase Latin letters, digits, and punctuation marks, which occupy positions 33 through 126 in the ASCII table). A substring, consisting of characters placed consecutively in the given string, is called special if it contains no two equal characters. Write a program strange that reads the given string $s$ and finds the longest special substring.

Input

The given string $s$ is written on the standard input.

Output

Your program must print on the first line of the standard output two integers (separated by exactly one space): the length of the sought longest special substring and the position in the given string (counted from zero) where the special substring begins. On the second line of the standard output, your program must print the sought longest special substring. When the given string contains more than one longest special substring, your program must print the one found among them that is located rightmost in the given string.

Constraints

Constraint: the length of the given string is between 1 and 20 000 000 characters.

Examples1

Example 1
Input
```
abcaacxaa
```
Expected output
```
3 5
cxa
```