You're given a string s consisting of letters 'a', 'b' and 'c'.

The matching function m_s( i ) is defined as the number of matching characters of s and its i-shift. In other words, m_s( i ) is the number of characters that are matched when you align the 0-th character of s with the i-th character of its copy.

You are asked to compute the maximum of m_s( i ) for all i ( 1 <= i <= |s| ). To make it a bit harder, you should also output all the optimal i's in increasing order.

Input

The first and only line of input contains the string s. 2 <= |s| <= 10⁵.

Output

The first line of output contains the maximal m_s( i ) over all i.

The second line of output contains all the i's for which m_s( i ) reaches maximum.

Example

Input:
caccacaa
Output:
4
3

Explanation:

caccacaa
   caccacaa

The underlined characters indicate the ones that match when shift = 3.