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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastInputReader in = new FastInputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        public void solve(int testNumber, FastInputReader in, PrintWriter out) {
            String s = in.next();
            StringBuilder sR = new StringBuilder(s);
            sR.reverse();

            int open = 0, close = 0, max = 0, ans = 1;
            int openR = 0, closeR = 0, maxR = 0, ansR = 1;

            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                switch (c) {
                    case ')':
                        close++;
                        if (close > open) {
                            open = close = 0;
                        } else if (close == open) {
                            int current = open + close;
                            if (current == max && current > 0) {
                                ans++;
                            } else if (current > max) {
                                max = current;
                                ans = 1;
                            }
                        }
                        break;

                    case '(':
                        open++;
                        break;

                    default:
                        throw new RuntimeException("Invalid Input");
                }

                char cR = sR.charAt(i);
                switch (cR) {
                    case '(':
                        closeR++;
                        if (closeR > openR) {
                            openR = closeR = 0;
                        } else if (closeR == openR) {
                            int currentR = openR + closeR;
                            if (currentR == maxR && currentR > 0) {
                                ansR++;
                            } else if (currentR > maxR) {
                                maxR = currentR;
                                ansR = 1;
                            }
                        }
                        break;

                    case ')':
                        openR++;
                        break;

                    default:
                        throw new RuntimeException("Invalid Input");
                }
            }

            if (maxR > max) {
                out.println(maxR + " " + ansR);
            } else if (maxR < max) {
                out.println(max + " " + ans);
            } else {
                out.println(max + " " + Math.max(ans, ansR));
            }
        }

    }

    static class FastInputReader {
        final InputStream stream;
        final byte[] buf = new byte[8192];
        int curChar;
        int numChars;
        FastInputReader.SpaceCharFilter filter;

        public FastInputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) return -1;
            }
            return buf[curChar++];
        }

        public String next() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}