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

public class LongestRegularBracketSequence {
	static Scanner sc;
	static int maxEnd = -1;
	static int maxStart = -1;
	static int count = 0;
	static Stack<Integer> openings;
	static boolean bracket[];
	static String s;

	static void check(int tempEnd) {
		int tempStart = openings.pop();
		bracket[tempEnd] = true;
		bracket[tempStart]= true;
		if (tempEnd - tempStart > maxEnd - maxStart) {
			maxEnd = tempEnd;
			maxStart = tempStart;
			count = 1;
		} else {
			if (tempStart == maxEnd + 1) {
				maxEnd = tempEnd;
				count = 1;
				return;
			}
			if (tempEnd - tempStart == maxEnd - maxStart) {
				count++;
			}
		}
	}

	static int countOccurence() {
		int state = 0;
		int counter = 0;
		int max = 0;
		for (int i = 0; i < bracket.length; i++) {
			if(bracket[i]) {
				state++;
				if(state>max) {
					max = state;
					counter = 1;
				}else if (state==max){
					counter++;
				}
			}else{
				state = 0;
			}
		}
		count = max;
		return counter;
	}

	public static void main(String[] args) {
		sc = new Scanner(System.in);
		s = sc.next();
		openings = new Stack<Integer>();
		bracket = new boolean[s.length()];
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == '(') {
				openings.add(i);
			} else {
				if (openings.isEmpty())
					continue;
				check(i);
			}
		}
		if(maxEnd==-1){
			System.out.println(0+" "+1);
			return;
		}
		int res = countOccurence();
		System.out.println(count + " " + res);
	}
}