Segment Tree 1

Problem Description

You are given $n$ numbers $a_1, a_2, a_3, \dots, a_n$.

You must support $q$ operations:

1. 1 x d: set $a_x = d$.
2. 2 l r: query $\min_{i=l}^{r} a_i$, and find how many times this minimum occurs.

Input Format

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \times 10^5$).

The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

The following $q$ lines each describe an operation of the form 1 x d or 2 l r, with $1 \le x \le n$, $1 \le l \le r \le n$, and $1 \le d \le 10^9$.

Output Format

For each query, output one line with two numbers: the minimum value and how many times it occurs.

Sample Input

5 5
1 2 3 4 5
2 4 5
1 5 1
2 1 5
1 2 3
2 2 4

Sample Output

4 1
1 2
3 2

Constraints

$1 \le n, q \le 2 \times 10^5$, $1 \le a_i, d \le 10^9$, $1 \le x \le n$, $1 \le l \le r \le n$.