Dãy ngoặc đúng

Cho một chuỗi không rỗng chỉ gồm các ký tự ( và ) có độ dài không vượt quá \(10^6\).

Một chuỗi ngoặc được gọi là đúng định dạng (regular) nếu có thể chèn các ký tự + và 1 vào nó để được một biểu thức toán học hợp lệ. Ví dụ: (())(), (), (()(())) là đúng định dạng; còn )(, ((), (()))( thì không đúng định dạng.

Hãy tìm:

• độ dài lớn nhất của một đoạn con liên tiếp của chuỗi đầu vào mà nó là chuỗi ngoặc đúng định dạng;
• số lượng các đoạn con như vậy có độ dài lớn nhất.

Nếu không có đoạn con nào đúng định dạng, in ra 0 1.

\InputFile

Một dòng chứa một chuỗi gồm các ký tự ( và ). Độ dài của chuỗi không vượt quá \(10^6\).

\OutputFile

In ra hai số nguyên: đầu tiên là độ dài lớn nhất của đoạn ngoặc đúng định dạng tìm được; tiếp theo là số lượng đoạn con có độ dài đó.

\Examples

\beginexample
\exmp)((())))(()())
6 2

\exmp))(
0 1

\endexample

\Scoring

• Subtask 1 (20 điểm): \(n \le 100\)
• Subtask 2 (20 điểm): \(n \le 1000\)
• Subtask 3 (60 điểm): \(n \le 10^6\)