Một hệ thống có ~N~ kênh tần số, được đánh số từ ~1~ đến ~N~.

Mỗi kênh ~i~ có một mức tải ~A_i~. Ban đầu: ~A_i = 0~ với mọi ~1 \le i \le N~.

Có ~Q~ thao tác được thực hiện trực tuyến.

Để tránh việc xử lý ngoại tuyến, hai đầu mút của mỗi thao tác được mã hóa theo kết quả truy vấn gần nhất.

Gọi ~last~ là kết quả của truy vấn loại ~2~ gần nhất. Ban đầu ~last = 0~.

Với mỗi thao tác, từ hai số ~x, y~ trong dữ liệu vào, ta giải mã:

~l = (x + last) \bmod N + 1~

~r = (y + last) \bmod N + 1~

Nếu ~l > r~ thì đổi chỗ ~l~ và ~r~.

Có hai loại thao tác:

• 1 x y v: tăng ~A_i~ thêm ~v~ với mọi ~l \le i \le r~.
• 2 x y: tìm giá trị lớn nhất của ~A_i~ với ~l \le i \le r~. In kết quả và gán kết quả đó cho ~last~.

Input

Dòng đầu gồm hai số nguyên ~N, Q~.

~Q~ dòng tiếp theo, mỗi dòng mô tả một thao tác:

• 1 x y v
• 2 x y

Output

Với mỗi thao tác loại 2, in ra một dòng chứa giá trị lớn nhất trên đoạn tương ứng.

Constraints

~1 \le N \le 10^9~

~1 \le Q \le 2 \cdot 10^5~

~0 \le x, y < N~

~1 \le v \le 10^9~

Mọi kết quả đều nằm trong phạm vi số nguyên 64-bit có dấu.

Sample Input

10 5
1 0 4 3
2 0 9
1 0 4 2
2 7 6
2 0 3

Sample Output

3
5
2

Explanation

Ban đầu ~last = 0~.

• Thao tác 1: đoạn sau giải mã là ~[1,5]~, tăng mỗi phần tử thêm ~3~.
• Thao tác 2: đoạn sau giải mã là ~[1,10]~, giá trị lớn nhất là ~3~, nên ~last = 3~.
• Thao tác 3: đoạn sau giải mã là ~[4,8]~, tăng mỗi phần tử thêm ~2~.
• Thao tác 4: đoạn sau giải mã là ~[1,10]~, giá trị lớn nhất là ~5~, nên ~last = 5~.
• Thao tác 5: đoạn sau giải mã là ~[6,9]~, giá trị lớn nhất là ~2~.