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.ArrayDeque;
import java.util.InputMismatchException;
import java.util.Deque;
import java.util.Arrays;

public class Main {
    static InputStream inStream;
    static PrintWriter out = new PrintWriter(System.out);
    static String INPUT = "";
    static Deque<Integer> lefts = new ArrayDeque<Integer>();


    public static void main(String[] args) throws IOException {
        inStream = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());

        StringBuilder input = nextStringBuilder();
        int start = 0;
        Integer lastLeft = 0;
        int longest=0;
        int curLen=-1;
        int longCounter=1;


        for(int i=0; i<input.length(); i++){
            if(input.charAt(i)=='('){
                lefts.push(i);
            }
            else {
                if(lefts.isEmpty()){
                    start = i+1;
                }
                else {
                    lefts.pop();

                    if(lefts.isEmpty()){
                        curLen = i - start + 1;
                    }
                    else{
                        lastLeft = lefts.peek();
                        curLen = i - lastLeft;
                    }
                }

                if(curLen > longest){
                    longest = curLen;
                    longCounter=1;
                }
                else if(curLen == longest){
                    longCounter++;
                }
                curLen=-1;
            }
        }

        if(longest==0){
            out.println("0 1");
        }
        else{
            out.print(longest);
            out.print(" ");
            out.println(longCounter);
        }
        out.flush();
    }


    private static boolean eof() {
        if (lenbuf == -1) return true;
        int lptr = ptrbuf;
        while (lptr < lenbuf) if (!isSpaceChar(inbuf[lptr++])) return false;
        try {
            inStream.mark(1000);
            while (true) {
                int b = inStream.read();
                if (b == -1) {
                    inStream.reset();
                    return true;
                } else if (!isSpaceChar(b)) {
                    inStream.reset();
                    return false;
                }
            }
        } catch (IOException e) {
            return true;
        }
    }

    private static byte[] inbuf = new byte[1024];
    static int lenbuf = 0, ptrbuf = 0;

    private static int readByte() {
        if (lenbuf == -1) throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {
                lenbuf = inStream.read(inbuf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (lenbuf <= 0)
                return -1;
        }
        return inbuf[ptrbuf++];
    }

    private static boolean isSpaceChar(int c) {
        return !(c >= 33 && c <= 126);
    }

    private static int skip() {
        int b;
        while ((b = readByte()) != -1 && isSpaceChar(b)) ;
        return b;
    }

    private static double nextDouble() {
        return Double.parseDouble(nextString());
    }

    private static char nextChar() {
        return (char) skip();
    }

    private static String nextString() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private static StringBuilder nextStringBuilder() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb;
    }

    private static char[] nextString(int n) {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) {
            buf[p++] = (char) b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }

    private static int[] nextArray0(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nextInt();
        return a;
    }

    private static int[] nextArray1(int n) {
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++)
            a[i] = nextInt();
        return a;
    }

    private static long[] nextArrayLong1(int n) {
        long[] a = new long[n + 1];
        for (int i = 1; i <= n; i++)
            a[i] = nextLong();
        return a;
    }

    private static long[] nextArrayLong0(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = nextLong();
        return a;
    }

    private static int nextInt() {
        int num = 0, b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private static long nextLong() {
        long num = 0;
        int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
}