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.sql.Array;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

public class longestRegularbracketSequence {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        String seq = sc.nextLine();

        printLongestBracketSeq(seq);
    }

    public static void printLongestBracketSeq(String seq){
        char[] seqArr = seq.toCharArray();
        int i;
        Stack<Integer> st = new Stack<>();

        int[] d = new int[seqArr.length];
        int[] c = new int[seqArr.length];
        int[] lengthOfMatched = new int[seqArr.length];
        for(i=0;i<seqArr.length;i++){
            d[i] = -1;
            c[i] = -1;
            lengthOfMatched[i] = 0;
        }
        for(i=0;i<seqArr.length;i++){
            if(seqArr[i]=='('){
                st.push(i);
            }else{
                if(st.isEmpty()){
                    continue;
                }else{
                    d[i] = st.peek();
                    st.pop();
                    lengthOfMatched[i] = i - d[i] +1;
                }
            }
            //System.out.println(st.toString());
        }

        for(i=0;i<c.length;i++){
           c[i] = d[i];
        }
        int maxLength = 0;
        for(i=0;i<c.length;i++){
            if(c[i] != -1 && seqArr[i]==')'){
                int k = c[i]-1;
                while(k>=0 && seqArr[k]==')' && c[k]!=-1){
                    c[i] = c[k];
                    k = c[k] - 1;
                }
                lengthOfMatched[i] = i  - c[i] +1;
                maxLength = Math.max(lengthOfMatched[i], maxLength);
            }
        }
        int count = 0;
        if(maxLength==0){
            count = 1;
        }else{
            for(i=0;i<lengthOfMatched.length;i++){
                if(lengthOfMatched[i]==maxLength){
                    count++;
                }
            }
        }


        System.out.println(maxLength+" "+count);

    }
}