Cho 1 dãy S ban đầu không có phần tử nào. Máy tính sẽ đưa ra n lệnh có dạng sau :

  -  I x y : Chèn số x vào tập s giữa 2 vị trí y-1 và y (-10^9<=x<=10^9)

     Quy định : Với k là số phần tử trong tập S , y = 1 thì x được chèn vào đầu dãy, y = k+1 thì x được chèn vào cuối dãy.

  -  S x y : Đổi chố vị trí 2 phần tử thứ x và y (1<= x,y <= k)

  -  D x : Xóa phần tử thứ x ra khỏi dãy S (1<=x<=k)

  -  Q x y : Tìm giá trị lớn nhất từ vị trí x đến vị trí y.(1<=x<=y<=k)

Yêu cầu : Cho n lệnh. Hãy trả lời mỗi truy vấn

Input

- Dòng đầu là số n (n <= 10^5)

- N dòng tiếp theo là các lệnh có mẫu như trên

Output

Gồm một số dòng , mỗi dòng trả lời cho 1 truy vấn theo thứ tự từ trên xuống

Example

Input:
7
I 1 1
I 5 2
I 2 3
S 1 2
Q 1 2
D 1
Q 1 1

Output:
5
1