Problem: This is yet another problem dealing with regular bracket sequences.

We should remind you that a bracket sequence is called regular, if by inserting «+» and «1» into it we can get a correct mathematical expression. For example, sequences «(())()», «()» and «(()(()))» are regular, while «)(», «(()» and «(()))(» are not. 

You are given a string of «(» and «)» characters. You are to find its longest substring that is a regular bracket sequence. You are to find the number of such substrings as well.

Input

The first line of the input file contains a non-empty string, consisting of «(» and «)» characters. Its length does not exceed 106.

Output

Print the length of the longest substring that is a regular bracket sequence, and the number of such substrings. If there are no such substrings, write the only line containing "0 1".

Examples

Input

)((())))(()())


Output

6 2


Input

))(


Output

0 1

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Vector;

/**
 * Date: 19.02.2010
 * Time: 14:56:28
 *
 * @author Sergey Bankevich (Sergey.Bankevich@gmail.com)
 */
public class C5 {
    static BufferedReader in;

    public static void main( String[] args ) throws IOException {
        in = new BufferedReader( new InputStreamReader( System.in ) );
        char[] c = in.readLine().toCharArray();
        int r = 0;
        int cnt = 1;
        int[] left = new int[c.length];
        boolean[] isEnd = new boolean[c.length];
        int top = -1;
        for ( int i = 0; i < c.length; i ++ ) {
            char d = c[i];
            if ( d == '(' ) {
                top ++;
                if ( i > 0 && ! isEnd[i - 1] ) {
                    left[top] = i;
                }
            } else {
                if ( top >= 0 ) {
                    isEnd[i] = true;
                    if ( i - left[top] + 1 > r ) {
                        r = i - left[top] + 1;
                        cnt = 1;
                    } else if ( i - left[top] + 1 == r ) {
                        cnt ++;
                    }
                    top --;
                }
            }
            /*System.out.println( d + " " + top + " " + r + " " + cnt );
            for ( int j = 0; j < 4; j ++ ) {
                System.out.print( left[j] + " " );
            }                       
            System.out.println();*/
        }
        System.out.println( r + " " + cnt );
    }
}