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.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int i  , count , num;
        String[] str;
        int[] dp = new int[10000001];

        while (in.hasNext()){
            str = in.next().split("");
            dp[0] = 0;
            count = 0;
            num = 1;

            for(i = 1 ; i < str.length ; i++){
                dp[i] = 0;

                if(i - dp[i - 1] - 1 >= 0 && str[i].equals(")") && str[i - dp[i - 1] - 1].equals("("))
                {
                    dp[i] = dp[i - 1] + 2;
                    if(i - dp[i - 1] - 2 >= 0 && dp[i - dp[i - 1] - 2] != 0)
                    {
                        dp[i] += dp[i - dp[i - 1] - 2];
                    }
                }
                if(count < dp[i]) {
                    count = dp[i];
                    num = 1;
                }
                else if(count == dp[i] && count != 0) num++;
            }

            System.out.println(count + " " + num);
        }
    }
}