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 C {

    private static final long modulo = 1000000007;

    private static void solve() {
        String seq = in.nextLine();
        long max = 0;
        long count = 1;
        List<Integer> stack = new ArrayList<>();
        stack.add(-1);
        for (int i = 0; i < seq.length(); i++) {
            if (seq.charAt(i) == '(') {
                stack.add(i);
            } else {
                int stackSize = stack.size();
                if (stackSize == 1) {
                    stack.set(0, i);
                } else {
                    stack.remove(stackSize - 1);
                    int beginPos = stack.get(stackSize - 2);
                    int length = i - beginPos;
                    if (length > max) {
                        max = length;
                        count = 0;
                    }
                    if (length == max) count++;
                }
            }
        }
        out.println(max + " " + count);
    }


    private static long inverse(long a) {
        long result = 1;
        int n = (int) modulo - 2;
        while (n != 0) {
            if ((n & 1) == 1)
                result = (result * a) % modulo;
            a = (a * a) % modulo;
            n >>= 1;
        }
        return result;
    }

    private static long pow(long a, long n) {
        if (n == 0) return 1;
        if (n % 2 == 0) {
            long ans = pow(a, n / 2);
            return ans * ans;
        } else {
            return a * pow(a, n - 1);
        }
    }


    public static void main(String[] args) {
        solve();
        closeStreams();
    }

    private static void closeStreams() {
        in.close();
        out.close();
    }


    private static final FastScanner in = new FastScanner();
    private static final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    public static class FastScanner {

        private BufferedReader br;
        private StringTokenizer st;

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                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());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        void close() {
            try {
                br.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

    }
}