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:
//package Chapter2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Map;
import java.util.Stack;
import java.util.TreeMap;

public class longestRegularBracketSequence {

	static class SuffixAutomaton {

		int[] link, len;
		TreeMap<Character, Integer>[] next;
		int lst, idx;
		int length[];
		int [] ans;
		char [] s;
		int[] occ;
		void trace(int idx, int pos) {
			for (Map.Entry<Character, Integer> entry : next[idx].entrySet()) {
				Character c = entry.getKey();
				Integer x = entry.getValue();
				if(c==s[pos]) {
					ans[x]=length[pos];
					trace(x,pos+1);
					break;
				}
			}
		}
		void dfs(int idx) {
			if(occ[idx]!=-1)
				return;
			occ[idx]=0;
			for (Map.Entry<Character, Integer> entry : next[idx].entrySet()) {
				Character c = entry.getKey();
				Integer x = entry.getValue();
				if(c=='$')
					occ[idx]++;
				else {
					dfs(x);
					occ[idx]+=occ[x];
				}
			}
		}
		SuffixAutomaton(char[] s, int [] length)
		{	
			this.length = length;
			int n = s.length;
			ans = new int[n<<1];
			this.s  =s;
			occ = new int[n<<1];
			Arrays.fill(occ, -1);
			link = new int[n<<1];
			len = new int[n<<1];
			next = new TreeMap[n<<1];
			next[0] = new TreeMap<>();
			for(char c: s)
				addLetter(c);
		}
		
		void addLetter(char c)
		{
			int cur = ++idx, p = lst;
			while(!next[p].containsKey(c)) { next[p].put(c, cur); p = link[p]; }
			
			int q = next[p].get(c);
			if(q != cur)
				if(len[q] == len[p] + 1)
					link[cur] = q;
				else
				{
					int clone = ++idx;
					len[clone] = len[p] + 1;
					link[clone] = link[q];
					next[clone] = new TreeMap<>(next[q]);
					link[cur] = link[q] = clone;
					while(next[p].get(c) == q) { next[p].put(c, clone);	p = link[p]; }
				}
			len[cur] = len[lst] + 1;
			next[cur] = new TreeMap<>();
			lst = cur;
		}
	}

public static void main(String[] args) throws IOException{
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	String x = in.readLine();
	char[] cur = x.toCharArray();
	Stack<Integer> st = new Stack<Integer>();
	int [] len = new int[cur.length];
	Arrays.fill(len, -1);
	for (int i = 0; i < len.length; i++) {
		if(cur[i]=='(')
			st.push(i);
		else if(st.isEmpty())
			continue;
		else 
			len[i]=1+i-st.pop();
	}
//	System.out.println(Arrays.toString(len));
	//SuffixAutomaton sa = new SuffixAutomaton(cur, len);
//	sa.dfs(0);
//	sa.trace(0, 0);
	int ans = 0;
	int lenMax = 0;
	int occ = 1;
	int maxSofar = 0;
	for (int i = len.length-1; i >=0; i--) {
		//System.out.println(i+" "+maxSofar);
		if(len[i] ==-1) {
			if(maxSofar!=0) {
				if(lenMax==maxSofar)
					occ++;
				else if(lenMax<maxSofar) {
					occ = 1;
					lenMax = maxSofar;
				}				
			}
			maxSofar = 0;
			continue;
		}
		else {
		//	System.out.print(i+" "+len[i]+" ");
			maxSofar +=len[i];
			i-=(len[i]);
			i++;
			//System.out.println(i);
		}
	}
	if(maxSofar!=0)
	if(lenMax==maxSofar)
		occ++;
	else if(lenMax<maxSofar) {
		occ = 1;
		lenMax = maxSofar;
	}					
	System.out.println(lenMax+" "+occ);
}
}