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.io.*;
public class Main
{
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }
    static class Pair implements Comparable<Pair>
    {
        int f,s;
        Pair(int f,int s)
        {
            this.f=f;
            this.s=s;
        }
        public int compareTo(Pair p)
        {
            return this.f-p.f;
        }
    }
    public static void main(String args[])
    {
        FastReader fs=new FastReader();
        PrintWriter pw=new PrintWriter(System.out);
        char c[]=fs.nextLine().toCharArray();
        int n=c.length;
        int d[]=new int[n];
        TreeMap<Integer,Integer> tmap=new TreeMap<>();
        Stack<Character> st=new Stack<>();
        for(int i=0;i<n;i++)
        {
            if(c[i]=='(')
            st.push('(');
            if(c[i]==')'&&i-1>=0)
            {
                if(!st.isEmpty())
                {
                    if(c[i-1]==')')
                    {
                        d[i]+=d[i-1]+2;
                        if(i-2-d[i-1]>=0)
                        d[i]+=d[i-2-d[i-1]];
                    }
                    else
                    {
                        if(i-2>=0)
                        d[i]+=d[i-2]+2;
                        else
                        d[i]=2;
                    }
                    st.pop();
                    tmap.put(d[i],tmap.getOrDefault(d[i],0)+1);
                }
            }
        }
        if(tmap.isEmpty())
        pw.println("0 1");
        else
        pw.println(tmap.lastKey()+" "+tmap.get(tmap.lastKey()));
        pw.flush();
        pw.close();
    }
}