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.Vector;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.Stack;
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;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ProblemCLongestRegularBracketSequence solver = new ProblemCLongestRegularBracketSequence();
        solver.solve(1, in, out);
        out.close();
    }

    static class ProblemCLongestRegularBracketSequence {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            String st = in.next();
            int sl = st.length();
            int max = 0, tct = 1;
            Stack<ProblemCLongestRegularBracketSequence.val> s = new Stack<ProblemCLongestRegularBracketSequence.val>();
            for (int i = 0; i < sl; i++) {
                if (st.charAt(i) == '(') {
                    s.push(new ProblemCLongestRegularBracketSequence.val('('));
                } else {
                    if (!s.isEmpty()) {
                        ProblemCLongestRegularBracketSequence.val curr = s.pop();
                        if (curr.b) {
                            if (!s.isEmpty() && s.peek().val == '(' && !s.peek().b) {
                                s.pop();
                                if (!s.isEmpty() && s.peek().b) {
                                    s.peek().val += curr.val + 2;
                                } else {
                                    curr.val += 2;
                                    s.push(curr);
                                }
                            } else {
                                s.push(curr);
                                s.push(new ProblemCLongestRegularBracketSequence.val(')'));
                            }
                        } else if (curr.val == '(') {
                            if (!s.isEmpty() && s.peek().b) {
                                s.peek().val += 2;
                            } else {
                                curr.val = 2;
                                curr.b = true;
                                s.push(curr);
                            }
                        } else {
                            s.push(new ProblemCLongestRegularBracketSequence.val(')'));
                        }
                    }
                }
            }
            for (ProblemCLongestRegularBracketSequence.val i : s) {
                //System.out.println(i.val+" "+i.b);
                if (i.b) {
                    if (i.val > max) {
                        max = i.val;
                        tct = 1;
                    } else if (i.val == max) {
                        tct++;
                    }
                }
            }
            out.println(max + " " + tct);
        }

        static class val {
            boolean b;
            int val;

            val(int v) {
                val = v;
            }

        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(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 readString() {
            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 String next() {
            return readString();
        }

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

        }

    }
}