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.io.*;
public class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
//		int t=Integer.parseInt(br.readLine());
//		while(t-->0){
			String s=br.readLine();
			int max=0;
			int temp=0;
			Stack st=new Stack();
			int arr[]=new int[s.length()];
			for(int i=0;i<s.length();i++){
				if(s.charAt(i)=='('){
					st.push(i);	
				}else{
					if(!st.empty()){
						int o=(Integer)st.peek();
						char c=s.charAt(o);
		//				System.out.println(c);
						if(c=='('){
							temp+=2;
							arr[i]=1;
							arr[(Integer)st.pop()]=1;
					 

						}
					}
				}		
			}
			int count=0;
			for(int i=0;i<s.length();i++){
				temp=0;
				while(i<s.length()){
					if(arr[i]==1)
						temp+=1;
					else
						break;
					i+=1;
				}
				if(temp>=max){
					if(temp==max){
						count+=1;
					}else{	
					max=temp;
					count=1;
					}

				}
			}
			if(max==0)
				count=1;
			System.out.println(max+" "+count);
//		}
	}	
}