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 t, d, ct, q, ans, l, m, r, n, mx, mn, i, j, k, x, y, z, s;
char ch;
string ss = "", str = "";
long long a[200003], b[200003];
int main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr);
  s = k = d = l = mx = m = mn = r = q = i = j = z = x = y = ct = ans = 0;
  stack<long long> st;
  cin >> ss;
  n = ss.length();
  long long dp[n + 2];
  memset(dp, 0, sizeof(dp));
  for (i = 0; i < n; i++) {
    if (ss[i] == '(') {
      st.push(i);
      continue;
    }
    if (st.empty()) continue;
    long long lft = st.top();
    st.pop();
    if (lft)
      dp[i] = dp[lft - 1] + i - lft + 1;
    else
      dp[i] = i - lft + 1;
    mx = max(mx, dp[i]);
  }
  for (i = 0; i < n; i++)
    if (dp[i] == mx) ct++;
  if (!mx) return cout << "0 1", 0;
  cout << mx << " " << ct;
  return 0;
}