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.

Subtasks

Bộ test của bài được chia làm các subtask như sau:

• Subtask ~1~ (~12~ test): ~n \leq 500~ và ~q \leq 300~
• Subtask ~2~ (~13~ test): ~n \leq 7000~ và ~q \leq 4200~
• Subtask ~3~ (~12~ test): ~n \leq 200000~ và ~q \leq 120000~
• Subtask ~4~ (~13~ test): ~n \leq 1000000~ và ~q \leq 600000~

Điểm tối đa của bài là ~60~ điểm.

Ví dụ

Input

6 3
((()))
4 3 1

Output

2 2 1

Giải thích

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 (()()).