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

/**
 * Created by HREN_VAM.
 */

public class C implements Runnable{

    BufferedReader in;
    PrintWriter out;
    StringTokenizer st;
    public static final String filename = "c";

    public void solve() throws IOException{
        String s = nextToken();
        int n = s.length();
        int[] level = new int[2 * n + 5];
        for(int i = 0;i < 2 * n + 5;i ++){
            level[i] = -1;
        }
        int middle = (n + 1);
        int curLevel = 0;
        int max = 0;
        int count = 1;
        for(int i = 0;i < n + 1;i ++){
            if((level[middle + curLevel] != -1) && (max == i - level[middle + curLevel]))count ++;
            if((level[middle + curLevel] != -1) && (max < i - level[middle + curLevel])){
                max = i - level[middle + curLevel];
                count = 1;
            }
            if(i == n)break;
            if(s.charAt(i) == '('){
                if(level[middle + curLevel] == -1)level[middle + curLevel] = i;
                curLevel ++;
            }else{
                level[middle + curLevel] = -1;
                curLevel --;
            }
        }
        out.println(max + " " + count);
    }

    public void run(){
        try{
            Locale.setDefault(Locale.US);
            in = new BufferedReader(new InputStreamReader(System.in));
            //in = new BufferedReader(new FileReader(filename + ".in"));
            out = new PrintWriter(System.out);
            //out = new PrintWriter(new FileWriter(filename + ".out"));
            st = new StringTokenizer("");
            solve();
            out.close();
        } catch(IOException e){
            throw new RuntimeException(e);
        }
    }

    public static void main(String[] args){
        new Thread(new C()).start();
    }

    public String nextToken() throws IOException{
        while(!st.hasMoreTokens()){
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }

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

    public double nextDouble() throws IOException{
        return Double.parseDouble(nextToken());
    }
}