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.Arrays;
import java.util.Scanner;
import java.util.Stack;

/**
 *
 * @author 753617
 */
public class Bseq {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
     Scanner in = new Scanner(System.in);
 String i=" "+in.nextLine();
    boolean b[] = new boolean[i.length()];
    Stack<Integer> s= new Stack<Integer>();
        //(())
        int F[]= new int[i.length()];
        Arrays.fill(F, 0);
        int size=0;
        int max=0;
    for(int j=1; j<=i.length()-1; j++)
    {
            
            if((i.charAt(j)=='('))
            {
                
                s.push(j);
            }
                      
            else if(!s.isEmpty()){
                F[0]=0;
                int k= s.pop();
               
                F[j]=(j-k)+1+F[k-1];
            
                    
                
            }
                     
                      
        }
        
        
       
   //    System.out.println(Arrays.toString(F));
  int count=0;
  max=0;
  int c=0;    
for(int l =0; l<F.length; l++)
{
    if(F[l]>max)
    {
        max=F[l];
    }
}

for(int l=0; l<F.length; l++){
    
  if(max!=0){
    count=(F[l]==max)?++count:count;
    
}
  else{
      break;
  }}
count=count>0?count:1;   
        
     System.out.println(max+" "+count);
    }

}