FINDMAX1

View as PDF

Points: 100 (p) Time limit: 2.0s Memory limit: 1G Input: stdin Output: stdout

Cho một dãy \(a\) gồm \(N\) số nguyên, được đánh số từ 1 đến \(N\), số thứ \(i\) có giá trị là \(a_i\) ban đầu tất cả các số đều có giá trị bằng 0. Ta có \(Q\) thao tác. Có hai loại thao tác

  • Loại 1: Gồm hai số \(i\), \(v\): gán \(a_i = v\)
  • Loại 2: Gồm hai số \(l\), \(r\): trả về số có giá trị lớn nhất trong đoạn từ \(l\) đến \(r\).

Input

  • Dòng đầu tiền gồm 2 hai số nguyên dương \(N\), \(Q\) (\(N, Q \leq 2000\))
  • Dòng thứ hai gồm \(N\) số, là giá trị ban đầu của dãy \(a\)
  • \(Q\) dòng tiếp theo mỗi dòng là gồm 3 số, số đầu tiên là \(t\) (\(1 \leq t \leq 2\)), là loại thao tác của thao tác hiện tại. Nếu \(t = 1\), hai số tiếp theo sẽ là \(i\)\(v\) (\(1 \leq i \leq N\), \(1 \leq v \leq 10^{9}\)). Nếu \(t = 2\), hai số tiếp theo sẽ là \(l\)\(r\) \((1 \leq l \leq r \leq n)\).

Output

  • Dòng nhiều dòng là đáp án cho các thao tác loại 2, mỗi số in trên một dòng.

Example

Test 1

Input
5 6
1 2 3 4 5
2 1 5
1 1 6
2 1 5
2 2 4
1 2 5
2 2 4 
Output
5    
6    
4
5

Comments