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:
//<editor-fold defaultstate="collapsed" desc="comment">
import java.io.File;
import java.io.PrintStream;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

import javax.swing.text.html.HTMLDocument.HTMLReader.PreAction;
//</editor-fold>

public class Main 
{
    public static void main(String[] args) throws Exception
    {
        StringBuilder resBuilder = new StringBuilder();
        new Program(IOGenerator.getScanner(IOGenerator.CONSOLE), IOGenerator.getPrintStream(IOGenerator.CONSOLE), resBuilder).run();
        System.out.print(resBuilder);
    }
}

//<editor-fold defaultstate="collapsed" desc="comment">

class IOGenerator
{
    public static final int CONSOLE = 0;
    public static final int FILE = 1;
    
    public static Scanner getScanner(int type) throws Exception
    {
        if (type == CONSOLE)
            return new Scanner(System.in);
        else if (type == FILE)
            return new Scanner(new File("c:\\a.txt"));
        
        throw new Exception();
    }
    
    public static PrintStream getPrintStream(int type) throws Exception
    {
        if (type == CONSOLE)
            return System.out;
        else if (type == FILE)
            return new PrintStream(new File("c:\\a2.txt"));
        
        throw new Exception();
    }
}
//</editor-fold>


class Program
{
    @SuppressWarnings("unused")
	private final Scanner in;
    @SuppressWarnings("unused")
	private final PrintStream out;
    @SuppressWarnings("unused")
	private final StringBuilder resBuilder;
    
    Program(Scanner scanner, PrintStream out, StringBuilder resBuilder)
    {
        this.in = scanner;
        this.out = out;
        this.resBuilder = resBuilder;
    }
    
    void run()
    {
    	char[] expression = in.nextLine().toCharArray();
    	Stack<Integer> openingBracePosition = new Stack<>();
    	int[] closingBracePosition = new int[expression.length];
    	
    	Arrays.fill(closingBracePosition, -1);
    	
    	for (int i = 0; i < expression.length; i++)
    	{
    		if (expression[i] == '(')
    			openingBracePosition.push(i);
    		else if (!openingBracePosition.isEmpty())
    			closingBracePosition[openingBracePosition.pop()] = i;
    	}
    	
    	openingBracePosition = null;
    	
    	int i = 0;
    	int bestLen = 0;
    	int bestLenCount = 1;
    	int validBraceStart = 0;
    	int newLen;
    	
    	while (true)
    	{
    		while (i < expression.length && (expression[i] == ')' || closingBracePosition[i] == -1))
    			i++;
    		
    		if (i == expression.length)
    			break;
    		
    		validBraceStart = i;
    		
    		while (i < expression.length && closingBracePosition[i] != -1)
    		{
    			i = closingBracePosition[i];
    			newLen = i - validBraceStart + 1;
    			
    			if (newLen > bestLen)
    			{
    				bestLen = newLen;
    				bestLenCount = 1;
    			}
    			else if (newLen == bestLen)
    				bestLenCount++;
    			
    			i++;
    		}
    	}
    	
    	resBuilder.append(bestLen).append(" ").append(bestLenCount).append("\n");
    }
}