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.InputStreamReader;
import java.util.Stack;

public class LRBS {

    private static int depth = 0;

    static class Element {
        int val;
        int depth;

        Element(int val, int depth) {
            this.val = val;
            this.depth = depth;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        solve(br.readLine());
    }

    private static void solve(String string) {
        depth = 0;
        Stack<Character> stack = new Stack<>();
        Stack<Element> elements = new Stack<>();
        for (int i = 0; i < string.length(); i++) {
            if (string.charAt(i) == '(') {
                en(stack);
            } else {
                if (stack.isEmpty()) {
                    if (!elements.isEmpty() && elements.peek().depth != -1) {
                        elements.push(new Element(0, -1));
                    }
                } else {
                    de(stack, elements);
                }
            }
        }
        calc(elements);
    }

    private static void calc(Stack<Element> elements) {
        int count = 0;
        int max = 0;
        int pd = -2;
        int mc = 0;
        while (!elements.isEmpty()) {
            Element pop = elements.pop();
            if (pd == -2 || pd == pop.depth) {
                count += pop.val;
            } else {
                if (count > max) {
                    max = count;
                    mc = 1;
                } else if (count == max) {
                    mc++;
                }
                count = pop.val;
            }
            if (pop.depth == -1) {
                pd = -2;
                count = 0;
            } else {
                pd = pop.depth;
            }
        }

        if (count > max) {
            max = count;
            mc = 1;
        } else if (count == max) {
            mc++;
        }

        if (max == 0) {
            System.out.println("0 1");
        } else {
            System.out.println(max + " " + mc);
        }
    }

    private static void en(Stack<Character> stack) {
        stack.push('(');
        depth++;
    }

    private static void de(Stack<Character> stack, Stack<Element> elements) {
        int val = 2;
        if (!elements.isEmpty() && elements.peek().depth == depth) {
            val += elements.pop().val;
        }
        stack.pop();
        depth--;
        if (!elements.isEmpty() && elements.peek().depth == depth) {
            val += elements.pop().val;
        }
        elements.push(new Element(val, depth));
    }
}