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.*;

public class check {
    int INF = (int)1e9;
    
    void solve(InputReader in, PrintWriter out) throws IOException {
        char[] s = in.next().toCharArray();
        Stack<Integer> stack = new Stack<>();
        int m = 0, c = 1, k = 0, x = 0;
        for(int i=0; i<s.length; i++) {
            if(s[i]=='(') {
                stack.push(1);
            } else {
                if(stack.size()>0) {
                    k = 1; x = 0;
                    while(stack.size()>0 && stack.peek()%2==0) {
                        k += stack.pop();
                        x++;
                    }
                    if(stack.size() >0 && stack.peek()==1) {
                        k += 1;
                        stack.pop();
                        stack.push(k);
                        x = 2;
                    } else if(stack.size()==0) {
                        k--;
                    }
                    if(k>m) {
                        m = k;
                        c = 1;
                    } else if(k==m && k!=0 && x>1) {
                        c++;
                    }
                } else {
                    stack = new Stack<>();
                }
            }
        }
        while(stack.size()>0) {
            while(stack.size()>0 && stack.peek()%2==1) {
                stack.pop();
            }
            k = 0; x = 0;
            while(stack.size()>0 && stack.peek()%2==0) {
                k += stack.pop();
                x++;
            }
            if(k>m) {
                m = k;
                c = 1;
            } else if(k==m && k!=0 && x>1) {
                c++;
            }
        }
        out.println(m + " " + c);
    }
    
    
    public static void main(String[] args) throws IOException {
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        int t = 1;//in.nextInt();
        while(t-- >0) {
            new check().solve(in, out);
        }
        out.close();
    }
    
    static class InputReader {
        static BufferedReader br;
        static StringTokenizer st;
    
        public InputReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
    }
}