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.Deque;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * @author vstepanov on 3/29/2017.
 */
public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
           String seq = in.next();
//        String[] ss = new String[]{
//            ")((())))(()())",
//            "))(",
//            "()(())()",
//            "((((()(((",
//            "))))()())))",
//            "(()())()(())()()())())()((()(()(())()()())((()(())()(()()()()))()(())()(((()())()(()((())()(())(()))",
//            ")(()(((((())))))(((()))))))((()(((((((())())()))))((((((((())))((((((())))))(()((((()))))(()))))))))",
//            "())(((((())())((((()))(())))())())(((()(()()()())(())()))((()(())())()()))()(()())))))(()))((())(((("
//        };
//        for (String seq : ss) {
            Deque<IL> queue = new LinkedList<>();
            for (int j = 0; j < seq.length(); j++) {
                char e = seq.charAt(j);
                if (e == ')') {
                    IL nil = null;
                    boolean close = false;
                    while (queue.size() > 0) {
                        IL il = queue.pop();
                        if (il.l == 0) {
                            if (!close) {
                                int l = nil == null ? 0 : nil.l;
                                nil = new IL(il.i, l + 2);
                                close = true;
                            } else {
                                queue.push(il);
                                break;
                            }
                        } else {
                            if (nil == null) {
                                nil = il;
                                continue;
                            }
                            if (il.i + il.l == nil.i) {
                                nil = new IL(il.i, nil.l + il.l);
                            } else {
                                queue.push(il);
                                break;
                            }
                        }
                    }
                    if (nil != null) queue.push(nil);
                } else {
                    queue.push(new IL(j, 0));
                }
            }
            int ml = 0;
            int li = 0;
            for (IL il : queue) {
                if (il.l > ml) {
                    ml = il.l;
                    li = 1;
                } else if (il.l == ml) li++;
            }
            if (ml > 0) System.out.println(ml + " " + li);
            else System.out.println("0 1");

        }
    }

    static class IL {
        int i,l;

        public IL(int i, int l) {
            this.i = i;
            this.l = l;
        }
    }
}