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.*;
import static java.lang.System.out;

public final class LongestRegularBracketSequence {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] l = br.readLine().toCharArray();
        int[] a = new int[l.length];
        int[] b = new int[l.length];
        Deque<Integer> s = new ArrayDeque<Integer>();
        for (int i = 0; i < l.length; i++) {
            if (l[i] == '(') { a[i] = -1; b[i] = -1; s.addFirst(i); continue; }

            if (s.isEmpty()) {
                a[i] = -1;
                b[i] = -1;
                continue;
            }

            int ind = s.removeFirst();
            a[i] = ind;
            b[i] = (ind - 1 >= 0 && b[ind - 1] >= 0) ? b[ind - 1] : a[i];
        }

        int max = 0;
        int count = 1;
        for (int i = 0; i < l.length; i++) {
            if (l[i] == '(' || b[i] == -1) continue;

            int v = i - b[i] + 1;
            if (v > max) {
                max = v;
                count = 1;
            }
            else if (v == max) count++;
        }

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