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.BufferedReader;
import java.io.InputStreamReader;
import static java.lang.Math.abs;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.HashMap;
import java.util.HashSet;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;
import java.util.TreeSet;
import static java.lang.Short.parseShort;
import static  java.lang.Integer.parseInt;
import static  java.lang.Long.parseLong;
import static  java.lang.Double.parseDouble;
public class template implements Runnable {
	template()
	{
		
	}
	public void run()
	{
		FastInput in=new FastInput();
		PrintWriter p=new  PrintWriter(System.out,true);
		Stack<Integer> s=new Stack<Integer>();
		int len,i,j,max,dp[]=new int[1000001];
		String d;
		d=in.readString();
		for(i=0;i<d.length();i++)
			dp[i]=-1;
		int count=0;
		max=-1;
		for(i=0;i<d.length();i++)
		{
			if(d.charAt(i)=='(')
				s.push(i);
			else
			{if(!s.empty())
			{
				j=s.peek();
				len=i-j+1;
				s.pop();
				if(j>0 && dp[j-1]!=-1)
				{
					len+=dp[j-1];
				}
				dp[i]=len;
				if(max==len)
				{
					count++;}
					if(len>max)
						{max=len;
						count=1;}
						
				
			}
			}
		}if(max>0)
		p.println(max+" "+count);
		else
			p.println(0+" "+1);
	}

	public static void main(String[] args) throws InterruptedException,IOException {
		Thread t=new Thread(null, new template(),"template",1<<25 );
		t.start();
		t.join();

	}
}
class FastInput{
	BufferedReader br;
	StringTokenizer st;
	FastInput()
	{
		br=new BufferedReader(new InputStreamReader(System.in));
	}
	String next() throws IOException
	{
		while(st==null || !st.hasMoreElements())
		{
			st=new StringTokenizer(br.readLine());
		}
		return st.nextToken();
	}
	Long readLong() 
	{
		try {
			return parseLong(next());
		} catch (NumberFormatException e) {
			// TODO Auto-generated catch block
			return (long)0;
		} catch (IOException e) {
			// TODO Auto-generated catch block
			return (long)0;
		}
	}
	int readInt()
	{
		try {
			return parseInt(next());
		} catch (NumberFormatException e) {
			// TODO Auto-generated catch block
		return 0;
		} catch (IOException e) {
			// TODO Auto-generated catch block
		return 0;
		}
	}
	String readString()
	{
		try {
			return next();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			return "";
		}
	
	}
	double readDouble()
	{try {
		return parseDouble(next());
	} catch (NumberFormatException e) {
		// TODO Auto-generated catch block
		return (double)0;
	} catch (IOException e) {
		// TODO Auto-generated catch block
		return (double)0;
	}
	}
    short readShort() 
    {
    	try {
			return parseShort(next());
		} catch (NumberFormatException e) {
			// TODO Auto-generated catch block
	return 0;
		} catch (IOException e) {
			// TODO Auto-generated catch block
			return 0;
		}
    }
}