Cho mảng \(a\) độ dài \(n\): \(a_{1}, a_{2}, \ldots, a_{n}\). Với một dãy con liên tiếp \((l, r)\) \((a_{l}, a_{l + 1}, \ldots, a_{r})\), biến đổi tối giản của nó được định nghĩa là một dãy con liên tiếp \((u, v)\) thỏa mãn:

• \(l \leq u \leq v \leq r\).
• \(min(a_{u}, a_{u + 1}, \ldots , a_{v}) = \min(a_{l}, a_{l + 1}, \ldots, a_{r})\).
• \(max(a_{u}, a_{u + 1}, \ldots , a_{v}) = \max(a_{l}, a_{l + 1}, \ldots, a_{r})\).
• Độ dài của đoạn \((u, v)\) là nhỏ nhất có thể.

Lưu ý: mỗi đoạn con có thể có nhiều biến đổi tối giản.

Bạn sẽ phải trả lời \(q\) truy vấn có dạng:

• \(1\) \(p\) \(x\): đặt \(a_{p} = x\).
• \(2\) \(l\) \(r\): cho biết độ dài và số lượng biến đổi tối giản khác nhau của đoạn \((l, r)\). 2 biến đổi tối giản \((u, v)\) và \((x, y)\) được gọi là khác nhau khi \(u \neq x\) hoặc \(v \neq y\).

Input

• Dòng đầu tiên gồm hai số nguyên \(n\) và \(q\) \((1 \leq n, q \leq 2 \times 10^{5})\).
• Dòng thứ hai gồm \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{9})\).
• \(q\) dòng tiếp theo gồm các truy vấn:
  • \(1\) \(p\) \(x\) \((1 \leq p \leq n, 1 \leq x \leq 10^{9})\) - miêu tả truy vấn loại \(1\)
  • \(2\) \(l\) \(r\) \((1 \leq l \leq r \leq n)\) - miêu tả truy vấn loại \(2\)
• Dữ liệu vào đảm bảo có ít nhất một truy vấn loại \(2\).

Output

• Với mỗi truy vấn loại \(2\), in ra kết quả của truy vấn đó trên một dòng.

Scoring

• Subtask \(1\) (\(27\%\) số điểm): \(n, q \leq 800\).
• Subtask \(2\) (\(13\%\) số điểm): \(a_{1} \leq a_{2} \leq \ldots \leq a_{n}\) và không có truy vấn loại \(1\).
• Subtask \(3\) (\(15\%\) số điểm): \(a_{1}, a_{2}, \ldots , a_{n}\) là hoán vị của \(1, 2, \ldots, n\) và không có truy vấn loại \(1\).
• Subtask \(4\) (\(19\%\) số điểm): \(q \leq 400\).
• Subtask \(5\) (\(26\%\) số điểm): Không có ràng buộc gì thêm.

Example

10 9
4 7 5 3 4 4 3 4 8 5
2 4 8
1 2 8
2 1 10
1 7 8
2 3 9
1 8 3
2 1 10
1 1 2
2 1 10

2 3
3 2
4 1
2 2
2 1