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 codeforces;

import java.io.*;
import java.util.*;

final public class LRBS {
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		Stack<Character> st = new Stack<Character>();
		for(int i=s.length()-1;i>=0;i--){
			st.push(s.charAt(i));
		}
		int bopen = 0;
		int bclose = 0;
		int len=0;
		int maxl = 0;
		int count = 0;
		int i=0;
		int j=0;
		for(i=0;!st.empty();i++){
			if(st.pop() == '('){
				bopen++;
				len++;
			}
			else{
				bclose++;
				len++;
			}
			if(bclose>bopen){
				len--;
				if(len>maxl){
					maxl=len;
					count=1;
				}
				else if(len==maxl && maxl>0)
					count++;
				len=0;
				bopen=0;
				bclose=0;
				j=i;
			}
		}
		
		if(bclose==bopen && bclose!=0){
			if(len==maxl)
				count++;
			else if(len>maxl){
				maxl=len;
				count=1;
			}
			System.out.println(maxl+" "+count);
			return;
		}
		
		bopen=0;
		bclose=0;
		len=0;
		for(int k=s.length()-1;k>j;k--){
			if(s.charAt(k)==')')
			{
				bclose++;
				len++;
			}
			else{
				bopen++;
				len++;
			}
			if(bopen>bclose){
				len--;
				if(len>maxl){
					maxl=len;
					count=1;
				}
				else if(len==maxl && maxl!=0){
					count++;
				}
				len=0;
				bopen=0;
				bclose=0;
			}
		}
//		if(bopen>=bclose && bclose>0){
//			if(2*bclose>maxl){
//				maxl=2*bclose;
//				count=1;
//			}
//			else if(2*bclose==maxl){
//				count++;
//			}		
//		}
		if(maxl==0){
			System.out.println("0 1");
			return;
		}
			System.out.println(maxl+" "+count);
	}
}