Truy vấn max (Trại hè MB 2019)

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 đánh số từ \(1\) tới \(n\). Lương khởi điể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 lương cho nhân viên \(i\) là \(k\) (\(1 \le i \le n\); \(0 \le k \le 10^9\)).
• 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\) (\(1 \le i \le j \le 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 đầu tiên chứa hai số nguyên dương \(n, m\) (\(n, m \le 10^5\)).
• \(m\) dòng tiếp theo, mỗi dòng chứa thông tin về một lệnh, bắt đầu bằng một ký tự thuộc \(\{S, Q\}\):
• Nếu ký tự đầu dòng là S, tiếp theo là hai số nguyên \(i, k\) cho biết lệnh đó là \(S(i, k)\).
• Nếu ký tự đầu dòng là Q, tiếp theo là hai số nguyên \(i, j\) cho biết lệnh đó là \(Q(i, j)\).

Output

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

Sample Input 1

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

Sample Output 1

5
7