Có \(n\) tòa nhà trên một con đường, được đánh số \(1,2,..,n\). Mỗi tòa nhà có một tiệm bánh pizza và một căn hộ.

Giá pizza trong tòa nhà thứ \(k\) là \(p_k\). Nếu bạn gọi một bánh pizza từ tòa nhà \(a\) đến \(b\), giá của nó (với giao hàng) là \(p_a + |a - b|\).

Nhiệm vụ của bạn là xử lí 2 dạng truy vấn sau:

1. Giá pizza \(p_k\) của tòa nhà thứ \(k\) đổi thành \(x\).
2. Bạn đang ở tòa nhà thứ \(k\) và muốn gọi một bánh pizza. Giá tối thiểu để gọi là gì?

Input

• Dòng đầu tiên gồm hai số nguyên \(n\) và \(q\): số tòa nhà và số truy vấn.
• Dòng thứ hai gồm \(n\) số nguyên \(p_1, p_2,...,p_n\): giá pizza ban đầu của mỗi tòa nhà.
• Cuối cùng, có \(q\) dòng truy vấn. Mỗi dòng sẽ là 1 k x hoặc 2 k.

Constraints

• \(1 \leq n,q \leq 2\cdot 10^5\)
• \(1 \leq p_i,x \leq 10^9\)
• \(1 \leq k \leq n\)

Output

• In các đáp án của các truy vấn loại 2.

Example

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

5
4