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;
using ll = long long;
void solve() {
  string ins;
  cin >> ins;
  int siz = ins.size();
  vector<int> match(siz, -1);
  for (int i = 0; i <= siz - 1; ++i) {
    stack<int> stk;
    for (int j = i; j <= siz - 1; ++j) {
      if (ins[j] == '(')
        stk.push(j);
      else if (ins[j] == ')') {
        if (stk.empty() == true) {
          i = j;
          break;
        }
        match[j] = stk.top();
        match[stk.top()] = j;
        stk.pop();
      }
      if (j == siz - 1) {
        i = j;
        break;
      }
    }
  }
  int nowL = 0, maxL = 0, maxLC = 1;
  for (int i = 0; i <= siz; ++i) {
    if (match[i] == -1 || i == siz) {
      if (nowL > maxL) {
        maxL = nowL;
        maxLC = 1;
      } else if (nowL == maxL) {
        ++maxLC;
      }
      nowL = 0;
    } else {
      ++nowL;
    }
  }
  if (maxL == 0) maxLC = 1;
  cout << maxL << ' ' << maxLC << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  std::cout.tie(NULL);
  solve();
  cout.flush();
  return 0;
}