Cho dãy số gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~. Độ đẹp của một đoạn từ vị trí ~L~ đến vị trí ~R~ được tính bằng công thức:

~\displaystyle \max_{L \le u \le R}\{(a_u-a_L)(a_R-a_u)\}~

Có tất cả ~m~ truy vấn. Mỗi truy vấn thuộc một trong hai loại sau:

• ~1\ u\ x~: Gán giá trị ~a_u=x~ ~(1 \le u \le n)~;

• ~2\ L\ R~: Tính độ đẹp của đoạn từ vị trí ~L~ đến vị trí ~R~ ~(1 \le L \le R \le n)~.

Yêu cầu: Với mỗi truy vấn thuộc loại ~2~ hãy tính độ đẹp của đoạn ~[L,R]~ tương ứng.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m~ ~(1 \le n,m \le 5 \cdot 10^4)~;

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1,a_2,\dots,a_n~ ~(1 \le a_i \le 10^9, 1 \le i \le n)~;

• ~m~ dòng tiếp theo, mỗi dòng mô tả một truy vấn. Với truy vấn loại ~1\ u\ x~ thì ~1 \le u \le n, 1 \le x \le 10^9~; với truy vấn loại ~2\ L\ R~ thì ~1 \le L \le R \le n~;

• Các số trên một dòng cách nhau bởi dấu cách. Dữ liệu đảm bảo có ít nhất một truy vấn loại ~2\ L\ R~.

Output

• Với mỗi truy vấn loại ~2\ L\ R~ in một số nguyên trên một dòng là độ đẹp của đoạn ~[L,R]~ tương ứng.

Scoring

Sample Input 1

4 3
2 1 4 3
2 1 4
1 2 3
2 1 3

Sample Output 1

0
1

Notes

Dãy số ban đầu là: ~\{2,1,4,3\}~. Với truy vấn ~2\ 1\ 4~, độ đẹp của đoạn ~[1,4]~ là:

~\displaystyle \max_{1 \le u \le 4}\{(2-2)(3-2),(1-2)(3-1), (4-2)(3-4),(3-2)(3-3)\}=0~.

Với truy vấn ~1\ 2\ 3~: gán giá trị ~a_2=3~.

Dãy số trở thành: ~\{2,3,4,3\}~.

Với truy vấn ~2\ 1\ 3~, độ đẹp của đoạn ~[1,3]~ là:

~\displaystyle \max_{1 \le u \le 3}\{(2-2)(4-2),(3-2)(4-3), (4-2)(4-4)\}=1~.