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

public class Prog_5_C {
    private static BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));

    static int maxLen;
    static int count;
    static List<Pair> segments = new ArrayList<>();

    static class Pair {
        int a;
        int b;

        public Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }

    private static int calc(String s) {
        //int balance = 0;
        int currentLen = 0;
        Stack<Integer> opens = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                //balance++;
                opens.add(i);
            } else {
                if (!opens.isEmpty()) {
                    Pair segment = new Pair(opens.pop(), i);
                    segments.add(segment);
                    int len = segment.b - segment.a + 1;
                    if (len > maxLen) {
                        maxLen = len;
                    }
                }
            }
        }
        return maxLen;
    }

    public static void main(String[] args) throws IOException {
        String s = buffer.readLine();

        //String s = "(()())()(())()()())())()((()(()(())()()())((()(())()(()()()()))()(())()(((()())()(()((())()(())(()))"; //"(()())()(())()()())())()((()(()(())()()())((()(())()(()()()()))()(())()(((()())()(()((())()(())(()))";
        calc(s);

        segments.sort((o1, o2) -> {
            int compare_a = Integer.compare(o1.a, o2.a);
            if (compare_a != 0) {
                return compare_a;
            }
            return Integer.compare(o1.b, o2.b);
        });

        count = 0;
        int lastStart = -1;
        int lastEnd = -2;
        int maxLen = 0;
        for (Pair seg : segments) {
            if (seg.a > lastEnd + 1) {
                int len = lastEnd - lastStart + 1;
                if (len > maxLen) {
                    maxLen = len;
                    count = 1;
                } else if (len == maxLen) {
                    if (len > 0) {
                        count++;
                    }
                }
                //if (lastStart >= 0) {
                //    System.out.println("" + lastStart + ":" + lastEnd + ":" + s.substring(lastStart, lastEnd + 1));
                //}
                lastStart = seg.a;
            }
            lastEnd = Math.max(lastEnd, seg.b);
        }

        if (lastStart > -1) {
            int len = lastEnd - lastStart + 1;
            if (len > maxLen) {
                maxLen = len;
                count = 1;
            } else if (len == maxLen) {
                if (len > 0) {
                    count++;
                }
            }
        }

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