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.*;
public class A
{
      public static void main(String ar[])
      {
            Scanner s=new Scanner(System.in);
            char c[]=s.nextLine().toCharArray();   int count=0;
            int n=c.length;
            int a[]=new int[n];
            HashMap<Integer,Integer> hs=new HashMap<Integer,Integer>();
            for(int i=0;i<n;i++)
             if(c[i]=='(')
              a[i]=1;
             else
              a[i]=-1;
            
            Stack<Integer> st=new Stack<Integer>();
            int t=0,max=0;  int last=-1;
            for(int i=0;i<n;i++)
            {
               
               if(a[i]==1)
                st.add(i);
               else
               {
                     if(st.isEmpty())
                      last=i;
                     else
                      st.pop();
               
                if(st.isEmpty())
                 t=i-last;
                else
                t=i-Math.max(last,st.peek());
                if(t>max)
                {  max=t;  count=1;  }
                else if(t==max)
                {  count++;          }
               }
            }
            if(max==0)
             System.out.println("0 1");
            else
             System.out.println(max+" "+count);
      }
}