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

public class Main {
    private static String s;
    private static boolean b[];

    private static int process(int i, int j) {
        if (s.charAt(i) == '(' && s.charAt(j) == ')') {
            b[i] = b[j] = true;

            do {
                j++;
            } while (j < s.length() && b[j]);

            if (j >= s.length() || s.charAt(j) == '(') {
                return j;
            }

            do {
                i--;
            } while (i >= 0 && b[i]);

            if (i < 0 || s.charAt(i) == ')') {
                return j;
            }

            return process(i, j);
        }

        for (i = j; i < s.length(); i++) {
            if (!b[i]) {
                break;
            }
        }
        return i;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
//        int n = Integer.parseInt(st.nextToken());


        s = st.nextToken();
        b = new boolean[s.length()];

        int i = 0, j = 1;
        while (j < s.length()) {
            i = process(i, j);
            j = i + 1;
        }

//        while (true) {
//            int k = 0;
//            int l = -1;
//            for (int i = 0; i < s.length(); i++) {
//
//
//                if (b[i]) {
//                    continue;
//                }
//                if (s.charAt(i) == '(') {
//                    l = i;
//                } else if (l >= 0) {
//                    b[l] = b[i] = true;
//                    l = -1;
//                    k++;
//                }
//            }
//
//            if (k == 0) {
//                break;
//            }
//        }

        int l = 0;
        int max = 0, count = 1;

        for (i = 0; i < s.length(); i++) {
            if (b[i]) {
                l++;
            } else {
                if (l > max) {
                    max = l;
                    count = 1;
                } else if (l == max && l > 0) {
                    count++;
                }
                l = 0;
            }
        }

        if (l > max) {
            max = l;
            count = 1;
        } else if (l == max && l > 0) {
            count++;
        }

        System.out.println(max + " " + count);
    }
}