Given an empty set S, you have to apply Q operations on this set while keeping the set sorted in increasing order and elements have indices 0 <= i < size(S)

The operations are insert, delete, find min difference in a given range, find max difference in a given range.

Input

I k : Insert k into S, if k is not in S

D k : Delete k from S, if k is in S

N i j : Print min{abs(S[x] - S[y]) | i <= x, y <= j} or -1 if the range has 1 element

X i j : Print max{abs(S[x] - S[y]) | i <= x, y <= j} or -1 if the range has 1 element

limits: 0 < Q <= 200000 , 0 <= k <= 10^9 , 0 <= i,j < size(S)

Output

For each N and X operations, print an integer per line as described above.

Example

Input:
11
I 1
I 12
I 4
I 8
N 0 3
X 0 3
N 1 3
X 0 2
D 4
N 0 1
X 1 2

Output:
3
11
4
7
7
4