{"code":"ide","name":"Người soạn thảo văn bản (DHBB 2021 T.Thử)","description":"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.\r\nỞ 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\r\ndà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\r\nngoặc tương ứng đóng hoặc mở tương ứng.\r\n\r\nChú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\r\nứng với nó là dấu ngoặc đóng tại vị trí $j$, thỏa mãn:\r\n- $i < j$ ;\r\n- 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ẽ\r\nthu được một dãy ngoặc đúng\r\n- $j$ có giá trị bé nhất có thể.\r\n\r\nĐịnh nghĩa tương tự cho dấu ngoặc đóng.\r\n\r\nHãy giúp An xác định các ngoặc tương ứng của nhau.\r\n\r\n

Input

\r\n\r\n- Dòng đầu tiên ghi số nguyên $n\\ (1 \\le n \\le 100000)$ - độ dài tối đa của văn bản, và $m$ ($1 \\le m \\le 100000$) - số lần thao\r\ntác sửa đổi ký hiệu.\r\n- 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 \\le i \\le 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$\".\r\n\r\n

Output

\r\n\r\n- Đố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\r\nnó. Nếu không tồn tại, in -1. \r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 3 4\r\n 1 (\r\n 3)\r\n 2)\r\n 3)\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n -1\r\n 1\r\n 1\r\n -1\r\n ```","points":500.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}