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.*;
public class LongestDS {
public static void main(String[] args){
    Scanner in = new Scanner(System.in);
    Stack<Integer> stack = new Stack<Integer>();
    String s = in.nextLine();
    stack.push(-1);
    int length = 0;
    int a = 0;
    int b = 0;
    for(int i = 0 ;i < s.length();i++){
        if(s.charAt(i) == '(')
            stack.push(i);
        else if(stack.size() > 1){
            stack.pop();
            length = i - stack.peek();
            if(length > a){
                a = length;
                b = 1;
            }
            else if (length == a){
                b += 1;
            }
        }
        else{
            stack.pop();
            stack.push(i);
        }           
    }
    if(a == 0 && b == 0){
        System.out.println(0 + " "+1);  
        return;
    }
    System.out.println(a + " "+b);
}
}