Cho dãy số $A_1,A_2,\dots ,A_n$ và $m$ truy vấn. Có 2 loại truy vấn:

• Loại $1$: $1xy$: gán giá trị của $A_x=y$.
• Loại $2$: $2lr$ $(l\le r)$: yêu cầu tìm giá trị nhỏ nhất trong đoạn $[l,r]$.

Input

• Dòng đầu chứa số $2$ nguyên $n,m$ $(n,m\le {10}^5)$.
• Dòng thứ $2$ chứa $n$ số nguyên dương $A_1,A_2,\dots ,A_n$.
• $m$ dòng tiếp theo chứa $m$ truy vấn thuộc một trong hai loại trên.

Tất cả các số đều dương và nhỏ hơn ${10}^9$.

Output

• Kết quả của các truy vấn loại $2$ theo thứ tự.

Sample Input 1:

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

Sample Output 1:

2
1
7

Cho dãy số $A_1,A_2,\dots ,A_n$ và $m$ truy vấn. Có 2 loại truy vấn:

• Loại $1$: $1lrx$: tăng đoạn $A_l,A_{l+1},...,A_r$ lên $x$ đơn vị.
• Loại $2$: $2lr$ $(l\le r)$: yêu cầu tìm giá trị nhỏ nhất trong đoạn $[l,r]$.

Input

• Dòng đầu chứa số $2$ nguyên $n,m$ $(n,m\le {10}^5)$.
• Dòng thứ $2$ chứa $n$ số nguyên dương $A_1,A_2,\dots ,A_n$.
• $m$ dòng tiếp theo chứa $m$ truy vấn thuộc một trong hai loại trên.

Tất cả các số đều dương và nhỏ hơn ${10}^9$.

Output

• Kết quả của các truy vấn loại $2$ theo thứ tự.

Sample Input 1:

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

Sample Output 1:

6
4
7

Cho dãy số $A_1,A_2,\dots ,A_n$ và $m$ truy vấn. Có 3 loại truy vấn:

• Loại $1$: $+lrx$: cộng các số trong đoạn $A_l,A_{l+1},...,A_r$ với $x$.
• Loại $2$: $\ast lrx$: nhân các số trong đoạn $A_l,A_{l+1},...,A_r$ với $x$.
• Loại $3$: $?p$: đưa ra giá trị của $A_p$ mod ${10}^9+7$.

Input

• Dòng đầu chứa số $2$ nguyên $n,m$ $(n,m\le {10}^5)$.
• Dòng thứ $2$ chứa $n$ số nguyên dương $A_1,A_2,\dots ,A_n$.
• $m$ dòng tiếp theo chứa $m$ truy vấn thuộc một trong ba loại trên.

Tất cả các số đều dương và nhỏ hơn ${10}^9$.

Output

• Kết quả của các truy vấn loại $3$ theo thứ tự.

Subtask

• Sub $1$: $n,m\le 1000$.
• Sub $2$: $n,m\le 100000$.

Sample Input 1:

4 5
1 3 0 7
+ 3 3 9
? 3
* 2 4 6
+ 1 4 9
? 4

Sample Output 1:

9
51

Cho dãy số $A_1,A_2,\dots ,A_n$ và số nguyên dương $k$. Hãy tìm dãy con dài nhất của $A$ (không nhất thiết phải liên tiếp) sao cho chênh lệch giữa $2$ phần tử liên tiếp trong dãy con không ít hơn $k$.

Input

• Dòng đầu chứa số $2$ nguyên $n,k$ $(n\le {10}^5)$.
• Dòng thứ $2$ chứa $n$ số nguyên dương $A_1,A_2,\dots ,A_n$.

Tất cả các số đều dương và nhỏ hơn ${10}^9$.

Output

• Độ dài của dãy con dài nhất thỏa mãn yêu cầu đề bài.

Subtask

• Sub $1$: $n,m\le 1000$.
• Sub $2$: $n,m\le 100000$.

Sample Input 1:

6 15
1014 1024 1034 1045 1030 998

Sample Output 1:

4

Cho dãy số độ dài $n$ và $m$ truy vấn. Ban đầu tất cả các số đều bằng $0$. Có 2 loại truy vấn:

• Loại $1$: $1lrab$: cộng thêm vào phần tử thứ $i$ thêm $(i-L)a+b$ đơn vị với mọi $L\le i\le R$.
• Loại $2$: $2lr$ $(l\le r)$: yêu cầu tìm tổng của các phần tử trong khoảng $[l,r]$, lấy dư cho ${10}^9+7$.

Input

• Dòng đầu chứa số $2$ nguyên $n,m$ $(n,m\le {10}^5)$.
• $m$ dòng tiếp theo chứa $m$ truy vấn thuộc một trong hai loại trên.

Tất cả các số đều dương và nhỏ hơn ${10}^9$.

Output

• Kết quả của các truy vấn loại $2$ theo thứ tự.

Subtask

• Sub $1$: $n,m\le 1000$.
• Sub $2$: $n,m\le 100000$.

Sample Input 1:

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

Sample Output 1:

15
18