피터와 교과서

피터는 오늘 방을 정리하다가 예전에 쓴 영문학 교과서를 찾았다. 이 과목을 좋아하지 않아서 교과서를 해체하기로 마음먹고, 쪽을 하나씩 뜯어내기 시작했다.

교과서는 $n$쪽이고 각 쪽에는 1번부터 $n$번까지 번호가 붙어 있다. 제본 방식 때문에 $i$번 쪽은 $n - i + 1$번 쪽과 같은 낱장에 인쇄되어 있다. 그래서 피터가 어떤 쪽을 뜯어내면 같은 낱장에 있는 다른 쪽도 함께 떨어져 나간다. 피터는 쪽을 하나씩 뜯어내다가 이따금 아직 교과서에 남아 있는 쪽을 번호가 작은 순서로 늘어놓았을 때 $p$번째 쪽의 번호가 무엇인지 알고 싶어진다. 피터의 질문에 답하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 첫째 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 1000$)가 주어진다.

이어서 $t$개의 테스트 케이스가 다음 형식으로 주어진다. 각 테스트 케이스의 첫째 줄에는 교과서의 쪽수 $n$과 질의의 수 $q$가 주어진다 ($2 \le n \le 100$, $n$은 짝수, $1 \le q \le 100$). 다음 $q$개의 줄에는 질의가 한 줄에 하나씩 주어진다.

• - i: 피터가 $i$번 쪽을 뜯어낸다. 같은 낱장에 있는 쪽도 함께 떨어져 나간다.
• ? p: 남아 있는 쪽 중 $p$번째 쪽의 번호를 묻는다.

뜯어내는 질의에서 그 쪽은 아직 교과서에 남아 있고, 번호를 묻는 질의에서 교과서에는 쪽이 $p$개 이상 남아 있다.

? 질의마다 해당하는 쪽 번호를 한 줄에 하나씩 출력한다.