Một hệ thống gồm ~N~ cảm biến được xếp thành hàng, đánh số từ ~1~ đến ~N~. Cảm biến thứ ~i~ có tần số hiệu chỉnh là số nguyên dương ~A_i~. Mức đồng bộ của một nhóm cảm biến được tính bằng ước chung lớn nhất của các tần số trong nhóm.

Yêu cầu: Xử lý ~Q~ thao tác thuộc một trong hai loại:

• Loại 1 — 1 ~L~ ~R~ ~X~: tăng tần số của mọi cảm biến ~A_i~ (~L \le i \le R~) thêm ~X~;

• Loại 2 — 2 ~L~ ~R~: Xét các cảm biến ở các vị trí ~L, L+1, \dots, R~; được phép loại không quá một cảm biến. Hãy tính mức đồng bộ lớn nhất có thể của các cảm biến còn lại.

Truy vấn có ~L=R~ luôn có đáp án ~A_L~ (không loại bỏ cảm biến nào).

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N, Q~ (~1 \le N, Q \le 2 \cdot 10^5~);

• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ (~1 \le A_i \le 10^9~);

• Mỗi dòng trong ~Q~ dòng tiếp theo có một trong hai dạng:

  • 1 ~L~ ~R~ ~X~, với ~1 \le L \le R \le N~ và ~1 \le X \le 10^9~;

  • 2 ~L~ ~R~, với ~1 \le L \le R \le N~.

Output

Với mỗi thao tác loại ~2~, in ra trên một dòng đáp án tương ứng.

Scoring

Sample Input 1

3 3
6 10 15
2 1 3
1 2 3 2
2 1 3

Sample Output 1

5
6

Notes

• Thao tác ~1~: loại bỏ cảm biến đầu tiên có giá trị ~6~, kết quả là ước chung lớn nhất của ~10~ và ~15~ là ~5~.

• Thao tác ~2~: sau phép cộng, dãy là ~[6, 12, 17]~.

• Thao tác ~3~: loại bỏ cảm biến cuối cùng có giá trị ~17~, kết quả là ước chung lớn nhất của ~6~ và ~12~ là ~6~.