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

6 3
((()))
4 3 1

2 2 1