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;
bool rev(long long x, long long y) { return x > y; }
void input_arr(long long a[], long long n) {
  for (long long i = 0; i < n; i += 1) cin >> a[i];
}
bool sortbysec(const pair<long long, long long> &a,
               const pair<long long, long long> &b) {
  return a.second < b.second;
}
bool sortinrev(const pair<long long, long long> &a,
               const pair<long long, long long> &b) {
  return (a.first > b.first);
}
void print_vec(vector<long long> &v) {
  for (auto i : v) cout << i << " ";
  cout << '\n';
}
bool sortinrevbysec(const pair<long long, long long> &a,
                    const pair<long long, long long> &b) {
  return (a.second > b.second);
}
void print_arr(long long a[], long long n) {
  for (long long i = 0; i < n; i += 1) cout << a[i] << " ";
  cout << '\n';
}
template <typename... T>
void input(T &...args) {
  ((cin >> args), ...);
}
template <typename... T>
void print(T &&...args) {
  ((cout << args << '\n'), ...);
}
template <typename... T>
void deb(T &&...args) {
  cout << "~~ ";
  ((cout << args << " "), ...);
  cout << '\n';
}
vector<long long> visited(1000001, 0);
long long val;
map<long long, long long> mp1, ans, edges;
long long j;
void dfs(long long z) {
  visited[z]++;
  j = z;
  if (mp1[z] > 0 && visited[edges[z]] == 0) {
    val += abs(edges[z] - z);
    dfs(edges[z]);
  }
}
void stand8th() {
  string s;
  input(s);
  stack<long long> stk;
  long long MX = INT64_MIN;
  for (long long i = 0; i < (long long)(s.size()); i += 1) {
    if (s[i] == '(') {
      stk.push(i);
    } else {
      if ((long long)(stk.size()) > 0) {
        MX = max(MX, abs(i - stk.top()) + 1);
        edges[stk.top()] = i + 1;
        mp1[stk.top()]++;
        stk.pop();
      }
    }
  }
  if (MX == INT64_MIN) {
    cout << 0 << " " << 1 << '\n';
    return;
  }
  for (long long i = 0; i < (long long)(s.size()); i += 1) {
    if (mp1[i] > 0 && visited[i] == 0) {
      val = 0;
      dfs(i);
      i = j;
      ans[val]++;
    }
  }
  auto it = ans.end();
  it--;
  cout << it->first << " " << it->second << '\n';
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long tin = 1;
  while (tin--) {
    stand8th();
  }
  return 0;
}