Giải bài trực tuyến

Tiếp tục hành trình khám phá sức mạnh của các cấu trúc dữ liệu đặc biệt, hai nhà thám hiểm pirate và duyhung123abc lại lao vào những thử thách với những bài toán hóc búa mới. Nhưng những gì họ thu thập được chẳng là bao. Chán chường và bế tắc, họ quyết định lật giở những bài toán đã giải để xem lại những thành quả đã đạt được. Đột nhiên, một thứ ánh sáng lạ kì lóe lên trong đầu họ: "Tại sao không kết hợp một số bài toán lại với nhau !" . Và đây, QMAX3VN đã ra đời, tự nhiên như cái cách mà lửa đã đến với loài người.

Chuyện kể rằng vào một buổi sáng nọ trong một doanh trại quân đội, các quân nhân đang tập trung thành một hàng ngang để chuẩn bị tập thể dục buổi sáng. Nhưng vấn đề là không phải tất cả họ đều dậy cùng một lúc. Ban đầu, hàng ngang chẳng có người nào. Sau một lúc, lại có một anh chàng quân nhân hộc tốc chạy ra. Mỗi anh chàng lại thích đứng cạnh ai đó, nên cứ nhất quyết chen vào một vị trí nào đó trong hàng. Thật là một cảnh tượng hỗn độn và không thể chấp nhận. Mặt ai cũng cúi gằm xuống đất chuẩn bị chịu sự trừng phạt của viên chỉ huy. Viên chỉ huy, tuy nghiêm khắc nhưng cũng rất nhân hậu, đã đưa một trò chơi như sau để cho các anh chàng một bài học. Mỗi khi ông ta đưa ra một khẩu lệnh (x,y) thì lập tức các quân nhân phải chỉ vào người cao nhất trong các quân nhân đang đứng từ vị trí x đến vị trí y trong hàng. Khẩu lệnh sẽ được phát ra liên tục từ khi có một quân nhân bước vào hàng. Hình phạt đang chờ những người làm sai khẩu lệnh. Sân tập ướt đẫm những giọt mồ hồi lo lắng của các cậu lính trẻ. Họ đang cần sự giúp đỡ của bạn!

Input

Dữ liệu vào gồm nhiều dòng:

• Dòng thứ 1 : Một số nguyên n (1 ≤ n ≤ 100000): Số sự kiện sẽ diễn ra trong buổi tập thể dục.
• Dòng thứ 2 đến dòng thứ n+1: Mỗi dòng là một trong hai sự kiện:
  • A x y : Một quân nhân có chiều cao x vừa chen vào giữa vị trí thứ y-1 và y trong hàng (-10⁹ ≤ x ≤ 10⁹; 1 ≤ y ≤ k+1 , với k là số anh lính hiện có trong hàng).
  • Q x y : Khẩu lệnh của viên chỉ huy. Hãy tìm chiều cao của người cao nhất trong các quân nhân đang đứng từ vị trí thứ x đến vị trí thứ y trong hàng (1 ≤ x ≤ y ≤ k , với k là số anh lính hiện có trong hàng).

Output

Dữ liệu ra gồm nhiều dòng:

• Với mỗi khẩu lệnh của viên chỉ huy, ghi trên một dòng chiều cao của người mà các quân nhân cần phải chỉ vào.

Example

Input:
10
A 1 1
A 2 2
Q 1 2
A 3 1
A 4 3
Q 2 4
A 5 2
Q 2 3
A 6 3
Q 1 4

Output:
2
4
5
6