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.*;
import java.io.*;

public class Contest {

	public static void main(String[] args) throws IOException, NumberFormatException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		int[] close = new int[s.length()];
		Stack<Integer> stack = new Stack<>();
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == '(') {
				stack.add(i);
			} else if (!stack.isEmpty()) {
				close[stack.pop()] = i;
			}
		}
		int max = 0;
		int ans = 1;
		for (int i = 0; i < close.length; i++) {
			if (close[i] != 0) {
				int res = Math.abs(close[i] - i) + 1;
				int j = i;
				int idx = i;
				while (close[j] + 1 < close.length && close[close[j] + 1] != 0) {
					res += Math.abs(close[close[j] + 1] - (close[j] + 1)) + 1;
					j = close[j] + 1;
					if (close[j] + 1 < close.length) {
						idx = j;
					}
				}
				if (res == max) {
					ans++;
				}
				if(res>max){
				    max=res;
				    ans=1;
				}
				i = idx;
			}
		}
		System.out.println(max + " " + ans);
	}
}