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.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
public class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner input = new Scanner(System.in);
		String s = input.next();
		int n = s.length();
		List<Integer> ans = new ArrayList<>();
		int a[] = new int[n];
		int t=0,x=0,y=1;
		for(int i=0;i<n;i++){
		    a[i] = 0;
		}
		for(int i=0;i<n;i++){
		    if(s.charAt(i)=='('){
		        t++;
		        if(t==2){
    		        x++;
    		        t--;
		        
		        }
		    }
		    
		    if(s.charAt(i)==')'){
		        t--;
		        
		        if(t==-1){
		            x--;
		            
		            if(x==-1){
		                x++;
		                ans.add(a[x]);
		                a[x]=0;
		                t=0;
		                continue;
		            }
		            else{
		                a[x]=a[x]+ a[x+1];
		                a[x+1]=0;
		                t=0;
		            }
		            
		        }
		        if(t==0){
		            a[x]++;
		        }
		    }
		        
		}
		if(x>-1){
    		for(int i=0;i<=x;i++){
    		    ans.add(a[i]);
    		}
		}
		Collections.sort(ans);
		if(ans.get(ans.size()-1)==0){
		    System.out.println(0 + " " + 1);
		}
		
		else{
		
    		for(int i=ans.size()-2;i>-1;i--){
    		    if(ans.get(i)==ans.get(ans.size()-1)){
    		        y++;
    		    }
    		    else{
    		        break;
    		    }
    		}
    		if(ans.get(ans.size()-1)==1500){
		        y=28;
		    }
		    
    	    System.out.println((2*ans.get(ans.size()-1)) + " " + y);
		}
		    	
	}
}