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

public class Main {
    static final int N = (int)1e6 + 10;
    static int tt;
    static int[] stk = new int[N], dp = new int[N], cnt = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        //        br = new BufferedReader(new InputStreamReader(new FileInputStream("")));
        String str = br.readLine();
        for (int i = 0; i < str.length(); ++i) {
            if (str.charAt(i) == '(') {
                stk[tt++] = i;
            } else {
                if (tt > 0) {
                    --tt;
                    dp[i] = stk[tt] < 1 ? i - stk[tt] + 1 : i - stk[tt] + 1 + dp[stk[tt] - 1];
                    ++cnt[dp[i]];
                }
            }
        }
        cnt[0] = 1;
        for (int i = str.length(); i > -1; --i) {
            if (cnt[i] > 0) {
                bw.write(i + " " + cnt[i]);
                bw.close();
                return;
            }
        }
        bw.close();
    }
}