Text Editor

Little Ivan recently decided to write his own text editor. He plans to use this editor to write complex programs, so a feature that highlights matching brackets is very important to him.

At this early stage, the text editor needs to support only one operation: changing the character at position i. The editor does not allow the text to be longer than n characters. Whenever the new character is an opening or closing parenthesis, the editor must highlight the parenthesis matching it, if such a parenthesis exists.

Let us define a matching parenthesis. Suppose the character at position i of the text is an opening parenthesis. Then the parenthesis matching it is the closing parenthesis at position j satisfying the following:

• i < j;
• if we take the text from position i through position j inclusive and delete every character that is not a parenthesis, the result is a correct bracket sequence;
• j is minimal.

The matching parenthesis of a closing parenthesis is defined in the same way.

Unfortunately, Ivan could not implement the feature he wanted. Your task is, for the given operations, to find the matching parenthesis for each operation that changes a character to a parenthesis.

The first line contains the integers n (1 ≤ n ≤ 100000), the maximum length of the text, and m (1 ≤ m ≤ 100000), the number of character modification operations.

The next m lines describe the character modification operations, each given as an integer i, the position whose character is changed, and the new character c (1 ≤ i ≤ n; c is a lowercase Latin letter, an opening parenthesis, or a closing parenthesis).

Initially the text consists of n lowercase Latin letters “a”.

For each operation that changes a character to a parenthesis, output the position of its matching parenthesis on a separate line. If no matching parenthesis exists, output -1 on that line.