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

public class Main implements Runnable  {
StreamTokenizer ST;      
PrintWriter out;      
BufferedReader br;   
Scanner in;
int inf = 1000000000;
double x = 1e-8;

int nextInt() throws IOException{      
    ST.nextToken();      
    return (int)ST.nval;      
}
long nextLong() throws IOException{      
    ST.nextToken();      
    return (long)ST.nval;      
}      
String next() throws IOException{      
    ST.nextToken();      
    return ST.sval;      
}      
double nextD() throws IOException{      
    ST.nextToken();      
    return ST.nval;      
}      
public static void main(String[] args) throws IOException {       
    new Thread(new Main()).start();      
}

public void run()  {      
    try {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));  
        //in = new Scanner(br);
        ST = new StreamTokenizer(br);      
        solve();      
        out.close();
        //in.close();
        br.close();   
    }         
    catch (IOException e) {        
        throw new IllegalStateException(e);       
    }      
}

public void solve() throws IOException {
    char[] s = br.readLine().toCharArray();
    int n = s.length;
    int next[]  = new int[n];
    Arrays.fill(next, -1);
    Stack<Integer> st = new Stack<Integer>();
    Vector<Integer> v = new Vector<Integer>();
    for (int i=0; i<n; i++) if (s[i]=='(') st.push(i); else {
        if (!st.isEmpty()) {
            int pr = st.pop();
            next[pr] = i;
            if (st.isEmpty()) v.add(i-pr+1);
        } else {
            next[i]  = -1;
        }
    }
    int res = 0, cnt = 1;
    int p = 0;
    while (p<n) {
        if (next[p]<0) {
            p++; continue;
        }
        int x = 0;
        while (p<n&& next[p]>0) {
            x += next[p]-p+1;
            p = next[p]+1;
        }
        if (x>res) {
            res = x; cnt = 1;
        } else if (x==res){
            cnt++;
        }       
    }
    if (res==0) cnt = 1;
    out.println(res+" "+cnt);
}
}