Bé An quyết định tự viết IDE cho mình. Và một trong những chức năng rất quan trọng là các cặp dấu ngoặc.

Ở giai đoạn đầu, IDE chỉ nên hỗ trợ một thao tác - thay đổi ký tự ở vị trí ~i~. Tuy nhiên, IDE không cho phép văn bản dài hơn ~n~ ký tự. Mỗi lần nếu có ký tự mới là một dấu ngoặc mở hoặc dấu ngoặc đóng, IDE phải làm nổi bật dấu ngoặc tương ứng đóng hoặc mở tương ứng.

Chúng ta hãy định nghĩa khái niệm dấu ngoặc mở. Giả sử dấu ngoặc mở ở vị trí ~i~ trong văn bản. Thì dấu ngoặc đóng ứng với nó là dấu ngoặc đóng tại vị trí ~j~, thỏa mãn:

• ~i~ < ~j~;
• nếu lấy đoạn văn bản từ vị trí ~i~ đến vị trí ~j~ và loại bỏ tất cả các ký hiệu không phải là dấu ngoặc, chúng ta sẽ thu được một dãy ngoặc đúng
• ~j~ có giá trị bé nhất có thể.

Định nghĩa tương tự cho dấu ngoặc đóng.

Hãy giúp An xác định các ngoặc tương ứng của nhau.

Input

Dòng đầu tiên ghi số nguyên ~n~ ~(1 \leq n \leq 100000)~ - độ dài tối đa của văn bản, và ~m~ ~(1 \leq m \leq 100000)~ - số lần thao tác sửa đổi ký hiệu.

Mỗi dòng trong ~m~ dòng tiếp theo mô tả một thao tác sửa đổi có dạng ~i~ ~c~: thay đổi ký tự ở vị trí ~i~ bằng ký tự ~c~ ~(1 \leq i~ ~\leq n~, ~c~ là chữ thường trong bảng chữ cái Latinh hoặc dấu ngoặc đơn). Ban đầu, văn bản có ~n~ chữ cái Latin a.

Output

Đối với mỗi thao tác thay đổi ký tự bằng dấu ngoặc đơn, in ra trên một dòng vị trí của dấu ngoặc đơn tương ứng với nó. Nếu không tồn tại, in ~-1~.

Sample Input

3 4
1 (
3)
2)
3)

Sample Output

-1
1
1
-1