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.Arrays;
import java.util.Scanner;
import java.util.Stack;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
/**
 *
 * @author madis
 */
public class Braces {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        Stack<Character> st = new Stack<Character>();
        int max = 0;
        int localmax = 0;
        int count = 0;
        int a[] = new int[str.length()];
        Arrays.fill(a, -1000);
        int last = -1000;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == ')') {
                if (last == -1000) {
                    a[i] = 1000;
                } else {
                    a[i] = -1;
                    int temp = a[last];
                    a[last] = -1;
                    last = temp;
                }
            } else if (str.charAt(i) == '(') {
                a[i] = last;
                last = i;
            }
        }
        for (int i = 0; i < str.length(); i++) {
            if (a[i] == -1) {
                localmax++;
            } else if (a[i] != -1) {
                if (localmax > max) {
                    count = 1;
                    max = localmax;
                } else if (localmax == max) {
                    count++;
                }
                localmax = 0;
            }
        }

        if (localmax > max) {
            count = 1;
            max = localmax;
        } else if (localmax == max) {
            count++;
        }
        if(max==0){
            count=1;
        }
        System.out.println(max + " " + count);
    }
}