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