Peter and the Textbook

Peter was cleaning his room today and found his old English literature textbook. He does not like the subject, so he decided to take the book apart and started tearing out the pages one at a time.

The textbook has $n$ pages, numbered from 1 to $n$. Because of the way the book is bound, page $i$ is printed on the same sheet as page $n - i + 1$. When Peter tears out one page, the other page on the same sheet comes away with it. Between tears Peter sometimes wants to know this: if the pages still left in the book are listed in increasing order of page number, what is the number of the $p$-th one? Answer his questions.

The input contains several test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$).

Each of the $t$ test cases is given in the following format. The first line of a test case contains two integers $n$ and $q$ ($2 \le n \le 100$, $n$ is even, $1 \le q \le 100$), the number of pages in the textbook and the number of queries. Each of the next $q$ lines contains one query.

• - i: Peter tears out page $i$, and the page on the same sheet comes away with it.
• ? p: Peter asks for the number of the $p$-th page among those still remaining.

For a tear query the page is still in the textbook, and for a page number query the textbook still holds at least $p$ pages.

For each ? query, print the number of the requested page on its own line.