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 Solution {
	static Scanner sc=new Scanner(System.in);
	static PrintWriter out=new PrintWriter(System.out);
	//Main
	static int n;
	static char s[];
	public static void main(String args[]) {
		int test=1;
		//test=sc.nextInt();
		while(test-->0) {
			char s[]=sc.nextLine().toCharArray();
			int n=s.length;
			Stack<Integer> st=new Stack<>();
			int dp[][]=new int[n][2];
			for(int i=0;i<n;i++) {
				if(s[i]=='(') {
					st.push(i);
				}
				else {
					if(st.isEmpty()) dp[i][0]=dp[i][1]=-1;
					else {
						dp[i][0]=dp[i][1]=st.pop();
						if(dp[i][0]-1>=0 && dp[dp[i][0]-1][1]!=-1 && s[dp[i][0]-1]==')')dp[i][1]=dp[dp[i][0]-1][1];
					}
				}
			}
			int ans=0,cnt=0;
			for(int i=0;i<n;i++) if(dp[i][1]!=-1 && s[i]==')')ans=Math.max(ans, i-dp[i][1]+1);
			for(int i=0;i<n;i++) if(dp[i][1]!=-1 && i-dp[i][1]+1==ans && s[i]==')')cnt++;
			out.println(ans+" "+Math.max(cnt,1));
		}
		out.flush();
		out.close();
	}
}