You are building a zoo. This zoo has a shape of N×N square and there is a ticket booth on each corner of this square: (0,0); (0,N); (N,N); (N,0).

Input file contains three types of format:

+ X Y (a house has been build on the coordinate (X, Y))

- X Y (a house has been destroyed on the coordinate (X, Y))

? X Y (here (X, Y) denotes a gate to enter the zoo)

For every gate (X, Y), your task is to find out the shortest distance to the current gate (X, Y) from the farthest house among all the houses available.

For entering the zoo at the gate (X, Y), you have to consider the following conditions:

1. While calculating the distance from the farthest house to the gate, you can't consider the path inside the zoo, because you haven't reached the gate yet!
2. You must visit at least one corner to purchase a ticket to enter the zoo.
3. A house can't be built inside the zoo.
4. Traversals from house to any corners include Euclidean distance. And Corner to Gate include row and column distance. Because you can enter the zoo only through a gate.
5. The gates will always be on the boundary of the zoo.

Input

Input starts with two positive integers N (≤ 10⁹) and P (≤ 2×10⁵). The next P lines contains either + X Y or - X Y or ? X Y. The value of X, Y have the range of -10⁹ ≤ X, Y ≤ 10⁹.

Note: The Input has given in such a way so that all the Euclidean distances are integers.

Output

For each ? X Y, print the fastest distance to the gate (X, Y) from the farthest house.

Sample

Input
10 6
+ -4 3
+ 7 14
+ 10 -3
? 4 0
- 7 14
? 8 0

Output
21
13