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


public class C5 {
	private String ip;
	private int[] ipArr;
	private int longest;
	private int occurences = 1;
	
	public static void main(String[] args) {
		C5 obj = new C5();
		obj.init();
		obj.compute();
	}
	
	private void init() {
		Scanner scn = new Scanner(System.in);
		ip = scn.nextLine();
		ipArr = new int[ip.length()];
		
		for(int i=0;i<ip.length();i++)
		{
			char temp = ip.charAt(i);
			if(temp == '(')
			{
				ipArr[i] = 1;
			}
			else {
				ipArr[i] = -1;
			}
		}
	}
	
	private void compute() {
		int startIndex = 0;
		int[] ansArr = new int[ipArr.length];
		int maxDiff = 0;
		int counter = 0;
		int sum = 0;
		int prev = -1;
		int prevstart = -1;
		Stack<Integer> stack = new Stack<>();
		
		for(int i=0;i<ipArr.length;i++)
		{
			if(ipArr[i] > 0)
				stack.push(i);
			
			sum += ipArr[i];
			
			if(sum < 0)//negative
			{
				startIndex = i+1;
				sum = 0;
			}
			else if(sum == 0)
			{
				int diff = i - startIndex + 1;
				
				for(int j=startIndex;j<=i;j++)
				{
					ansArr[j] = 1;
				}
				/*if(diff > maxDiff)
				{
					maxDiff = diff;
					counter = 1;
				}
				else if(diff == maxDiff)
				{
					counter++;
				}*/
				
				startIndex = i+1;
				
			}
			else if(ipArr[i] < 0){
				//int sumA = ipArr[i];
				ansArr[stack.pop()] = 1;
				ansArr[i] = 1;
				/*for(int k = i;sumA!=0;k--)
				{
					ansArr[k] = 1;
					if(k!=i)
						sumA += ipArr[k];
				}*/
				
				//prev = i;
			}//closing bracket.
		}
		
		int ansSum=0;
		for(int i=0;i<ansArr.length;i++)
		{
			if(ansArr[i] == 0)
			{
				ansSum = 0;
			}
			else
			{
				ansSum+=ansArr[i];
				if(maxDiff < ansSum)
				{
					maxDiff = ansSum;
					counter = 1;
				}
				else if(maxDiff == ansSum)
				{
					counter++;
				}
			}
			
		}
		
		if(maxDiff > 0)
		{
			System.out.println(maxDiff + " " + counter);
		}
		else
		{
			System.out.println("0 1");
		}
	}
}