Truy vấn cửa hàng pizza (Pizzeria Queries)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Có $N$ tòa nhà trên một con phố, đánh số từ $1$ đến $N$. Tòa nhà $i$ có một tiệm pizza với giá cơ bản $p_i$. Nếu đang ở tòa nhà $b$ và đặt pizza từ tòa nhà $a$, tổng giá phải trả là:

Có hai loại truy vấn:

• 1 k x: giá pizza ở tòa nhà $k$ trở thành $x$.
• 2 k: đang ở tòa nhà $k$, hãy tìm giá nhỏ nhất có thể phải trả.

Input

Dòng đầu chứa $N,Q$.

Dòng thứ hai chứa $p_1,\ldots,p_N$.

$Q$ dòng tiếp theo mô tả truy vấn.

Output

Với mỗi truy vấn loại 2, in giá nhỏ nhất.

Subtask

• Subtask 1 — 20%: $1\le N,Q\le 50$, $1\le p_i,x\le 10^4$.
• Subtask 2 — 30%: $1\le N,Q\le 5000$, $1\le p_i,x\le 10^9$.
• Subtask 3 — 50%: $1\le N,Q\le 2\cdot10^5$, $1\le p_i,x\le 10^9$.

Ví dụ

Input

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

Output

5
4

Giải thích

Ở tòa nhà $2$, đặt từ tòa nhà $3$ có giá $4+1=5$. Sau khi giá ở tòa nhà $5$ thành $1$, phương án tốt nhất từ tòa nhà $2$ có tổng giá $4$.