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.*;
import java.lang.*;
import java.io.*;

public class Codechef
{
   
	public static void main (String[] args) throws java.lang.Exception
	{
	    //2InputReader input = new InputReader(System.in);
	    //OutputWriter out = new OutputWriter(System.out);
	    Scanner input = new Scanner(System.in);
	    String s = input.nextLine();
	    Stack<Integer>stack = new Stack<>();
	    int max = 0;
	    ArrayList<Integer>list = new ArrayList<>();
	    stack.push(-1);
	    for(int i=0;i<s.length();i++){
	          if(s.charAt(i) == '('){
	              stack.push(i);
	          }else{
	              stack.pop();
	              if(!stack.isEmpty()){
	                  int t = stack.peek();
	                  max = Math.max(max,i-t);
	                  list.add(i-t);
	              }else{
	                  stack.push(i);
	              }
	          }
	    }
	    int count =0;
	    for(int lengths:list){
	        if(lengths == max)count++;
	    }
	    if(max == 0){
	        System.out.println(max+" "+1);
	    }else{
	    System.out.println(max+" "+count);
	    }
	}
}