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à \(v\) (\(1 \leq i \leq N\), \(1 \leq v \leq 10^{9}\)). Nếu \(t = 2\), hai số tiếp theo sẽ là \(l\) và \(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

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 

5    
6    
4
5