Có \(n\) tòa nhà trên một con phố, được đánh số từ \(1, 2, \dots, n\). Mỗi tòa nhà có một cửa hàng pizza và một căn hộ. Giá pizza ở tòa nhà \(k\) là \(p_k\). Nếu bạn đặt pizza từ tòa nhà \(a\) đến tòa nhà \(b\), giá của nó (bao gồm cả phí giao hàng) là \(p_a + |a - b|\). Nhiệm vụ của bạn là xử lý hai loại truy vấn:

1. Giá pizza \(p_k\) ở tòa nhà \(k\) trở thành \(x\).
2. Bạn đang ở tòa nhà \(k\) và muốn đặt pizza. Giá tối thiểu là bao nhiêu?

Định dạng nhập

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\): số lượng tòa nhà và số lượng truy vấn.

Dòng thứ hai chứa \(n\) số nguyên \(p_1, p_2, \dots, p_n\): giá pizza ban đầu ở mỗi tòa nhà.

Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi dòng là "1 k x" hoặc "2 k".

Định dạng xuất

In ra câu trả lời cho mỗi truy vấn loại \(2\).

Ràng buộc

\(1 \le n, q \le 2 \cdot 10^5\)

\(1 \le p_i, x \le 10^9\)

\(1 \le k \le n\)

Ví dụ:

Input

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

Output

5
4

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House