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 N = 1e6 + 10;
char s[N];
int to[N];
vector<pair<int, char> > v;
vector<int> ans;
int main() {
  scanf("%s", s);
  int len = strlen(s);
  memset(to, -1, sizeof(to));
  for (int i = 0; i < len; ++i) {
    if (v.empty()) {
      v.push_back(make_pair(i, s[i]));
    } else {
      pair<int, char> tmp = v.back();
      if (tmp.second == '(' && s[i] == ')') {
        assert((i - tmp.first + 1) % 2 == 0);
        to[tmp.first] = i;
        v.pop_back();
      } else {
        v.push_back(make_pair(i, s[i]));
      }
    }
  }
  int cnt = 0;
  for (int i = 0; i <= len; ++i) {
    if (s[i] == '(') {
      if (to[i] >= 0) {
        cnt += to[i] - i + 1;
        i = to[i];
      } else {
        ans.push_back(cnt);
        cnt = 0;
      }
    } else {
      ans.push_back(cnt);
      cnt = 0;
    }
  }
  int mx = 0, cc = 0;
  for (int i = 0; i < ans.size(); ++i) {
    mx = max(mx, ans[i]);
  }
  for (int i = 0; i < ans.size(); ++i) {
    if (mx == ans[i]) {
      ++cc;
    }
  }
  if (mx == 0) {
    printf("0 1\n");
  } else {
    printf("%d %d\n", mx, cc);
  }
  return 0;
}