ShyWoou có một dãy số gồm \(N\) phần tử \(a_1, a_2, ..., a_n\) biểu diễn trên một vòng tròn, bắt đầu từ \(1\) theo chiều kim đồng hồ, ShyWoou có \(Q\) thao tác thực hiện lần lượt, thao tác thứ \(i\) sẽ có một trong ba loại như sau:

• \(1\) \(d:\) đẩy toàn bộ vòng tròn xoay theo chiều kim đồng hồ \(d\) vị trí.
• \(2\) \(s\) \(t\) \(p:\) thay thế giá trị nhỏ nhất trong đoạn \([s, t]\) thành giá trị \(p\) \((\)nếu có nhiều giá trị nhỏ nhất, hãy chọn giá trị có chỉ số thấp nhất\().\)
• \(3\) \(u\) \(v:\) tính tổng các số từ vị trí \(u\) đến vị trí \(v.\)

ShyWoou yêu cầu bạn thực hiện \(Q\) thao tác và in ra kết quả của thao tác loại \(3\).

Input

• Dòng đầu tiên gồm số nguyên \(N, Q\) \((N \leq 10^6, Q \leq 10^5)\)
• Dòng thứ hai gồm \(N\) số nguyên \(a_1, a_2, ..., a_{N}\) \((a_{i} \leq 10^6)\).
• \(Q\) dòng tiếp theo, với dòng thứ \(i:\) số đầu tiên là \(1\) hoặc \(2\) hoặc \(3\).
  • Số \(1\) theo sau bởi số nguyên \(d\) \((1 \leq d \leq 10^6).\)
  • Số \(2\) theo sau bởi ba số nguyên \(s \space t \space p\) \((1 \leq s \leq t \leq N), (1 \leq p \leq 10^6).\)
  • Số \(3\) theo sau bởi hai số nguyên \(u \space v\) \((1 \leq u \leq v \leq N).\)

Output

• Với thao tác \(3\) có dạng \(3 \space u \space v\), in ra tổng các phần tử từ vị trí \(u\) đến vị trí \(v\) trên vòng tròn.

Sample Input

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

Sample Output

10

Subtask

• \(30\%\) số test đầu tiên có \(N \leq 10^3, Q \leq 10^3\).
• \(70\%\) số test còn lại có \(N \leq 10^6, Q \leq 10^5\).