Dãy ngoặc là một dãy chỉ gồm các kí tự mở ngoặc ( và đóng ngoặc ). Dãy ngoặc đúng là một dãy ngoặc được xây dựng dựa trên quy tắc sau:
Dãy ngoặc rỗng là một dãy ngoặc đúng.
Nếu là một dãy ngoặc đúng, thì () là một dãy ngoặc đúng.
Nếu và là hai dãy ngoặc đúng thì cũng là dãy ngoặc đúng.
Ví dụ, (()), ()() và ()(()) là các dãy ngoặc đúng; còn )( hay (() thì không.
Bạn được cho một xâu kí tự là một dãy ngoặc đúng cùng dãy số . Bạn cần thực hiện lần lượt thao tác. Tại thao tác thứ , bạn cần làm những việc sau:
Thay đổi kí tự thứ của (từ ( sang ) hoặc ngược lại).
Tìm vị trí là vị trí nhỏ nhất sao cho nếu thay đổi kí tự ở vị trí (từ ( sang ) hoặc ngược lại) thì xâu kí tự trở thành dãy ngoặc đúng.
In ra vị trí vừa tìm được và thay đổi kí tự ở vị trí này.
Chú ý rằng, ở bất kì thao tác nào, bạn bắt đầu khi xâu đang là dãy ngoặc đúng. Do đó, việc thay đổi kí tự thứ khiến bây giờ chắc chắn không phải dãy ngoặc đúng, và ta dễ dàng chứng minh được vị trí cần tìm ở trên là luôn tồn tại. Khi thay đổi kí tự ở vị trí , trở lại là dãy ngoặc đúng.
Dữ liệu vào:
Dòng đầu tiên chứa hai số nguyên và , lần lượt là độ dài của dãy ngoặc và số thao tác bạn cần thực hiện;
Dòng thứ hai chứa xâu kí tự là một dãy ngoặc đúng độ dài ;
Dòng thứ ba chứa số nguyên mô tả các thao tác cần thực hiện.
Dữ liệu ra:
In ra số nguyên là các vị trí tìm được ở các thao tác. Các số cần được viết trên một dòng, ngăn cách với nhau bởi dấu cách.
Ví dụ:
Dữ liệu vào:
6 3
((()))
4 3 1
Dữ liệu ra:
2 2 1
Giải thích:
Trong ví dụ trên, ban đầu dãy ngoặc là ((())). Các thao tác diễn ra như sau:
Thao tác đầu tiên: Sau khi thay đổi kí tự ở vị trí , trở thành (((()). Để trở lại là dãy ngoặc đúng, bạn cần thay đổi kí tự ở vị trí . Khi đó trở thành ()(()).
Thao tác tiếp theo: Sau khi thay đổi kí tự ở vị trí , trở thành ())()). Để trở lại là dãy ngoặc đúng, bạn cần thay đổi kí tự ở vị trí . Khi đó trở thành (()()).
Thao tác cuối cùng: Sau khi thay đổi kí tự ở vị trí , trở thành )()()). Để trở lại là dãy ngoặc đúng, bạn cần thay đổi kí tự ở vị trí . Khi đó trở thành (()()).
Giới hạn:
Bộ test của bài được chia làm các subtask như sau:
