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 < i < n; 0 < k < 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

• Vào từ file văn bản QUERY.INP

• Dòng 1 chứa hai số nguyên dương \(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, đầu tiên là một ký tự \(\in\) {\(S\), \(Q\)}:
  • Nếu ký tự đầu dòng là \(S\), tiếp theo là hai số nguyên \(j, 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

• Ghi ra file văn bản QUERY.OUT

• 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 đó.

Example

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

5
7