Dãy ngoặc cấp k

Xét các dãy ngoặc đúng độ dài $N$ dùng một loại ngoặc. Độ sâu của một dãy là số ngoặc mở chưa được đóng lớn nhất khi quét từ trái sang phải. Giữ các dãy có độ sâu đúng bằng $k$, sắp chúng theo thứ tự từ điển với ( đứng trước ), rồi hãy đếm số dãy và tìm thứ hạng $1$-based của dãy truy vấn.

Input

• Dòng đầu chứa $N$ và $k$.
• Dòng thứ hai chứa một dãy ngoặc đúng độ dài $N$, có độ sâu lớn nhất đúng bằng $k$.

Output

• Dòng đầu in số dãy ngoặc đúng có độ sâu lớn nhất đúng bằng $k$.
• Dòng thứ hai in thứ hạng $1$-based của dãy đã cho.

Constraints

• $N$ chẵn, $2\le N\le 60$.
• $1\le k\le N/2$.
• Dãy truy vấn đúng và có độ sâu lớn nhất đúng bằng $k$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $N\le 30$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

6 2
(()())

3
1