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 maxn = 1000005;
namespace sxdaknoip {
stack<unsigned> sta;
priority_queue<unsigned> q;
int f[maxn];
int main() {
  string s;
  cin >> s;
  for (unsigned i = 0; i < s.length(); ++i) {
    if (s[i] == ')') {
      if (!sta.empty()) {
        int top = sta.top();
        sta.pop();
        f[i] = i - top + 1;
      }
    } else
      sta.push(i);
  }
  for (unsigned i = 0; i < s.length(); ++i)
    if ((int)i != f[i] && f[i] && f[i - f[i]]) f[i] += f[i - f[i]];
  int maxx = 0, maxnn = 1;
  for (unsigned i = 0; i < s.length(); ++i) {
    if (f[i]) {
      if (f[i] > maxx) {
        maxx = f[i];
        maxnn = 1;
      } else if (f[i] == maxx)
        maxnn++;
    }
  }
  cout << maxx << ' ' << maxnn;
  return 0;
}
}  // namespace sxdaknoip
int main() {
  sxdaknoip::main();
  return 0;
}