Trong ngôn ngữ lập trình LISP, mọi thứ được viết bên trong các cặp ngoặc cân bằng. Vì vậy mã LISP đôi khi có những đoạn rất dài chỉ gồm dấu ngoặc đóng ), và việc viết đúng số lượng dấu ngoặc này khá phiền toái.

Để tránh lỗi cú pháp, một số phương ngữ LISP có dấu ngoặc đóng ma thuật ], thay cho một hoặc nhiều dấu ) sao cho các dấu ( được cân bằng đúng. Hãy xác định số dấu ) mà mỗi dấu ] thay thế. Nếu có nhiều đáp án, được phép in bất kỳ đáp án nào.

Dữ liệu vào

Dòng đầu gồm hai số nguyên \(N, M\) (\(0 \le N \le 10\,000\,000\), \(0 \le M \le 5\,000\,000\)), lần lượt là độ dài xâu và số dấu ngoặc ma thuật.

Phần còn lại của tệp, bắt đầu từ dòng thứ hai, là một xâu dài \(N\) chỉ gồm (, ) và ]; ký tự ] xuất hiện đúng \(M\) lần. Để dễ đọc, xâu được chia thành các dòng, mỗi dòng không quá \(72\) ký tự.

Dữ liệu ra

Dòng đầu in 0 hoặc 1.

Nếu không thể cân bằng xâu, in 0 và không in thêm gì.

Nếu có thể cân bằng, in 1, sau đó in thêm đúng \(M\) dòng. Dòng thứ \(i\) chứa số nguyên \(C_i \ge 1\), là số dấu ) mà dấu ] thứ \(i\) trong xâu thay thế.

Ví dụ

8 2
(((((])]

1
3
1