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.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
public class MyClass
{
    public static void print(String str)
    {
        System.out.print(""+str);
    }
    public static void println(String str)
    {
        System.out.println(""+str);
    }
    public static void checkValid(String str,boolean valid[])
	{
	    int n=str.length();
	    Stack<Integer> s=new Stack<Integer>();
	    for(int i=0;i<n;i++)
	    {
	        char ch=str.charAt(i);
	        if(ch=='(')
	        {
	            s.push(i);
	        }
	        else
	        {
	            if(!s.isEmpty())
	            {
	                valid[i]=true;
	                valid[s.pop()]=true;
	            }
	        }
	    }
	}
	public static int globalCount;
	public static int longest(boolean valid[],int n)
	{
	    int count=0,maxCount=0;
	    for(int i=0;i<n;++i)
	    {
	        if(valid[i])
	        {
	            count++;
	            i++;
	            while(i<n&&valid[i])
	            {
	                count++;
	                i++;
	            }
	            if(count==maxCount)
	            {
	                globalCount++;
	            }
	            if(count>maxCount)
	            {
	                maxCount=count;
	                globalCount=1;
	            }
	            count=0;
	        }
	    }
	    return maxCount;
	}
    public static void func(String str)
    {
        int n=str.length();
		boolean valid[]=new boolean[n];
		for(int i=0;i<n;i++)
		{
		    valid[i]=false;
		}
		checkValid(str,valid);
// 		print("Valid: ");
// 		for(int i=0;i<n;++i)
// 		{
// 		    if(valid[i])
// 		    {
// 		        print("1");
// 		    }
// 		    else
// 		    {
// 		        print("0");
// 		    }
// 		}
// 		println("");
		globalCount=0;
		int max = longest(valid,n);
		if(max==0)
		{
		    println("0 1");
		}
		else
		{
		    println(max+" "+globalCount);
		}
    }
	public static void main (String[] args) throws java.lang.Exception
	{
	    Scanner s=new Scanner(System.in);
	    String str=s.next();
	    func(str);
	}
}