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;
long long INF = 1e18;
long long Pow(long long a, long long b, long long m) {
  if (b == 0) return 1;
  if (b % 2 == 0) {
    long long x = a * a;
    x %= m;
    return Pow(x, b / 2, m);
  }
  return (a * Pow(a, b - 1, m)) % m;
}
bool isPowerOfTwo(int x) { return x && (!(x & (x - 1))); }
int main() {
  string s;
  cin >> s;
  long long n = s.length();
  long long dp[n + 1];
  memset(dp, 0, sizeof(dp));
  ;
  for (long long i = 1; i <= (n - 1); i++) {
    long long j = i + 1;
    if (s[i] == ')') {
      if (s[i - 1] == '(')
        dp[j] = dp[j - 2] + 2;
      else {
        if ((j - 1) - dp[j - 1] - 1 >= 0 && s[(j - 1) - dp[j - 1] - 1] == '(') {
          dp[j] = dp[j - 1] + 2 + dp[(j - 1) - dp[j - 1] - 1];
        }
      }
    }
  }
  long long maxi = 0;
  long long ans = 0;
  for (long long i = 1; i <= (n); i++) {
    maxi = max(maxi, dp[i]);
  }
  for (long long i = 1; i <= (n); i++) {
    if (dp[i] == maxi) ans++;
  }
  if (maxi == 0) ans = 1;
  cout << maxi << " " << ans;
}