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