~n~ người đang đứng ở các vị trí từ ~1~ đến ~n~. Bạn cần thực hiện các truy vấn thuộc hai loại sau:

• "- x" — người ở vị trí ~x~ rời đi;

• "? x" — tìm người gần nhất đứng bên phải vẫn còn đứng.

Input

Dòng đầu tiên của đầu vào chứa hai số nguyên ~n~ và ~m~ (~1 \leq n, m \leq 10^6~) — số người và số truy vấn.

Tiếp theo là ~m~ dòng chứa các truy vấn, mỗi dòng một truy vấn. Với các truy vấn về việc rời đi, dòng truy vấn có dạng "- x" (~1 \leq x \leq n~). Với các truy vấn về người gần nhất, dòng truy vấn có dạng "? x" (~1 \leq x \leq n~).

Dữ liệu đảm bảo rằng tất cả những người rời đi đều khác nhau.

Output

In ra kết quả của mỗi thao tác "?" theo từng dòng theo thứ tự tương ứng. Nếu không có người nào bên phải — in ra "-1".

Scoring

Sample Input 1

5 10
? 1
- 3
? 3
- 2
? 1
? 2
- 4
? 3
- 5
? 3

Sample Output 1

1
4
1
4
5
-1