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.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;

/**
 * Created by IntelliJ IDEA.
 * User: Jamshed
 * Date: 4/23/12
 * Time: 10:10 AM
 */
public class Brackets implements Runnable {

    Scanner scanner;
    PrintWriter pw;

    public static void main(String arguments[]) {
        new Thread(new Brackets()).start();
    }

    public void solution() {

        String s = scanner.next();

        int maxCount = 1;
        int max = 0;

        ArrayList<Integer> startStack = new ArrayList<Integer>();
        startStack.add(-1);

        for(int i = 0; i < s.length(); ++i) {
            if(s.charAt(i) == '(') {
                startStack.add(i);
            } else {
                if(startStack.size() == 1) {
                    startStack.set(0, i);
                } else {
                    startStack.remove(startStack.size() - 1);

					int len = i - startStack.get(startStack.size() - 1);

                    if (len > max) {
						max = len;
						maxCount = 0;
					}

					if (len == max) {
						++maxCount;
					}
                }
            }
        }

        pw.println(max + " " + maxCount);

    }

    public void printA(int A[]) {
        for(int i = 0; i < A.length; i++) {
            pw.print(A[i] + " ");
        }
    }

    public void insertionSort(int A[]) {
        int key;
        int index;

        for(int i = 0; i < A.length; i++) {
            key = scanner.nextInt();

            index = i - 1;

            while(index > -1 && A[index] > key) {
                A[index + 1] = A[index];
                index--;
            }

            A[++index] = key;
        }
    }

    public void run() {
        scanner = new Scanner(System.in);
        pw = new PrintWriter(System.out);

        solution();

        scanner.close();
        pw.close();
    }
}