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.BufferedReader;

import java.io.IOException;

import java.io.InputStream;

import java.io.InputStreamReader;

import java.util.Arrays;

import java.util.Collections;

import java.util.Comparator;

import java.util.StringTokenizer;







public class A {

    public static void main(String[] args) throws IOException {
        Reader.init(System.in);

        Stack S = new Stack();
        S.push(-1);
        char[] A = Reader.next().toCharArray();
        int ans = 0;
        int counter = 0;
        for(int i=0;i<A.length;i++){
            if(A[i] == '('){
                S.push(i);
            }
            else{
                S.pop();
                if(S.top>=0) {
                    if((i-S.a[S.top])>ans){
                    ans = (i-S.a[S.top]);
                    counter =1;
                    }
                    else if((i-S.a[S.top])==ans){
                        counter++;
                    }

                }
                else{
                    S.push(i);
                }
            }
        }
        if (counter==0){counter++;}
        System.out.println(ans + " " + counter);
    }
}
class Reader {



    static BufferedReader reader;

    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */

    static void init(InputStream input) {

        reader = new BufferedReader(

                new InputStreamReader(input) );



        tokenizer = new StringTokenizer("");

    }



    static String nextToken() {

        while (tokenizer == null || !tokenizer.hasMoreTokens()) {

            try {

                tokenizer = new StringTokenizer(reader.readLine());

            } catch (IOException e) {

                throw new RuntimeException(e);

            }

        }

        return tokenizer.nextToken();

    }



    /** get next word */

    static String next() throws IOException {



        while ( ! tokenizer.hasMoreTokens() ) {



            //TODO add check for eof if necessary

            tokenizer = new StringTokenizer(

                    reader.readLine() );

        }

        return tokenizer.nextToken();

    }



    static int nextInt() throws IOException {



        return Integer.parseInt( next() );



    }



    static double nextDouble() throws IOException {

        return Double.parseDouble( next() );

    }



    static long nextLong() {

        return Long.parseLong(nextToken());

    }

}

class Stack{
    int max = 2000000;
    int[] a = new int[max];
    int top=-1;

    void push(int x){
        a[++top] = x;
    }
    void pop(){
        if (top>=0){top--;}
    }
}