Dynamic Range Minimum Queries

Source: CSES

Version: Phuoc Hung OJ Extended

Problem Statement

You are given an array of $n$ integers and $q$ operations. Each operation either assigns a new value to one position or asks for the minimum value on a contiguous range.

Input

• The first line contains two integers $n$ and $q$.
• The second line contains $n$ integers $x_1,x_2,\ldots,x_n$.
• Each of the next $q$ lines is either 1 k u, which sets $x_k=u$, or 2 a b, which asks for the minimum among $x_a,x_{a+1},\ldots,x_b$.

Output

For every operation of type 2, print the requested minimum value on its own line.

Subtasks

• Subtask 1 — 20%: $1 \le n,q \le 1000$, $1 \le x_i,u \le 10^6$.
• Subtask 2 — 30%: $1 \le n,q \le 50000$, $1 \le x_i,u \le 10^9$.
• Subtask 3 — 50%: $1 \le n,q \le 2\cdot10^5$, $1 \le x_i,u \le 10^9$.

Examples

Input

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

Output

2
1
3

Explanation

Initially, the minimum on $[1,4]$ is $2$, and on $[5,6]$ it is $1$. After 1 2 3, the range $[1,4]$ becomes $3,3,4,5$, so its minimum is $3$.