Ta có định nghĩa một dãy ngoặc đúng và bậc của dãy ngoặc đó bằng đệ quy như sau:

• Nếu ~A~ không có kí tự nào thì ~A~ là một dãy ngoặc đúng bậc ~0~.

• Nếu ~A~ là một dãy ngoặc đúng bậc ~a~, ~B~ là một dãy ngoặc đúng bậc ~b~ thì ~(A)~ là một dãy ngoặc đúng bậc ~a + 1~, ~AB~ là một dãy ngoặc đúng bậc ~max(a, b)~.

Cho một xâu ~S~ chỉ gồm các kí tự ~(~ và kí tự ~)~ cùng số ~K~, bạn cần trả lời ~2~ câu hỏi:

• ~1~. In ra số dãy con liên tiếp của ~S~ là một dãy ngoặc đúng bậc ~K~.

• ~2~. In ra độ dài của dãy con liên tiếp dài nhất của ~S~ là một dãy ngoặc đúng bậc ~K~.

Input

Gồm hai dòng:

• Dòng thứ nhất chứa xâu ~S~ (~1 \leq |S| \leq 10^5~) (trong đó ~|S|~ là độ dài của xâu ~S~).

• Dòng thứ hai chứa số ~K~ (~1 \leq K \leq 10^5~).

Output

• Dòng thứ nhất in ra câu trả lời của câu hỏi thứ nhất.

• Dòng thứ hai in ra câu trả lời của câu hỏi thứ hai, nếu không tồn tại dãy con liên tiếp của ~S~ là dãy ngoặc đúng bậc ~K~ thì in ra -1.

Scoring

• Subtask ~1~ (~30\%~ số điểm): ~|S| \leq 5000~.

• Subtask ~2~ (~70\%~ số điểm): không có ràng buộc gì thêm.

Sample Input 1

)(())(())(
2

Sample Output 1

3
8

Notes

Có 3 dãy con của ~S~ là dãy ngoặc đúng bậc ~2~: (()), (()), (())(()).

Trong đó, dãy ngoặc đúng bậc ~2~ dài nhất là (())(()).