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;
string s;
vector<vector<int> > Q(2000001);
vector<int> C;
vector<int> M;
int main() {
  int n;
  getline(cin, s);
  C.push_back(0);
  int w = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == ')')
      w--;
    else
      w++;
    C.push_back(w);
  }
  for (int i = 0; i < C.size(); i++) C[i] += 1000000;
  M.push_back(-1);
  for (int i = 1; i < C.size(); i++) {
    int j = i - 1;
    while (j >= 0 && C[j] >= C[i]) {
      j = M[j];
    }
    M.push_back(j);
  }
  for (int i = 0; i < C.size(); i++) Q[C[i]].push_back(i);
  int r1 = 0, r2 = 0;
  for (int i = 0; i < C.size(); i++) {
    int x = M[i];
    int l, r;
    if (x == -1) {
      if (Q[C[i]].empty())
        l = -1;
      else
        l = 0;
    } else {
      if (Q[C[i]].empty()) continue;
      l = 0;
      r = Q[C[i]].size() - 1;
      while (l < r) {
        int e = (l + r) / 2;
        if (Q[C[i]][e] < x)
          l = e + 1;
        else
          r = e;
      }
    }
    if (l != -1) r1 = max(r1, abs(i - Q[C[i]][l]));
  }
  if (r1 == 0) {
    cout << 0 << ' ' << 1 << endl;
  } else {
    int l = 0, r = r1;
    while (r < C.size()) {
      if (C[l] == C[r] && M[r] < l) r2++;
      l++;
      r++;
    }
    cout << r1 << ' ' << r2 << endl;
  }
  cin >> n;
  return 0;
}