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 C5 {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int k = 0, max = 0, l = -1;
        Stack<Integer> st = new Stack<Integer>();
        char[] c = bf.readLine().trim().toCharArray();
        for (int i = 0; i < c.length; i++) {
            if (c[i] == '(')
                st.push(i);
            else {
                if (st.isEmpty())
                    l = i;
                else {
                    st.pop();
                    int x = i - (st.isEmpty()? l : st.peek());
                    if (x == max) {
                        k++;
                    }
                    if (x > max) {
                        max = x;
                        k = 1;
                    }
                }
            }
        }
        if (max == 0)
            k = 1;
        System.out.println(max+" "+k);
    }

}