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.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;


public class Main {


		public static void main(String[] args) throws IOException {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
			String input = br.readLine();
		    int n = input.length();    
	        // Create a stack and push -1 as initial index to it. 
	        Stack<Integer> stk = new Stack<>(); 
	        stk.push(-1); 
	       
	        // Initialize result 
	        int result = 0; 
	        int total = 0;
	       
	        // Traverse all characters of given string 
	        for (int i=0; i<n; i++) 
	        { 
	            // If opening bracket, push index of it 
	            if (input.charAt(i) == '(') 
	              stk.push(i); 
	       
	            else // If closing bracket, i.e.,str[i] = ')' 
	            { 
	                // Pop the previous opening bracket's index 
	                stk.pop(); 
	       
	                // Check if this length formed with base of 
	                // current valid substring is more than max  
	                // so far 
	                if (!stk.empty()) {
	                	if (i - stk.peek() > result) {
	                		total = 1;
	                	}
	                	else 
	                		if(result == i - stk.peek())
	                			total++;
	                    result = Math.max(result, i - stk.peek()); 
	                }
	       
	                // If stack is empty. push current index as  
	                // base for next valid substring (if any) 
	                else {
	                	stk.push(i);

	                }
	            } 
	        } 
	       if(total==0)
	    	   System.out.println("0 1");
	       else
	    	   System.out.println(result+" "+total); 
			bw.close();
			br.close();
	    } 

}