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 CodeForces5C {

	public static void main(String[] args) {
		Scanner read = new Scanner(System.in);
		char[] v = read.nextLine().toCharArray();
		int[] val = new int[v.length];
		int n = v.length;
		int i;
		//int j;
		int max=0, contorMax=0;
		//varianta 1
		/*
		for(i=n-1;i>=0;i--){
			if(v[i]==')'){
				continue;
			}
			int sum=0;
			for(j=i;j<n;j++){
				if(v[j]=='('){
					sum++;
				}
				else{
					sum--;
				}
				if(sum<=0){
					break;
				}
			}
			if(sum==0){
				val[i]=j-i+1;
				if(j+1<n){
					val[i]+=val[j+1];
				}
			}
			else{
				continue;
			}
			if(val[i]>=max){
				if(val[i]==max){
					contorMax++;
				}
				else{
					contorMax=1;
					max=val[i];
				}
			}
		}
		*/
		//varianta 2
		for(i=n-1;i>=0;i--){
			if(v[i]=='('){
				int sum=1;
				while(i+sum<n){
					if(v[i+sum]=='('){
						if(val[i+sum]!=0){
							sum+=val[i+sum];
						}
						else{
							sum=1;
							break;
						}
					}
					else{
						sum++;
						break;
					}
				}
				if((sum&1)==1){
					continue;
				}
				val[i]=sum;
				if(i+sum<n){
					val[i]+=val[i+sum];
				}
				if(val[i]>=max){
					if(val[i]==max){
						contorMax++;
					}
					else{
						contorMax=1;
						max=val[i];
					}
				}
			}
		}
		/*
		for(i=0;i<n;i++){
			System.out.print(val[i]+" ");
		}
		System.out.println();
		//*/
		if(max==0){
			contorMax=1;
		}
		System.out.println(max+" "+contorMax);
		read.close();
	}

}

/*
Tests:
(()(()))()(()(())))
answer: 18 1

(()(())))(()(())))
answer: 8 2

(()())()(())()()())())()((()(()(())()()())((()(())()(()()()()))()(())()(((()())()(()((())()(())(()))
answer 28 1

)((())))(()())
answer: 6 2
*/