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 longest_reg_bracket_seq 
{
	public static void main(String args[])throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String seq =  br.readLine();
		int n = seq.length();
		
		int [] d = new int [n];
		int [] c = new int [n];
		
		int [] maxno = new int [n+10];
		
		int max = 0;
		for (int i= 0; i<n ; i++)
		{c[i]=-1; d[i]=-1;}
		
		Stack <Integer> pos = new Stack<Integer>();
		for (int i = 0; i< n; i++)
		{
			if (seq.charAt(i)=='(')
				pos.push(i);
			else
			{
				if (pos.size()==0)
				{c[i] = -1; d[i] = -1;}
				
				
				else
				{
					d[i] = pos.peek();
					int l = i - d[i] + 1;
					if ((d[i]-1>=0)&&(seq.charAt(d[i]-1)==')')&&(c[d[i]-1] != -1))
						{l = i - c[d[i]-1] + 1;	c[i]=c[d[i]-1];}
					else
						c[i] = d[i];
					if (l >= max) 			{max =l;maxno[max]+=1;}
					pos.pop();
				}
			}
		}
		
		if (max == 0)
			System.out.println(0+" "+1);
		else
			System.out.println(max+" "+maxno[max]);
		
	}
}