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;
vector<int> vec[1000009];
int nm[1000009];
int arr[1000009], seg[4000500];
map<int, int> mp;
void create(int lo, int hi, int pos) {
  if (lo == hi) {
    seg[pos] = arr[lo];
    return;
  }
  int m = (lo + hi) / 2;
  create(lo, m, 2 * pos);
  create(m + 1, hi, 2 * pos + 1);
  seg[pos] = min(seg[2 * pos], seg[2 * pos + 1]);
}
int query(int qlo, int qhi, int lo, int hi, int pos) {
  if (qlo <= lo && qhi >= hi) {
    return seg[pos];
  }
  if (qlo > hi || qhi < lo) {
    return 999999999;
  }
  int m = (lo + hi) / 2;
  return min(query(qlo, qhi, lo, m, 2 * pos),
             query(qlo, qhi, m + 1, hi, 2 * pos + 1));
}
int main() {
  int a, b, c, d, e, i, j, k, l, n, m, x, y, t, p, mx, ans;
  ;
  string st;
  cin >> st;
  l = st.size();
  arr[1] = 0;
  l++;
  for (i = 2; i <= l; i++) {
    if (st[i - 2] == ')') {
      arr[i] = arr[i - 1] - 1;
    } else {
      arr[i] = arr[i - 1] + 1;
    }
  }
  c = 1;
  for (i = 1; i <= l; i++) {
    a = arr[i];
    if (mp[a] == 0) {
      mp[a] = c;
      nm[c] = a;
      c++;
    }
    a = mp[a];
    vec[a].push_back(i);
  }
  create(1, l, 1);
  mx = 0;
  ans = 1;
  for (i = 1; i < c; i++) {
    n = vec[i].size();
    n--;
    int temp = 0, left, right;
    for (j = 0; j < n; j++) {
      left = vec[i][j];
      right = vec[i][j + 1];
      x = query(left, right, 1, l, 1);
      if (x == nm[i]) {
        temp += (right - left);
        if (temp > mx) {
          mx = temp;
          ans = 1;
        } else if (temp == mx) {
          ans++;
        }
      } else {
        temp = 0;
      }
    }
  }
  printf("%d %d\n", mx, ans);
}