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.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] ch = in.next().toCharArray();
        int max1 = 0;
        int max2 = 0;
        int max = 0;
        int maxLocal = 0;
        int occ1 = 1;
        int occ2 = 1;
        int occ = 0;
        Stack<Character> pile = new Stack<>();
        for (int i = ch.length - 1; i >= 0; i--) {
            if (ch[i] == ')') {
                pile.push(ch[i]);
            } else {
                if (!pile.isEmpty()) {
                    pile.pop();
                    maxLocal += 2;
                } else {
                    if (maxLocal > max1) {
                        max1 = maxLocal;
                        occ1 = 1;
                    } else if (max1 == maxLocal) {
                        occ1++;
                    }
                    maxLocal = 0;
                }
            }
        }
        if (pile.isEmpty()) {
            if (maxLocal > max1) {
                max1 = maxLocal;
                occ1 = 1;
            } else if (max1 == maxLocal) {
                occ1++;
            }
            maxLocal = 0;
        }
        pile.removeAllElements();
        maxLocal = 0;
        for (int i = 0; i < ch.length; i++) {
            if (ch[i] == '(') {
                pile.push(ch[i]);
            } else {
                if (!pile.isEmpty()) {
                    pile.pop();
                    maxLocal += 2;
                } else {
                    if (maxLocal > max2) {
                        max2 = maxLocal;
                        occ2 = 1;
                    } else if (max2 == maxLocal) {
                        occ2++;
                    }
                    maxLocal = 0;
                }
            }
        }
        if (pile.isEmpty()) {
            if (maxLocal > max2) {
                max2 = maxLocal;
                occ2 = 1;
            } else if (max2 == maxLocal) {
                occ2++;
            }
            maxLocal = 0;
        }
        if (max1 == max2) {
            max = max1;
            occ = occ1;
        } else if (max1>max2) {
            max = max1;
            occ = occ1;
        } else {
            max = max2;
            occ = occ2;
        }
        if (max == 0) {
            System.out.println("0 1");
        } else {
            System.out.println(max + " " + occ);
        }
    }

}