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.*;
import java.lang.*;
import java.math.*;
import java.math.BigInteger;

public class Main {
	final int INF = 1000000000;
	final int MAXN = 100100;	
	
	Scanner input = new Scanner(System.in);
	BufferedReader inp = new BufferedReader(new InputStreamReader(System.in));
	PrintWriter out = new PrintWriter(System.out);
	
	public static void main(String[] args) throws IOException {
		new Main().run();
	}
		
	void run() throws IOException {
		String st = inp.readLine();		
		Stack<Data> stack = new Stack<Data>();		
		int res, cnt;
		res = 0;
		cnt = 1;
		for (int i = 0; i < st.length(); ++i) {
			if (st.charAt(i) == '(') {
				stack.push(new Data(0, 0));
			} else {
				//out.println(i + " " + stack.size());
				if (!stack.empty()) {
					Data last = stack.pop();
					if (last.len + 2 > res) {
						res = last.len + 2;
						cnt = 1;
					} else {
						if (last.len + 2 == res) {
							++cnt;
						}
					}
					if (!stack.empty()) {
						Data temp = stack.pop();
						stack.push(new Data(temp.len + last.len + 2, temp.seg + 1));
					} else {
						if (i + 1 < st.length() && st.charAt(i + 1) == '(') {
							++i;
							stack.push(new Data(last.len + 2, 1));
						}
					}
					//out.println(i + " " + res);
				}				
			}
		}
		while (!stack.empty()) {
			Data temp = stack.pop();
			if (temp.seg > 1) {
				if (temp.len > res) {
					res = temp.len;
					cnt = 1;
				} else {
					if (temp.len == res) {
						++cnt;
					}
				}
			}
		}
		out.println(res + " " + cnt);
		out.close();
	}	
	
	class Data {
		int len, seg;
		
		Data(int len, int seg) {
			this.len = len;
			this.seg = seg;
		}
	}
}