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:
//package com.company;
import java.io.*;
import java.util.*;

//@author Maurice Saldivar


public class Main {

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pr = new PrintWriter(System.out);
        String tokens = br.readLine();
        int N = tokens.length();
        int longestSeq = 0;
        int count = 1;
        int startPos = 0;
        Deque<Integer> stack = new ArrayDeque<Integer>();

        for (int i = 0; i < N; ++i) {

            if (tokens.charAt(i) == '(') {
                stack.push(i);
            }else {

                if (stack.isEmpty()) {
                    startPos = i + 1;
                    continue;
                }
                stack.pop();
                if (stack.isEmpty()) {

                    if (i - startPos + 1 > longestSeq) {
                        longestSeq = i - startPos + 1;
                        count = 1;
                    }else if (i - startPos + 1 == longestSeq) {
                        count++;
                    }
                } else {

                    if (i - stack.peek() > longestSeq) {
                        longestSeq = i - stack.peek();
                        count = 1;
                    }else if (i - stack.peek() == longestSeq) {
                        count++;
                    }
                }
            }
        }

        pr.print(longestSeq + " " + count);
        pr.flush();


    }
}