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 static java.lang.Math.*;

public class C {
	public static void p(Object... o){System.out.println(Arrays.deepToString(o));}
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		HashMap<Integer,Integer> lastSeen = new HashMap<Integer,Integer>();
		HashMap<Integer,Integer> firstSeen = new HashMap<Integer,Integer>();
		String S = sc.nextLine();
		int at = 0;
		int ans = 0;
		int count = 0;
		for(int i = 0; i < S.length();i++){

			if(!firstSeen.containsKey(at))
				firstSeen.put(at,i);
			if(S.charAt(i) == '(')
				at++;
			else{
				at--;
//				p(i,at,lastSeen,firstSeen);
				if(lastSeen.containsKey(at-1)){
					int len = i-lastSeen.get(at-1)-1;
//					p("\t",len);
					if(len > ans){
						ans = len;
						count = 1;
					}else if(len == ans)
						count++;
				}else if(firstSeen.containsKey(at)){
					int len = i-firstSeen.get(at)+1;
//					p("\t",len);
					if(len > ans){
						ans = len;
						count = 1;
					}else if(len == ans)
						count++;
				}
			}
			lastSeen.put(at,i);
		}
		if(ans == 0)
			count = 1;
		System.out.println(ans+" "+count);
	}
}