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.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class _5C {

  public static void main(String[] args) throws Exception {
    Reader.init(System.in);
    BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));

    char[] seq = Reader.next().toCharArray();
    boolean[] good = new boolean[seq.length + 1];
    
    Stack<Integer> stack = new Stack<>();
    for (int i=0; i<seq.length; i++) {
      if (seq[i] == '(') stack.add(i);
      else {
        if (!stack.isEmpty()) {
          good[i] = true;
          good[stack.pop()] = true;
        }
      }
    }
    
    int maxLen = 0;
    int cnt = 1;
    
    int acc = 0;
    for (int i=0; i<good.length; i++)
      if (good[i]) acc++;
      else {
        if (acc > maxLen) {
          maxLen = acc;
          cnt = 1;
        } else if (acc == maxLen) cnt++;
        acc = 0;
      }
    
    if (maxLen == 0) cnt = 1;
    cout.write(String.format("%d %d%n", maxLen, cnt));
    cout.close();
  }

  static class Pair<U extends Comparable<U>, V extends Comparable<V>> implements Comparable<Pair<U, V>> {
    final U _1;
    final V _2;

    private Pair(U key, V val) {
      this._1 = key;
      this._2 = val;
    }

    public static <U extends Comparable<U>, V extends Comparable<V>> Pair<U, V> instanceOf(U _1, V _2) {
      return new Pair<U, V>(_1, _2);
    }

    @Override
    public String toString() {
      return _1 + " " + _2;
    }

    @Override
    public int hashCode() {
      int res = 17;
      res = res * 31 + _1.hashCode();
      res = res * 31 + _2.hashCode();
      return res;
    }

    @Override
    public int compareTo(Pair<U, V> that) {
      int res = this._1.compareTo(that._1);
      if (res < 0 || res > 0)
        return res;
      else
        return this._2.compareTo(that._2);
    }

    @Override
    public boolean equals(Object obj) {
      if (this == obj)
        return true;
      if (!(obj instanceof Pair))
        return false;
      Pair<?, ?> that = (Pair<?, ?>) obj;
      return _1.equals(that._1) && _2.equals(that._2);
    }
  }

  /** Class for buffered reading int and double values */
  static class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
      reader = new BufferedReader(new InputStreamReader(input));
      tokenizer = new StringTokenizer("");
    }

    /** get next word */
    static String next() throws IOException {
      while (!tokenizer.hasMoreTokens()) {
        // TODO add check for eof if necessary
        tokenizer = new StringTokenizer(reader.readLine());
      }
      return tokenizer.nextToken();
    }

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

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

  static class ArrayUtil {
    static void swap(int[] a, int i, int j) {
      int tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
    }

    static void swap(long[] a, int i, int j) {
      long tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
    }

    static void swap(double[] a, int i, int j) {
      double tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
    }

    static void swap(char[] a, int i, int j) {
      char tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
    }

    static void swap(boolean[] a, int i, int j) {
      boolean tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
    }

    static void reverse(int[] a, int i, int j) {
      for (; i < j; i++, j--)
        swap(a, i, j);
    }

    static void reverse(long[] a, int i, int j) {
      for (; i < j; i++, j--)
        swap(a, i, j);
    }

    static void reverse(double[] a, int i, int j) {
      for (; i < j; i++, j--)
        swap(a, i, j);
    }

    static void reverse(char[] a, int i, int j) {
      for (; i < j; i++, j--)
        swap(a, i, j);
    }

    static void reverse(boolean[] a, int i, int j) {
      for (; i < j; i++, j--)
        swap(a, i, j);
    }

    static long sum(int[] a) {
      int sum = 0;
      for (int i : a)
        sum += i;
      return sum;
    }

    static long sum(long[] a) {
      long sum = 0;
      for (long i : a)
        sum += i;
      return sum;
    }

    static double sum(double[] a) {
      double sum = 0;
      for (double i : a)
        sum += i;
      return sum;
    }

    static int max(int[] a) {
      int max = Integer.MIN_VALUE;
      for (int i : a)
        if (i > max)
          max = i;
      return max;
    }

    static int min(int[] a) {
      int min = Integer.MAX_VALUE;
      for (int i : a)
        if (i < min)
          min = i;
      return min;
    }

    static long max(long[] a) {
      long max = Long.MIN_VALUE;
      for (long i : a)
        if (i > max)
          max = i;
      return max;
    }

    static long min(long[] a) {
      long min = Long.MAX_VALUE;
      for (long i : a)
        if (i < min)
          min = i;
      return min;
    }
  }
}