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.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;
import java.util.StringTokenizer;

public class C {
	
	
	public static void main(String[] args) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		char[] a = sc.next().toCharArray(); int n = a.length;
		ArrayList<Pair> match = new ArrayList<>();
		Stack<Integer> s = new Stack<>();
		int max = 0, occ = 0, sum = 0;
		for(int i = 0; i < n; i++)
			if(a[i] == '(') s.add(i);
			else if(a[i] == ')' && !s.isEmpty()) match.add(new Pair(s.pop(), i));
		Collections.sort(match);
		int size = match.size();
		for(int i = 0; i < size; i++)
		{
			sum += match.get(i).len;
			int j = i+1;
			while(j < size && match.get(j).from < match.get(i).to) j++;
			if(j < size && match.get(j).from != match.get(i).to + 1)
			{
				max = Math.max(max, sum);
				sum = 0;
			}
			i = j-1;
		}
		max = Math.max(max, sum);
		sum = 0;
		for(int i = 0; i < size; i++)
		{
			sum += match.get(i).len;
			int j = i+1;
			while(j < size && match.get(j).from < match.get(i).to) j++;
			if(j < size && match.get(j).from != match.get(i).to + 1)
			{
				if(sum == max) occ++;
				sum = 0;
			}
			i = j-1;
		}
		if(sum == max) occ++;
		occ = Math.max(occ, 1);
		out.println(max + " " + occ);
		out.flush();
		out.close();
	}
	
	static class Pair implements Comparable<Pair>
	{
		int from, to, len;
		Pair(int f, int t)
		{
			from = f; to = t; len = to - from + 1;
		}
		public int compareTo(Pair o) {
			return from - o.from;
		}
		
		public String toString()
		{
			return from + "," + to;
		}
	}
	
	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream system) {br = new BufferedReader(new InputStreamReader(system));}
		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public String nextLine()throws IOException{return br.readLine();}
		public int nextInt() throws IOException {return Integer.parseInt(next());}
		public double nextDouble() throws IOException {return Double.parseDouble(next());}
		public char nextChar()throws IOException{return next().charAt(0);}
		public Long nextLong()throws IOException{return Long.parseLong(next());}
		public boolean ready() throws IOException{return br.ready();}
		public void waitForInput(){for(long i = 0; i < 3e9; i++);}
	}
}