{"code":"pvhoi20b3bra","name":"PVHOI 2.0 - Bài 3: Biến đổi dãy ngoặc","description":"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:\r\n- Dãy ngoặc rỗng là một dãy ngoặc đúng.\r\n- Nếu $A$ là một dãy ngoặc đúng, thì ``(``$A$``)`` là một dãy ngoặc đúng.\r\n- Nếu $A$ và $B$ là hai dãy ngoặc đúng thì $AB$ cũng là dãy ngoặc đúng.\r\n\r\nVí dụ, ``(())``, ``()()`` và ``()(())`` là các dãy ngoặc đúng; còn ``)(`` hay ``(()`` thì không.\r\n\r\nBạ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:\r\n- Thay đổi kí tự thứ $p_i$ của $s$ (từ ``(`` sang ``)`` hoặc ngược lại).\r\n- 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.\r\n- In ra vị trí $a_i$ vừa tìm được và thay đổi kí tự ở vị trí này.\r\n\r\nChú ý 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.\r\n\r\nInput
\r\n\r\n- 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.\r\n\r\n- Dòng thứ hai chứa xâu kí tự $s$ là một dãy ngoặc đúng độ dài $n$.\r\n\r\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.\r\n\r\nOutput
\r\n\r\n- 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.\r\n\r\nScoring
\r\n\r\nBộ test của bài được chia làm các subtask như sau:\r\n- Subtask $1$ ($14.4$ điểm): $n \\leq 500$ và $q \\leq 300$\r\n- Subtask $2$ ($15.6$ điểm): $n \\leq 7000$ và $q \\leq 4200$\r\n- Subtask $3$ ($14.4$ điểm): $n \\leq 200000$ và $q \\leq 120000$\r\n- Subtask $4$ ($15.6$ điểm): $n \\leq 1000000$ và $q \\leq 600000$\r\n\r\nĐiểm tối đa của bài là $60$ điểm.\r\n\r\nExample
\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 6 3\r\n ((()))\r\n 4 3 1\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 2 2 1\r\n ```\r\n \r\n ??? warning \"Note\"\r\n Trong ví dụ trên, ban đầu dãy ngoặc $s$ là ``((()))``. Các thao tác diễn ra như sau:\r\n - 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 ``()(())``.\r\n - 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 ``(()())``.\r\n - 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 ``(()())``.","points":60.0,"partial":true,"time_limit":1.75,"memory_limit":1048576,"short_circuit":false,"allowed_languages":[4,34,36,37,5,6,11,12,14,28,38,39,9,18,17,29,23,27,35,25,26,10,19,32,15,16,24,20,33,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}