Mức Nhỏ Nhất Và Số Lần

Cho một mảng $a$ gồm $n$ phần tử, đánh số từ $0$ đến $n-1$. Bạn cần xử lý hai loại thao tác theo đúng thứ tự xuất hiện:

• $1$ $i$ $v$: thay $a_i$ bằng $v$;
• $2$ $l$ $r$: xét đoạn nửa mở $[l,r)$, tức là các vị trí $l,l+1,\dots ,r-1$. Hãy tìm giá trị nhỏ nhất trong đoạn và số vị trí mang giá trị ấy.

Input

• Dòng đầu chứa hai số nguyên $n$ và $m$ - số phần tử và số thao tác.
• Dòng thứ hai chứa $n$ số nguyên $a_0,a_1,\dots ,a_{n-1}$.
• Mỗi dòng trong $m$ dòng tiếp theo có dạng $1$ $i$ $v$ hoặc $2$ $l$ $r$.

Output

• Với mỗi thao tác loại $2$, in hai số trên một dòng: giá trị nhỏ nhất trong $[l,r)$ và số lần giá trị đó xuất hiện trong đoạn.

Constraints

• $1\le n,m\le 10^5$.
• $0\le a_i,v\le 10^9$.
• Với thao tác loại $1$: $0\le i<n$.
• Với thao tác loại $2$: $0\le l<r\le n$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,m\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

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

1 2
1 1
1 2