Tại Thành phố Hồ Chí Minh, nơi phát triển kinh tế tốt nhất tại đất nước Việt Nam. Mỗi ngày, các coder phải tính toán như sau: Có \(N\) nhà máy điện đứng thẳng hàng, mỗi nhà máy \(i\) ban đầu sản xuất \(a_i\) megawatt (MW) điện. Chính quyền thành phố yêu cầu bạn xử lý \(q\) truy vấn thuộc \(3\) loại:

1. Truy vấn cập nhật đoạn: Tăng công suất của tất cả nhà máy từ vị trí \(l\) đến \(r\) thêm \(v\) MW.
2. Truy vấn cập nhật điểm: Thay đổi công suất của nhà máy tại vị trí \(pos\) thành \(v\) MW.
3. Truy vấn câu hỏi: Tìm nhà máy có công suất nhỏ nhất trong đoạn \([l, r]\).

Vì p2o2HuaGiaBao dẫn các học sinh có tiềm năng đến nơi làm việc của các coder đó. Anh ta thử thách các học sinh tính toán bài toán trên. Để thể hiện điều đó, các bạn cần AC bài tập này để tuyển chọn vào Đội Tuyển Học Sinh Giỏi HGBCpp_.

Input

• Dòng đầu tiên chứa \(2\) số nguyên dương \(1\le N, q \le 10^5\). (Với \(N\) là số lượng nhà máy, \(q\) là số lượng truy vấn).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,a_3,...,a_n\) (\(a_i \le 10^9\)) để biểu diễn giá trị công suất của nhà máy thứ \(i\).
• \(q\) dòng tiếp theo biểu diễn mỗi truy vấn như trên.
  • Đối với truy vấn loại \(1\): \(1\le l,r\le N,\) \(v\le 10^9\)
  • Đối với truy vấn loại \(2\): \(1\le pos\le N,\) \(v\le 10^9\)
  • Đối với truy vấn loại \(3\): \(1\le l,r\le N\)

Output

• In ra các kết quả trong truy vấn loại \(3\).

Example

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

3
5