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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int maxx = 1000000 + 100;
struct node {
  char c;
  int no;
};
node s[maxx];
node x[maxx];
int main() {
  string y;
  while (cin >> y) {
    int i, j;
    int len = y.length();
    for (i = 0; i < len; i++) {
      s[i].c = y[i];
      s[i].no = i + 1;
    }
    for (i = 0; i < len; i++) {
      if (y[i] == '(') break;
    }
    int ans = 0;
    int re = 0, rep = 1;
    int k = 0;
    int temp, lrep = 1;
    for (; i < len - 1; i++) {
      k = 0;
      ans = 0;
      for (j = i; j < len; j++) {
        if (s[j].c == '(') {
          x[k++] = s[j];
          continue;
        } else if (s[j].c == ')') {
          if (k == 0) {
            break;
          } else if (x[k - 1].c == '(') {
            k--;
            ans += 2;
          }
        }
      }
      int kk = k;
      int flag = 0;
      if (k != 0) {
        ans = (x[0].no - i - 1);
        for (; k > 1; k--) {
          temp = x[k - 1].no - x[k - 2].no - 1;
          if (temp > ans) {
            ans = temp;
            lrep = 1;
            continue;
          }
          if (temp == ans && ans != 0) lrep++;
        }
        flag = 1;
      }
      if (ans > re) {
        re = ans;
        rep = lrep;
        if (len - i < ans) break;
        if (flag == 0)
          i += (re - 1);
        else
          i = (x[kk - 1].no - 1);
        continue;
      }
      if (ans == re && ans > 0) {
        rep++;
      }
      if (len - 1 - i < ans) break;
      if (ans != 0 && flag == 0)
        i += (ans - 1);
      else if (flag == 1)
        i = (x[kk - 1].no - 1);
      ans = 0;
    }
    printf("%d %d\n", re, rep);
  }
  return 0;
}