Cho mảng ~a~ gồm ~n~ phần tử, ban đầu có giá trị bằng ~1~. Thực hiện hai loại truy vấn:

• ~1~ ~l~ ~r~ ~x~: tăng đoạn ~[l, r]~ lên ~x~ đơn vị (~1 \le l \le r \le n~, ~1 \le x \le 10^9~).

• ~2~ ~l~ ~r~: tìm ~\gcd (a_l, a_{l + 1}, ..., a_r)~ (~1 \le l \le r \le n~).

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~ (~1 \le n, q \le 2 \times 10^5~), thể hiện số phần tử của mảng ~a~ và số truy vấn.

~q~ dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong hai loại trên.

Output

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

Sample Input 1

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

Sample Output 1

1
3
6

Notes

• Ban đầu, ~a = [1,1,1,1,1]~

• Sau hai truy vấn thêm, ~a=[1,6,6,3,3]~