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.*;
import java.util.*;
import java.math.*;
import java.text.*;

public class Main {

	String str;
	int index[];
	
	void run() throws Exception {
		str = cin.next();
		int i = 0, ans = 0, count = 1, len = str.length();
		while (str.charAt(i) == ')' && i < len) i++;
		if (i >= len) {
			System.out.println("0 1");
			return;
		}
		str = "(" + str.substring(i);
		len = str.length();
		index = new int[len];
		boolean flag = true;
		int temp = 0;
		for (i = 1; i < len; i++) {
			if (str.charAt(i) == '(') {
				if (str.charAt(i - 1) == ')' && flag) 
					temp++;
				else index[temp++] = i;
			} else if (temp == 0) {
				flag = false;
			} else {
				flag = true;
				temp--;
				if (i - index[temp] + 1 == ans) 
					count++;
				else if (i - index[temp] + 1 > ans) {
					ans = i - index[temp] + 1;
					count = 1;
				}
			}
		}
		System.out.println(ans + " " + count);
	}  
	
	public static void main(String[] args) throws Exception {	
//		InputStreamReader is = new InputStreamReader(new FileInputStream("E:/input.txt"));
//		BufferedReader cin = new BufferedReader(is);
		
		new Main().run();
//		out.close();
	}
	
//	InputStreamReader is = new InputStreamReader(System.in);
//	BufferedReader cin = new BufferedReader(is);
	
	static InputStream inputStream = System.in;
	static InputReader cin = new InputReader(inputStream);
//	static OutputStream outputStream = System.out;
//	static OutputWriter out = new OutputWriter(outputStream);
	
//	Scanner cin = new Scanner(new BufferedInputStream(System.in));
	
}

class Tree {
	int lt, rt;
	long sum;
}

class InputReader { 
    private InputStream stream; 
    private byte[] buf = new byte[1024]; 
    private int curChar; 
    private int numChars; 

    public InputReader(InputStream stream) { 
        this.stream = stream; 
    } 

	public int read() { 
        if (numChars == -1) 
            return -1; 
            //throw new InputMismatchException(); 
        if (curChar >= numChars) { 
            curChar = 0; 
            try { 
                numChars = stream.read(buf); 
            } catch (IOException e) { 
                throw new InputMismatchException(); 
            } 
            if (numChars <= 0) 
                return -1; 
        } 
        return buf[curChar++]; 
    } 

    public int nextInt() { 
        int c = read(); 
        if (c == -1) 
            return -1; 
        while (isSpaceChar(c)) 
            c = read(); 
        int sgn = 1; 
        if (c == '-') { 
            sgn = -1; 
            c = read(); 
        } 
        int res = 0; 
        do { 
            if (c < '0' || c > '9') 
                throw new InputMismatchException(); 
            res *= 10; 
            res += c - '0'; 
            c = read(); 
        } while (!isSpaceChar(c)); 
        return res * sgn; 
    } 
    
    public long nextLong() {
    	int c = read(); 
        if (c == -1) 
            return -1; 
        while (isSpaceChar(c)) 
            c = read(); 
        int sgn = 1; 
        if (c == '-') { 
            sgn = -1; 
            c = read(); 
        } 
        long res = 0; 
        do { 
            if (c < '0' || c > '9') 
                throw new InputMismatchException(); 
            res *= 10; 
            res += c - '0'; 
            c = read(); 
        } while (!isSpaceChar(c)); 
        return res * sgn;
    }
     
    public String next() {   
        StringBuilder str = new StringBuilder();   
        int ch;   
        while (isSpaceChar(ch = read()));   
        if (ch == -1)   
            return null;   
        do {   
            str.appendCodePoint(ch);   
        } while (!isSpaceChar(ch = read()));   
        return str.toString();   
    }  
     
    public static boolean isSpaceChar(int c) { 
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; 
    } 

    public char nextCharacter() { 
        int c = read(); 
        while (isSpaceChar(c)) 
            c = read(); 
        return (char) c; 
    }   
} 


class OutputWriter {
	private final PrintWriter writer;

	public OutputWriter(OutputStream outputStream) {
		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
	}

	public OutputWriter(Writer writer) {
		this.writer = new PrintWriter(writer);
	}

	public void print(Object...objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}

    public void printLine(Object...objects) {
		print(objects);
		writer.println();
	}

	public void close() {
		writer.close();
	}

	}