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 com.sun.swing.internal.plaf.basic.resources.basic_es;

import java.io.*;
import java.util.Stack;

public class LongestRegularBracketSequence {
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter printWriter = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    public static void main(String[] args) throws IOException{
         char[] sequence = bufferedReader.readLine().toCharArray();
//         char[] sequence = "()((()(()(())()()())((()(())()(()()()()))()(())()(((()())()(()((())()(())(()))".toCharArray();
//            char[] sequence = "))(".toCharArray();
        int max = 0;
        int num = 0;
        int cur = 0;
        int i = 0;
        Stack<Integer> stack = new Stack<Integer>();
        int base = -1;
        while (i < sequence.length) {
            if(sequence[i] == '(') {
                stack.push(i);
            }
            else {
                if(stack.isEmpty()) { // invalid
                    base = i;
                } else {
                    stack.pop();
                    if(stack.isEmpty()) {
                        cur = i - base;

                    } else {
                        cur = i - stack.peek();
                    }
                    if(cur > max) {
                        max = cur;
                        num = 1;
                    } else if (cur == max) {
                        num++;
                    }

                }

            }
            i++;
        }


        if(max == 0) {
            printWriter.println("0 1");

        } else {
            printWriter.println(max + " " + num);
        }

        printWriter.flush();
        printWriter.close();







    }
}