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

public class CodeForce {
    
    private void solve() throws IOException {
        final String line = nextToken();
        int []arr = new int[line.length()];
        int max_len = 0, max_count = 1;
        for(int i = 1; i < line.length(); i++) {
            if(line.charAt(i) == ')') {
                int c = -1;
                if(line.charAt(i - 1) == '(') {
                    arr[i] = 2;
                    c = 2;
                } else {
                    int k = i - 1;
                    int m = 0;
                    while(k >= 0 && arr[k] > 0) {
                        m += arr[k];
                        k -= arr[k];
                    }
                    if(k >= 0 && line.charAt(k) == '(') {
                        arr[i] = m + 2;
                        c = arr[i];
                    }
                }
                
                if(c > max_len) {
                    max_len = c;
                    max_count = 1;
                } else if(c == max_len) {
                    max_count++;
                }
            }
        }
        
        int k = line.length() - 1;
        int mmax_len = 0, mmax_count = 1;
        while(k >= 0) {
            if(line.charAt(k) == ')' && arr[k] > 0) {
                int m = 0;
                while(k >= 0 && arr[k] > 0) {
                    m += arr[k];
                    k -= arr[k];
                }
                if(m > mmax_len) {
                    mmax_len = m;
                    mmax_count = 1;
                } else if(m == mmax_len) {
                    mmax_count++;
                }
            } else {
                k--;
            }
        }
        
        if(mmax_len > max_len || mmax_len == max_len && mmax_count > max_count) {
            max_len = mmax_len;
            max_count = mmax_count;
        }
        
        System.out.println(max_len + " " + max_count);
    }
    
    public static void main(String[] args) {
        new CodeForce().run();
    }

    BufferedReader reader;
    StringTokenizer tokenizer;
    PrintWriter writer;

    public void run() {
        try {
            reader = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = null;
            writer = new PrintWriter(System.out);
            solve();
            reader.close();
            writer.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
    
    String nextLine() throws IOException {
        return reader.readLine();
    }

    String nextToken() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
}