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 LongestRegularBracketSequence
{
	public Scanner in = new Scanner(System.in);
	public PrintStream out = System.out;

	public char[] v;
	public String s;
	public int n;
	
	public int best, cnt;
	public int[] mark;
	
	public void main()
	{
		best = 0; cnt = 1;
		
		s = in.next();
		v = s.toCharArray();
		n = v.length;
		mark = new int[n];
		
		int len, bal;
		
		len = 0; bal = 0;
		for(int i=0;i<n;++i)
		{
			if(v[i] == '(') ++bal;
			else --bal;
			
			++len;
			
			if(bal == 0)
			{
				if(len > best)
				{
					best = len;
					cnt = 1;
				}
				else if(len == best)
				{
					if(mark[i-(len-1)] < best) ++cnt;
				}
				
				mark[i-(len-1)] = Math.max(mark[i-(len-1)], len);
			}
			else if(bal < 0)
			{
				bal = 0;
				len = 0;
			}
		}
		
		bal = len = 0;
		for(int i=n-1;i>=0;--i)
		{
			if(v[i] == ')') bal++;
			else bal--;
			
			++len;
			
			if(bal == 0)
			{
				if(len > best)
				{
					best = len;
					cnt = 1;
				}
				else if(len == best)
				{
					if(mark[i] < len) ++cnt;
				}
				
				mark[i] = Math.max(mark[i], len);
			}
			else if(bal < 0)
			{
				bal = len = 0;
			}
		}
		
		out.println(best+" "+cnt);
	}//end public void main()

	public static void main(String[] args)
	{
		(new LongestRegularBracketSequence()).main();
	}
}