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:
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Vaibhav
 */
import java.io.*;
import java.util.*;
public class C5 
{
    public static void main(String args[])throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String s=br.readLine();
        if(s.indexOf('(')==-1)
            System.out.println("0 1");
        else
        {
            s=s.substring(s.indexOf('('),s.length());
            int n=s.length();
            int arr[]=new int[n+1];
            int dp[]=new int[n+1];
            s=" "+s;int c=0;
            char ch[]=new char[n+1];
            Arrays.fill(ch,'0');
            for(int i=1;i<=n;i++)
            {
                if(s.charAt(i)=='(')
                {
                    arr[++c]=i;
                }
                else
                {
                    if(c>0)
                    {
                        if(i-arr[c] == 1)
                        {
                            ch[arr[c--]]='.';
                            ch[i]='.';
                            dp[i]=dp[i-2]+2;
                        }
                        else
                        {
                            if(ch[i-1]=='.' && c>0)
                            {
                                if(ch[arr[c]+1]=='.')
                                {
                                    ch[i]='.';ch[arr[c]]='.';
                                    dp[i]=dp[i-1]+dp[arr[c]-1]+2;
                                    c--;
                                }
                            }
                        }
                    }
                }
                //System.out.println(dp[i]+" "+i);
            }
            int max=0,cou=1;
            for(int i=1;i<=n;i++)
            {
                if(dp[i]==max)
                    cou++;
                else
                {
                    if(dp[i]>max)
                    {
                        max=dp[i];
                        cou=1;
                    }
                }
            }
            if(max!=0)
                System.out.println(max+" "+cou);
            else
                System.out.println("0 1");
        }
    }
}