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;
int clos_pos[1000010];
int recurse(int pos) {
  int next = clos_pos[pos];
  next--;
  if (next >= 0 && clos_pos[next] != -1) clos_pos[pos] = recurse(next);
  return clos_pos[pos];
}
int main() {
  string in;
  cin >> in;
  int N = in.size();
  int top = 0, max_glob = 0, max_tmp = 0, cnt = 0;
  bool found = false;
  int last = -1;
  vector<int> indx;
  memset(clos_pos, -1, sizeof(clos_pos));
  for (int i = 0; i < N; i++) {
    if (in[i] == '(') {
      top++;
      found = true;
      indx.push_back(i);
    }
    if (in[i] == ')') {
      if (indx.size() > 0) {
        int t = indx.size() - 1;
        clos_pos[i] = indx[t];
        indx.erase(indx.end() - 1);
      }
      if (top <= 0) continue;
      top--;
    }
    if (top == 0 && last > -1) {
      found = false;
      if (max_glob < (i - last + 1))
        max_glob = (i - last + 1), cnt = 1;
      else if (max_glob == (i - last + 1))
        cnt++;
      max_tmp = 0;
      last = -1;
    }
    if (found) max_tmp = max(max_tmp, top);
  }
  cnt = max_glob = 0;
  for (int i = 0; i < in.size(); i++)
    if (clos_pos[i] != -1) recurse(i);
  for (int i = 0; i < in.size(); i++)
    if (clos_pos[i] != -1) {
      int len = i - clos_pos[i] + 1;
      if (max_glob < len)
        max_glob = len, cnt = 1;
      else if (max_glob == len)
        cnt++;
    }
  if (max_glob == 0)
    cout << 0 << " " << 1 << "\n";
  else
    cout << max_glob << " " << cnt << "\n";
  return 0;
}