Quỳnh đang nghiên cứu một số đề tài về tin học, Quỳnh nghiên cứu giá trị tuyệt đối của một dãy ~X~ đó là chênh lệch giữa phần tử lớn nhất và phần tử nhỏ nhất của dãy ~X~.

Ví dụ ta có dãy ~X = [1, 6, 9, 3, -1, 7]~, giá trị tuyệt đối của dãy ~X~ này là ~|9 - (-1)| = 10~.

Vào một ngày đẹp trời, Quỳnh mời bạn tới phòng nghiên cứu, cô ấy cho bạn một dãy ~N~ số nguyên ~A_1, A_2, \cdots , A_N~. Cô ấy nhờ bạn viết 1 chương trình máy tính thực hiện ~Q~ phép toán trên dãy trên để có thể dữ liệu về nghiên cứu của mình, ~Q~ phép toán này có 2 loại:

• ~1 \ u \ v~: Phép toán này sẽ gán giá trị ~A_u = v~ ~(1 \leq u \leq N, -10^9 \leq v \leq 10^9)~.
• ~2 \ u \ v~: Phép toán này sẽ tính giá trị tuyệt đối của dãy ~A_u, A_{u + 1}, \cdots , A_v~ ~(1 \leq u \leq v \leq N)~.

Bạn hãy giúp Quỳnh viết chương trình thực hiện ~Q~ phép toán trên.

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~N, Q~ được phân tách nhau bởi dấu cách ~(1 \leq N, Q \leq 2 \times 10^5)~.
• Dòng tiếp theo gồm ~N~ số nguyên của dãy ~A_1, A_2, \cdots , A_N~ ~(-10^9 \leq A_i \leq 10^9)~.
• ~Q~ dòng tiếp theo, mỗi dòng thể hiện 1 trong 2 phép toán nêu trên.

Output

• Gồm nhiều dòng, mỗi dòng trả lời các phép toán loại ~2 \ u \ v~.

Sample

Input #1

8 5
3 2 4 5 1 1 5 3
2 1 4
2 2 7
1 5 7
1 6 0
2 2 7

Output #1

3
4
7