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 PYTHON3):

Solution:
'''
Jana Goodman

5c longest reg bracket sequence

'''
import sys

class Stack:
    def __init__(self):
        self.stack = list()
        self.len = 0

    def is_empty(self):
        return self.len == 0

    def top(self):
        if self.is_empty():
            return None
        return self.stack[-1]

    def push(self, elt):
        self.stack.append(elt)
        self.len += 1

    def pop(self):
        if self.is_empty():
            return None
        self.len -= 1
        return self.stack.pop(-1)

    def clear(self):
        self.stack = list()
        self.len = 0

    def replace(self, pos, elt):
        self.stack[pos] = elt

    def __repr__(self):
        return f'Stack: {self.stack}'

CLOSE = ')'
OPEN = '('

def max_regular(s):
    max_len, num_maxes, reg_len = 0, 0, None
    good_start = -1
    stack = Stack()
    for i, p in enumerate(s):
        if p == OPEN:
            stack.push(i)
        elif p == CLOSE:
            if stack.is_empty():
                good_start = i
            else:
                stack.pop()
                if stack.is_empty():
                    reg_len = i - good_start
                else:
                    reg_len = i - stack.top()
                if max_len < reg_len:
                    max_len, num_maxes = reg_len, 1
                elif max_len == reg_len:
                    num_maxes += 1

    return max_len, num_maxes

if __name__ == '__main__':
    seq = input().strip()
    max_len, num_maxes = max_regular(seq)
    if max_len == 0:
        num_maxes = 1
    print(f'{max_len} {num_maxes}')