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 codechef; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
public class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner s=new Scanner(System.in);
		String str=s.nextLine();
		int n=str.length();
		Stack<Integer> stc=new Stack<>();
		stc.push(-1);
		int max=0;
		int cnt=1;
		for(int i=0;i<n;i++)
		{
		    if(str.charAt(i)=='(')
		    stc.push(i);
		    else
		    {
		        if(stc.size()!=0)
		        {
		            stc.pop();
		        if(stc.size()!=0)
		        {
		            int len=i-stc.peek();
		            if(max==len)
		            cnt++;
		            if(max<len)
		            {
		                max=len;
		                cnt=1;
		            }
		        }else
		        {
		            stc.push(i);
		        }
		        }else
		        {
		            stc.push(i);
		        }
		    }
		}
	
		 System.out.println(max+" "+cnt);
	}
}