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

// bracket
public class P5C {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int len = s.length();
        char[] sch = s.toCharArray();
        int[] lb = new int[len];
        Arrays.fill(lb, -1);
        int curr = 0;
        for (int i = 0; i < len; ++i) {
            if (sch[i] == '(') {
                ++curr;
            } else {
                if (curr > 0) {
                    --curr;
                    int idx = i - 1;
                    while (true) {
                        if (sch[idx] == '(') {
                            break;
                        } else {
                            idx = lb[idx] - 1;
                        }
                    }
                    lb[i] = idx;
                } else {
                    lb[i] = -1;
                }
            }
        }
        for (int i = 0; i < len; ++i) {
            if (sch[i] == ')' && lb[i] >= 0) {
                lb[lb[i]] = -2;
            }
        }
        int maxLen = 0, cnt = 0;
        curr = 0;
        for (int i = 0; i < len; ++i) {
            if (lb[i] == -2 || lb[i] >= 0) {
                ++curr;
                if (curr > maxLen) {
                    maxLen = curr;
                    cnt = 1;
                } else if (curr == maxLen) {
                    ++cnt;
                }
            } else {
                curr = 0;
            }
        }
        if (maxLen == 0) {
            System.out.println("0 1");
        } else {
            System.out.println(maxLen + " " + cnt);
        }
    }

}