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.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;

public class LongestRegularBracketSequence_R5C {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		String s = sc.nextLine();

		int max = 0;
		int cnt = 0;
		Stack<Integer> st = new Stack<>();
		int start = 0;
		boolean[] good = new boolean[s.length()];
		for(int i=0;i<s.length();i++)
		{
			char c = s.charAt(i);
			if(c == '(')
				st.push(i);
			else
				if(!st.isEmpty())
					good[i] = good[st.pop()] = true;
		}
		int curLength = 0;
		for(int i=0;i<s.length();i++)
		{
			if(!good[i])
			{
				if(curLength == max)
					cnt++;
				if(curLength > max)
				{
					cnt = 1;
					max = curLength;
				}
				curLength = 0;
			}
			else
				curLength++;
		}
		if(curLength == max)
			cnt++;
		if(curLength > max)
		{
			cnt = 1;
			max = curLength;
		}
		
		PrintWriter pw = new PrintWriter(System.out);
		if(max == 0)
			cnt = 1;
		pw.println(max + " " + cnt);
		pw.flush();

	}

	static class Scanner{
		StringTokenizer st;BufferedReader br;
		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}
		public Scanner(String s) throws FileNotFoundException{	br = new BufferedReader(new FileReader(new File(s)));}
		public String next() throws IOException 
		{while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());return st.nextToken();}
		public int nextInt() throws IOException {return Integer.parseInt(next());}
		public long nextLong() throws IOException {return Long.parseLong(next());}
		public String nextLine() throws IOException {return br.readLine();}
		public double nextDouble() throws IOException {return Double.parseDouble(next());}
		public boolean ready() throws IOException {return br.ready();}
	}

}