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 \(A\) là một dãy ngoặc đúng, thì
(
\(A\))
là một dãy ngoặc đúng. - Nếu \(A\) và \(B\) là hai dãy ngoặc đúng thì \(AB\) 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ự \(s\) là một dãy ngoặc đúng cùng dãy \(q\) số \(p_1, p_2, \ldots, p_q\). Bạn cần thực hiện lần lượt \(q\) thao tác. Tại thao tác thứ \(i\), bạn cần làm những việc sau:
- Thay đổi kí tự thứ \(p_i\) của \(s\) (từ
(
sang)
hoặc ngược lại). - Tìm vị trí \(a_i\) là vị trí nhỏ nhất sao cho nếu thay đổi kí tự ở vị trí \(a_i\) (từ
(
sang)
hoặc ngược lại) thì xâu kí tự \(s\) trở thành dãy ngoặc đúng. - In ra vị trí \(a_i\) 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 \(s\) đang là dãy ngoặc đúng. Do đó, việc thay đổi kí tự thứ \(p_i\) khiến \(s\) 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í \(a_i\) cần tìm ở trên là luôn tồn tại. Khi thay đổi kí tự ở vị trí \(a_i\), \(s\) trở lại là dãy ngoặc đúng.
Input
-
Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n \leq 1000000, 1 \leq q \leq 600000)\), lần lượt là độ dài của dãy ngoặc \(s\) và số thao tác bạn cần thực hiện.
-
Dòng thứ hai chứa xâu kí tự \(s\) là một dãy ngoặc đúng độ dài \(n\).
-
Dòng thứ ba chứa \(q\) số nguyên \(p_1, p_2, \ldots, p_q\) \((1 \leq p_q \leq n)\) mô tả các thao tác cần thực hiện.
Output
- In ra \(q\) số nguyên \(a_1, a_2, \ldots, a_q\) 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.
Scoring
Bộ test của bài được chia làm các subtask như sau:
- Subtask \(1\) (\(14.4\) điểm): \(n \leq 500\) và \(q \leq 300\)
- Subtask \(2\) (\(15.6\) điểm): \(n \leq 7000\) và \(q \leq 4200\)
- Subtask \(3\) (\(14.4\) điểm): \(n \leq 200000\) và \(q \leq 120000\)
- Subtask \(4\) (\(15.6\) điểm): \(n \leq 1000000\) và \(q \leq 600000\)
Điểm tối đa của bài là \(60\) điểm.
Example
Test 1
Input
6 3
((()))
4 3 1
Output
2 2 1
Note
Trong ví dụ trên, ban đầu dãy ngoặc \(s\) 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í \(p_1 = 4\), \(s\) trở thành
(((())
. Để \(s\) trở lại là dãy ngoặc đúng, bạn cần thay đổi kí tự ở vị trí \(a_1 = 2\). Khi đó \(s\) trở thành()(())
. - Thao tác tiếp theo: Sau khi thay đổi kí tự ở vị trí \(p_2 = 3\), \(s\) trở thành
())())
. Để \(s\) trở lại là dãy ngoặc đúng, bạn cần thay đổi kí tự ở vị trí \(a_2 = 2\). Khi đó \(s\) trở thành(()())
. - Thao tác cuối cùng: Sau khi thay đổi kí tự ở vị trí \(p_3 = 1\), \(s\) trở thành
)()())
. Để \(s\) trở lại là dãy ngoặc đúng, bạn cần thay đổi kí tự ở vị trí \(a_3 = 1\). Khi đó \(s\) trở thành(()())
.
Comments