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.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class C5C {
	private StringTokenizer st;
	private BufferedReader bf;
	
	
	public C5C(){
		try {
			bf = new BufferedReader(new InputStreamReader(System.in));
			st = new StringTokenizer(bf.readLine());
			PriorityQueue<Integer> p = new PriorityQueue<Integer>(15, Collections.reverseOrder());

			String s = next();

			int[] abc = new int[1000000];
			
			int balance = 0;
			int prevbalance = -1;
			int val = 0;
			int count = 0;
			int prevone = 0;
			
			for (int i = 0; i < s.length(); i++) {
				if (s.charAt(i) == '(') {
					balance = balance + 1;
				} else {
					balance = balance - 1;
				}
				
				if (balance >= 0) {
					if (s.charAt(i) == '(' ) {
						abc[count++] = 1;
						prevone = count;
					} else {
						
						for (int j = prevone; j >= 0 ; j--) {
							if (abc[j] == 1) {
								abc[j] = 0;
								prevone = j;
								break;
							}
							if (abc[j] < 0)
								break;
						}
					}
				} else {
					if (prevbalance >= 0) {
						abc[count++] = -1;
						balance = 0;
					}
					
					balance = 0;
				}

				prevbalance = balance;
			}
			
			int maxVal = 0;
			int nextVal = 1;
			
			val = 0;
			for (int i = count - 1; i >= 0; i--) {
				if (abc[i] == 0) {
					val = val + 1;
				} else {
					if (val > 0) {
						int setVal = val * 2;
						if  (setVal >= maxVal) {
							maxVal = setVal;
							p.add(setVal);
						}
						//p.add(val * 2);
					}
					val = 0;
				}
			}

			if (val > 0) {
				if ((val * 2) >= maxVal) {
					p.add(val * 2);
				}
			}
			
			maxVal = 0;
			while (p.size() > 0) {
				int temp = p.poll();
				
				if (maxVal < temp) {
					maxVal = temp;
				} else if (maxVal > temp) {
					break;
				} else {
					nextVal++;
				}
			}
			
			System.out.println(maxVal);
			System.out.println(nextVal);

			
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	private int nextInt() throws IOException {
		return Integer.parseInt(next());
	}
	
	private String next() throws IOException {
		if (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(bf.readLine());
		return st.nextToken();
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		C5C c = new C5C();
	}

}