Chỉ còn đúng một ngày nữa là đến lễ tốt nghiệp. Ba người bạn thân là Youtuber_TWK, TheLegendOfSpirit và Nhan456 đang cùng nhau dọn dẹp lại phòng tin trước khi ra trường.

Trong lúc lục lại đống tài liệu cũ, cả ba phát hiện một cuốn sổ bí ẩn do các anh chị khóa trước để lại. Bên trong ghi một dãy số nguyên: \(a₁, a₂, ..., aₙ\)

Kèm theo đó là lời nhắn:

"Ai giải được bí mật của cuốn sổ này sẽ nhận được món quà tốt nghiệp đặc biệt."

Tò mò, cả ba bắt đầu nghiên cứu. Họ nhận ra cuốn sổ liên tục thay đổi dữ liệu và đưa ra các yêu cầu kiểm tra. Mỗi yêu cầu thuộc một trong hai loại:

• Loại 1: 1 i x

Một thông tin trong cuốn sổ bị cập nhật. Giá trị tại vị trí \(i\) được thay bằng \(x\).

• Loại 2: 2 l r

Cuốn sổ yêu cầu tìm mức tăng lớn nhất giữa hai vị trí trong đoạn từ \(l\) đến \(r\).

Cụ thể, cần tìm giá trị lớn nhất của: \(a[j] - a[i]\) với \(l ≤ i < j ≤ r\)

Nếu \(r−l+1<2\), in \(-1\).
Kết quả có thể âm nếu tất cả các cặp \(i<j\) trong đoạn đều cho giá trị \(a[j]−a[i]≤0\).

Vì thời gian đến lễ tốt nghiệp không còn nhiều, Youtuber_TWK, TheLegendOfSpirit và Nhan456 quyết định nhờ bạn giải giúp toàn bộ các truy vấn để khám phá bí mật cuối cùng của cuốn sổ.

Input

• Dòng đầu gồm hai số nguyên \(N,Q\). \((1≤N,Q≤5×10^5)\)
• Dòng thứ hai gồm \(N\) số nguyên \(a_i\). \((−10^9≤a_i​,x≤10^9)\)
• \(Q\) dòng tiếp theo mô tả các truy vấn.

Output

• Với mỗi truy vấn loại 2, in ra đáp án trên một dòng.

Example

5 4
1 5 2 8 4
2 1 5
1 3 10
2 1 5
2 2 4

7
9
5

6 6
9 7 5 3 1 0
2 1 6
1 6 100
2 1 6
2 4 6
2 5 5
2 2 3

-1
99
99
-1
-2