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.io.IOException;
import java.io.StreamTokenizer;
import java.util.Scanner;
import java.util.Stack;


public class MainC {

	public static void main(String[] args) throws Exception {
		new MainC().run();
	}
	public void run() throws Exception {
		//		StreamTokenizer st = new StreamTokenizer(new InputStreamReader(System.in));
		Scanner in = new Scanner(System.in);
		char c[] = in.nextLine().trim().toCharArray();
		int n = c.length, max = -1, count = 1;
		Stack<Integer> stack = new Stack<Integer>();
		stack.add(0);
		for(int i=0; i<n; i++){
			if(c[i] == '('){
				stack.add(i+1);
			}
			else{
				if(!stack.isEmpty()){
					stack.pop();
					if(stack.isEmpty()){
						stack.add(i+1);
					}
					int cur = (i+1) - stack.peek();
					if(cur == max){
						count++;
					}
					if(cur > max){
						max = cur;
						count = 1;
					}
				}
			}
		}
		if(max == -1 || max == 0){max = 0; count = 1;}
		System.out.println(max + " " + count);
	}

	public int n, m;
	int nextInt(StreamTokenizer st) {
		try {st.nextToken();}
		catch (IOException e) {}
		return (int) st.nval;
	}
}