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.*;
import java.util.*;
 
 
 public class C5 {

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		PrintWriter pw = new PrintWriter(System.out);
		char []c = br.readLine().toCharArray();
		int max=0;
		int num=0;
		int a=0;
		int cc=0;
		
		for(int i=0;i<c.length;i++)
		{
			a=a+(c[i]=='('?1:-1);
			if(a>0)
				cc++;
			else
				if(a==0)
				{
					cc++;
					if(cc>max)
						{num=1;max=cc;}
					else
						if(cc==max)
							num++;
				}
				else
					{a=0;cc=0;}
		}
		
		int max2=0;
		int num2=0;
		int a2=0;
		int cc2=0;
		
		for(int i=c.length-1;i>=0;i--)
		{
			a2=a2+(c[i]=='('?-1:1);
			if(a2>0)
				cc2++;
			else
				if(a2==0)
				{
					cc2++;
					if(cc2>max2)
						{num2=1;max2=cc2;}
					else
						if(cc2==max2)
							num2++;
				}
				else
					{a2=0;cc2=0;}
		}
		if(max==0)
			num=1;
		if(max2>max)
		{
			pw.println(max2+" "+num2);
		}
		else
			if(max2==max)
			{
				pw.println(max2+" "+Math.max(num2, num));
			}
			else
		       pw.println(max+" "+num);
			
		
		
		
		
		pw.close();
	}

}