Pizzeria Queries

Source: CSES

Version: Phuoc Hung OJ Extended

There are $N$ buildings on a street, numbered $1$ through $N$. Building $i$ has a pizzeria with base price $p_i$. If you are in building $b$ and order from building $a$, the total price is:

Process two query types:

• 1 k x: set the pizza price at building $k$ to $x$.
• 2 k: while at building $k$, find the minimum total price.

Input

The first line contains $N,Q$.

The second line contains $p_1,\ldots,p_N$.

The next $Q$ lines describe the queries.

Output

For every type 2 query, print the minimum price.

Subtasks

• 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$.

Examples

Input

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

Output

5
4

Explanation

The sample follows the operations exactly; each printed line corresponds to a query that requires output.