QUERY Truy vấn

Hệ thống quản lý nhân sự của công ty X cần quản lý thông tin về lương của n nhân viên dánh số từ 1 tới n. Luong khởi diểm của tất cả các nhân viên là 0 và hệ thống cần cung cấp hai lệnh:

• Lệnh cập nhật S(i, k): Ðặt luong cho nhân viên i là k (1 ≤ i ≤ n; 0 ≤ k ≤ 10⁹)
• Lệnh truy vấn Q(i, j): Cho biết lương của nhân viên hưởng lương cao nhất trong số các nhân viên từ i tới j (i ≤ i ≤ j ≤ n)

Yêu cầu: Cho một dãy m lệnh thuộc một trong hai loại trên, hãy trả lời tất cả các lệnh truy vấn

Input

• Dòng 1 chứa hai số nguyên duong n, m ≤ 10⁵.    
• m dòng tiếp theo, mỗi dòng chứa thông tin về một lệnh, dầu tiên là một ký tự thuộc {S; Q}
• Nếu ký tự dầu dòng là S, tiếp theo là hai số nguyên i, k cho biết lệnh dó là S(i, k)
• Nếu ký tự dầu dòng là  Q, tiếp theo là hai số nguyên i, j cho biết lệnh dó là Q(i, j)

Output : Tương ứng với mỗi lệnh truy vấn Q trong file dữ liệu, ghi ra trên một dòng một số nguyên là câu trả lời cho truy vấn dó.

Input	Output
5 6 S 2 1 S 4 5 Q 2 4 S 3 6 S 2 7 Q 1 4	5 7