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

    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
        FastScanner in = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        String s = in.next();
        Stack<Integer> stack = new Stack<>();
        int[] a = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.add(i);
            } else if (!stack.isEmpty()) {
                Integer l = stack.pop();
                a[l] = i;
            }

        }
        int i = 0, j = -2, l = 0, max = 0, maxc = 1;
        while (i < s.length()) {
            if (a[i] != 0) {
                if (j == (i - 1)) {
                    l += a[i] - i + 1;
                } else {
                    l = a[i] - i + 1;
                }
                j = a[i];
                i = j + 1;
                if (l > max) {
                    max = l;
                    maxc = 1;
                } else if (l == max) {
                    maxc++;
                }
            } else {
                i++;
            }
        }

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

}

class FastScanner {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer("");

    String next() {
        while (!st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    int[] readArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
        }
        return a;
    }

    long nextLong() {
        return Long.parseLong(next());
    }
}