Trong một dự án phát triển ứng dụng chỉnh sửa ảnh, bạn được giao nhiệm vụ thiết kế tính năng "Tạo khung ảnh nghệ thuật". Để tạo thành một khung ảnh hình chữ nhật hoàn chỉnh, hệ thống cần chọn ra đúng ~4~ thanh nẹp từ kho dữ liệu có sẵn. Hiện tại, kho dữ liệu đang có ~n~ thanh nẹp với độ dài lần lượt là ~a_1, a_2, \dots, a_n~. Bạn muốn chọn được ~4~ thanh nẹp sao cho tạo được khung ảnh có chu vi lớn nhất.

Ban đầu bạn có danh sách các thanh. Sau đó có ~Q~ thao tác, mỗi thao tác thuộc một trong hai loại:

• Loại ~1~: Cập nhật độ dài của một thanh.

• Loại ~2~: Hỏi chu vi lớn nhất có thể tạo được từ ~4~ thanh hiện tại.

Input

• Dòng đầu ghi số nguyên dương ~n~, ~Q~ ~(1 \le n, Q \le 2 \times 10^5)~.

• Dòng thứ hai ghi ~n~ số nguyên dương ~a_i~ ~(1 \le i \le n)~.

• ~Q~ dòng tiếp theo, mỗi dòng là một thao tác:

  • ~1~ ~i~ ~x~: Thao tác gán ~a[i] = x~.

  • ~2~: In ra kết quả hiện tại.

Các giá trị thỏa mãn ~1 \le a_i, x \le 10^9~.

Output

Với mỗi truy vấn loại ~2~, in ra một số nguyên là chu vi lớn nhất của khung ảnh có thể ghép được.

Nếu không thể tạo hình chữ nhật, in ra ~0~.

Scoring

Sample Input 1

8 3
4 2 5 7 4 5 2 5
2
1 4 5
2

Sample Output 1

18
20

Notes

• Ban đầu: có các cặp ~(5, 5)~, ~(4, 4)~, ~(2, 2)~, chọn ~5~ và ~4~, chu vi ~= 18~.

• Sau cập nhật: dãy thành ~4, 2, 5, 5, 4, 5, 2, 5~, có ~(5, 5, 5, 5)~, chọn ~5~ và ~5~, chu vi ~= 20~.