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

• Loại ~1~: ~1 \; x \; y~: gán giá trị của ~A_x = y~.
• Loại ~2~: ~2 \; l \; r~ ~(l \leq 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 \leq 10^5)~.
• Dòng thứ ~2~ chứa ~n~ số nguyên dương ~A_1, A_2, …, 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, …, A_n~ và ~m~ truy vấn. Có 2 loại truy vấn:

• Loại ~1~: ~1 \; l \; r \; x~: tăng đoạn ~A_l, A_{l + 1}, ..., A_r~ lên ~x~ đơn vị.
• Loại ~2~: ~2 \; l \; r~ ~(l \leq 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 \leq 10^5)~.
• Dòng thứ ~2~ chứa ~n~ số nguyên dương ~A_1, A_2, …, 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, …, A_n~ và ~m~ truy vấn. Có 3 loại truy vấn:

• Loại ~1~: ~+ \; l \; r \; x~: cộng các số trong đoạn ~A_l, A_{l + 1}, ..., A_r~ với ~x~.
• Loại ~2~: ~* \; l \; r \; x~: 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 \leq 10^5)~.
• Dòng thứ ~2~ chứa ~n~ số nguyên dương ~A_1, A_2, …, 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 \leq 1000~.
• Sub ~2~: ~n, m \leq 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, …, 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 \leq 10^5)~.
• Dòng thứ ~2~ chứa ~n~ số nguyên dương ~A_1, A_2, …, 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 \leq 1000~.
• Sub ~2~: ~n, m \leq 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~: ~1 \; l \; r \; a \; b~: cộng thêm vào phần tử thứ ~i~ thêm ~(i - L)a + b~ đơn vị với mọi ~L \leq i \leq R~.
• Loại ~2~: ~2 \; l \; r~ ~(l \leq 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 \leq 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 \leq 1000~.
• Sub ~2~: ~n, m \leq 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