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:
//package codeforce;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Problem5C {

	public static void main(String[] args) throws java.lang.Exception {
		BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
		char[] parens = buffer.readLine().toCharArray();
		
		int max =0;
		int max_count =0;
		int itr =0;		
		int bal=0;
		
		for( int i=0; i<parens.length; i++ ){
			if(parens[i] == '(') bal++;
			else bal--;
			
			if(bal==0){
				if(i-itr > max){
					max = i-itr;
					max_count = 1;
				} else if (i-itr == max){
					max_count++;
				}
			}else if(bal < 0){
				itr = i+1;
				bal = 0;
			}
		}
		
		//Go from other direction
		int max2 =0;
		int max2_count=0;
		bal =0;
		itr = parens.length-1;
		
		for( int i=parens.length-1; i>0; i--){
			if(parens[i] == '(') bal++;
			else bal--;
			
			if(bal==0){
				if(itr-i > max2){
					max2 = itr-i;
					max2_count = 1;
				} else if (itr-i == max2){
					max2_count++;
				}
			}else if(bal > 0){
				itr = i-1;
				bal = 0;
			}
		}
		max = Math.max(max, max2);
		max_count = Math.max(max_count, max2_count);
		
		if(max_count ==0)
			System.out.println("0 1");
		else
			System.out.println(max+1+" "+max_count);
	}
}