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:
//package codeforces;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.Closeable;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class A implements Closeable {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    A() throws IOException {
//        reader = new BufferedReader(new FileReader("input.txt"));
//        writer = new PrintWriter(new FileWriter("output.txt"));
    }

    StringTokenizer stringTokenizer;

    String next() throws IOException {
        while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
            stringTokenizer = new StringTokenizer(reader.readLine());
        }
        return stringTokenizer.nextToken();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    private int MOD = 1000 * 1000 * 1000 + 7;

    int sum(int a, int b) {
        a += b;
        return a >= MOD ? a - MOD : a;
    }

    int product(int a, int b) {
        return (int) (1l * a * b % MOD);
    }

    int pow(int x, int k) {
        int result = 1;
        while (k > 0) {
            if (k % 2 == 1) {
                result = product(result, x);
            }
            x = product(x, x);
            k /= 2;
        }
        return result;
    }

    int inv(int x) {
        return pow(x, MOD - 2);
    }

    void solve() throws IOException {
        final char[] s = next().toCharArray();
        final int[] f = new int[s.length + 1];
        for(int i = 1; i <= s.length; i++) {
            f[i] = f[i - 1] + (s[i - 1] == '(' ? 1 : -1);
        }
        class SegmentTree {
            int q = 1;
            {
                while(q <= f.length) {
                    q *= 2;
                }
            }
            int[] a = new int[2 * q];
            {
                Arrays.fill(a, Integer.MAX_VALUE);
            }

            void set(int i, int x) {
                for(i += q; i > 0; i /= 2) {
                    a[i] = Math.min(a[i], x);
                }
            }

            int getMin(int l, int r) {
                int min = Integer.MAX_VALUE;
                for(l += q, r += q; l < r; l /= 2, r /= 2) {
                    if(l % 2 == 1) {
                        min = Math.min(min, a[l++]);
                    }
                    if(r % 2 == 1) {
                        min = Math.min(min, a[--r]);
                    }
                }
                return min;
            }
        }
        SegmentTree segmentTree = new SegmentTree();
        for(int i = 0; i < f.length; i++) {
            segmentTree.set(i, f[i]);
        }
        Map<Integer, List<Integer>> positions = new HashMap<>();
        for(int i = 0; i < f.length; i++) {
            List<Integer> pos = positions.get(f[i]);
            if(pos == null) {
                pos = new ArrayList<>();
                positions.put(f[i], pos);
            }
            pos.add(i);
        }
        int bestLen = 0, quantity = 1;
        for (Map.Entry<Integer, List<Integer>> entry : positions.entrySet()) {
            List<Integer> pos = entry.getValue();
            int j = 0;
            for(int i = 0; i < pos.size() - 1; i++) {
                j = Math.max(j, i);
                while(j + 1 < pos.size() && segmentTree.getMin(pos.get(i), pos.get(j + 1)) >= entry.getKey()) {
                    j++;
                }
                int len = pos.get(j) - pos.get(i);
                if(len > bestLen) {
                    bestLen = len;
                    quantity = 0;
                }
                if(len == bestLen) {
                    quantity++;
                }
            }
        }
        if(bestLen == 0) {
            quantity = 1;
        }
        writer.println(bestLen + " " + quantity);
    }

    public static void main(String[] args) throws IOException {
        try (A a = new A()) {
            a.solve();
        }
    }

    @Override
    public void close() throws IOException {
        reader.close();
        writer.close();
    }
}