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

public class CF5C {
	public static BufferedReader buffstdin = new BufferedReader(new InputStreamReader(System.in));
	static OutputStream out = new BufferedOutputStream ( System.out );
	
	public static void Sprintln(Object s) throws IOException {
		String S = s + "";
		System.out.println(S);
	}
	public static void Sprint(Object s) throws IOException {
		System.out.print("" + s);
	}
	public static void println(Object s) throws IOException {
		String S = s + "\n";
		out.write(S.getBytes());
	}
	public static void println() throws IOException {
		out.write("\n".getBytes());
	}
	public static void print(Object s) throws IOException {
		out.write(("" + s).getBytes());
	}
	public static int Int(String s) {
		return Integer.parseInt(s);
	}
	public static String[] getLine() throws IOException {
		return buffstdin.readLine().trim().split(" ");
	}
	public static String getString() throws IOException {
		return buffstdin.readLine().trim();
	}
	public static int getInt() throws IOException {
		return Int(getString());
	}
	public static int[] getIntLine() throws IOException {
		String[] line = buffstdin.readLine().trim().split(" ");
		int[] a = new int[line.length];
		for(int i : range(line.length))	a[i] = Int(line[i]);
		return a;
	}
	public static int[] range(int u) {
		int[] array = new int[u];
		for(int i=0; i<u; i++) array[i] = i;
		return array;
	}
	public static int[] range(int l, int u) {
		int[] array = new int[u-l];
		for(int i=0; i<u-l; i++) array[i] = l+i;
		return array;
	}
	
	public static void main(String[] args) throws IOException {
		char[] line = getString().toCharArray();
		Stack<Integer> pars = new Stack<Integer>();
		int maxLength = 0;
		int numMax = 1;
		int[] a = new int[line.length];//position of earliest opening par that makes a sequence with some i in a[i]
		int[] b = new int[line.length];//position of corresponding opening bracket
		for(int l : range(line.length)) {
			a[l] = -1;
		}
		
		int i=0;
		for(char c : line) {
			if(c=='(') {
				pars.push(i);
			}
			else if(c==')') {
				if(pars.isEmpty()) { // if there is a closing par without a corresponding opening par, using this location in a sequence is impossible
					a[i] = -1;
					b[i] = -1;
				}
				else { // otherwise, we're good, but we need more info
					b[i] = pars.pop();
					a[i] = b[i];
					if(b[i] - 1 >= 0) {
						if(a[b[i]-1] != -1) {
							a[i] = a[b[i]-1];
						}
					}
				}
			}
			i++;
		}
		int len;
		for(int f : range(line.length)) {
			if(a[f] != -1) {
				//Sprintln(f +": " + (f - a[f]+1));
				len = f - a[f]+1; // add 1 for inclusiveness
				if(len > maxLength) {
					maxLength = len;
					numMax = 1;
				}
				else if(len == maxLength) {
					numMax++;
				}
			}
		}
		println(maxLength + " " + numMax);
		out.flush();
	}
}