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;

public class CF5C {

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        char[] input = in.readLine().toCharArray();
        
        int length = 0;
        int n = 1;
        int balance = 0;
        int start = -1;
        
        for(int i = 0; i < input.length; ++i)
        {
            if(input[i] == '(')
            {
                ++balance;
            }
            else
            {
                --balance;
            }
            if(balance == 0)
            {
                if(length < i - start)
                {
                    length = i - start;
                    n = 1;
                }
                else if(length == i - start)
                {
                    ++n;
                }
            }
            else if(balance < 0)
            {
                start = i; 
                balance = 0;
            }
        }
        if(balance == 0)
        {
            System.out.println(length + " " + n);
            return;
        }
        balance = 0;
        int end = start;
        start = input.length;
        
        for(int i = start -1; i > end; --i)
        {
            if(input[i] == ')')
            {
                ++balance;
            }
            else
            {
                --balance;
            }
            if(balance == 0)
            {
                if(length < start - i)
                {
                    length = start - i;
                    n = 1;
                }
                else if(length == start - i)
                {
                    ++n;
                }
            }
            else if(balance < 0)
            {
                start = i; 
                balance = 0;
            }
        }
        System.out.println(length + " " + n);
        
    }

}