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.*;
import java.lang.*;
import java.util.concurrent.ConcurrentHashMap;

import static java.lang.Math.*;

public class Main {
    static int int_max = Integer.MAX_VALUE;
    static int temp = 0;
    static HashMap<String, Boolean> map = new HashMap<>();

    /*static ArrayList<Integer> arr =new ArrayList<>();*/
    public static void main(String[] args) throws IOException {
        BufferedReader in;
        PrintWriter out;
        StringTokenizer st = new StringTokenizer("");

        FastReader sc = new FastReader();
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        char[] s = in.readLine().toCharArray();
        int[] stack = new int [s.length + 1];
        int[] cnt = new int [s.length + 1];
        int sp = 0;
        int last = 0;

        for (char c : s) {
            if (c == '(') {
                stack[++sp] = last + 1;
                last = 0;
            } else if (sp > 0) {
                int len = stack[sp--] + 1 + last;
                cnt[len]++;
                last = len;
            } else {
                last = 0;
            }
        }

        for (int i = s.length; i >= 0; i--) {
            if (cnt[i] > 0) {
                out.println(i + " " + cnt[i]);
                out.close();
                return;
            }
        }

        out.println("0 1");
        out.close();
    }


    static long lcm(long a, long b) {
        return (a / gcd(a, b)) * b;
    }

    static long gcd(long a, long b) {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }

    public static class FastReader {
        BufferedReader br;
        StringTokenizer st;

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


}