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
 *
 * @author Pranay2516
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CLongestRegularBracketSequence solver = new CLongestRegularBracketSequence();
        solver.solve(1, in, out);
        out.close();
    }

    static class CLongestRegularBracketSequence {
        public void solve(int testNumber, FastReader in, PrintWriter out) {
            char[] c = in.next().toCharArray();
            int n = c.length;
            Stack<Integer> st = new Stack<>();
            for (int i = 0; i < n; ++i) {
                if (c[i] == '(') st.push(i);
                else {
                    if (!st.isEmpty() && c[st.peek()] == '(') st.pop();
                    else st.push(i);
                }
            }
            st.push(n);
            if (st.size() == n + 1) out.println("0 1");
            else if (st.size() == 1 && st.peek() == n) out.println(n + " " + 1);
            else {
                int cur = st.pop(), h = st.peek(), cnt = 0, max = cur - h - 1;
                while (!st.isEmpty()) {
                    if (max < cur - h - 1) {
                        max = cur - h - 1;
                        cnt = 1;
                    } else if (max == cur - h - 1) cnt++;
                    cur = st.pop();
                    if (st.isEmpty()) {
                        if (max < cur) {
                            out.println(cur + " 1");
                            return;
                        }
                        if (max == cur) cnt++;
                        break;
                    }
                    h = st.peek();
                }
                out.println(max + " " + cnt);
            }
        }

    }

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

        public FastReader(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);

        }

    }
}