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.io.*;
import java.util.*;
public class Solution
{
    public static void main(String ag[])
    {
        Scanner sc=new Scanner(System.in);
        int i,j,k;
        char A[]=sc.next().toCharArray();
        int N=A.length;
        Stack<Integer> s=new Stack<>();
        int dp[]=new int[N];
        for(i=0;i<N;i++)
        {
            if(A[i]==')')
            {
                if(!s.isEmpty())
                {
                    int id=s.pop();
                    if(id-1>=0)
                    dp[i]=i-id+1+dp[id-1];
                    else 
                    dp[i]=i-id+1;
                }
            }
            else 
            {
                s.push(i);
            }
        }
        int freq[]=new int[N+1];
        for(i=0;i<N;i++)
        freq[dp[i]]++;
        
        int ans=0;
        int len=0;
        int cnt=1;
        for(i=N;i>0;i--)
        {
            if(freq[i]>0)
            {
                len=i;
                cnt=freq[i];
                break;
            }
        }
        System.out.println(len+" "+cnt);
    }
}