Một chuỗi siêu thị có \(N\) kho hàng được đánh số từ \(1\) đến \(N\). Ban đầu, kho hàng thứ \(i\) có \(A_i\) tấn hàng. Từ sáng sớm, có rất nhiều lượt xe chở hàng đến các kho, xe thứ \(t\) sẽ bổ sung cho các kho từ \(L_t\) đến \(R_t\), mỗi kho thêm \(X_t\) tấn hàng để chuẩn bị cho ngày mới.

Trong khi các kho đang nhận hàng, quản lý sẽ liên tục kiểm tra lượng hàng thực tế trong kho và lập kế hoạch phân phối cho ngày mới:

• Để kiểm tra lượng hàng thực tế trong các kho, quản lý sẽ hỏi các câu hỏi: tính tổng khối lượng hàng trong các kho được đánh số từ \(L\) đến \(R\).
• Để lập kế hoạch cho ngày mới, ban quản lý cần giải quyết các câu hỏi: nếu lấy hàng ở các kho liên tiếp bắt đầu từ kho được đánh số \(L\) trở về sau, thì cần lấy hàng ở tối thiểu bao nhiêu kho để có thể lấy đủ \(X\) tấn hàng, hoặc là không thể lấy đủ. Lưu ý rằng các câu hỏi này chỉ là các giả định và không thực sự lấy hàng ra khỏi kho.

Ban quản lý đã biết trước được kế hoạch nhận hàng của kho, cũng như các câu hỏi cần trả lời ở các thời điểm khác nhau. Do đó, họ đã chia quá trình nhận hàng, kiểm tra và lập kế hoạch phân phối thành \(Q\) sự kiện theo dòng thời gian, mỗi sự kiện thuộc một trong ba loại kể trên. Với mỗi sự kiện, ban quản lý sẽ tính toán được câu trả lời chính xác cho các câu hỏi.

Input

• Dòng đầu tiên gồm hai số nguyên \(N, Q\) \((1 \le N, Q \le 3 \cdot 10^5)\).
• Dòng tiếp theo gồm \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\) \((1 \le A_i \le 10^4)\).
• \(Q\) dòng tiếp theo, mỗi dòng thuộc một trong ba loại sau:
  • Mô tả sự kiện nhận hàng (loại \(1\)): 1 L R X \((1 \le L \le R \le N,\ 1 \le X \le 10^4)\).
  • Mô tả câu hỏi kiểm tra tổng (loại \(2\)): 2 L R \((1 \le L \le R \le N)\).
  • Mô tả câu hỏi lấy hàng (loại \(3\)): 3 L X \((1 \le L \le N,\ 1 \le X \le 10^5)\).

Output

• Với mỗi câu hỏi loại \(2\) và \(3\), in ra kết quả trên một dòng.
  • Với câu hỏi loại \(2\), in ra một số nguyên là tổng khối lượng hàng có trong các kho từ \(L\) đến \(R\).
  • Với câu hỏi loại \(3\), in ra:
    • \(-1\) nếu không thể lấy đủ \(X\) tấn hàng.
    • Một số nguyên dương là số kho ít nhất cần lấy nếu có thể lấy đủ hàng.

Example

3 6
1 2 3
1 1 2 1
1 2 3 2
2 1 2
2 2 3
3 1 4
3 3 10

7
10
2
-1

Scoring

• \(20\%\) số điểm có \(N, Q \le 2000\).
• \(20\%\) số điểm khác không có yêu cầu loại \(1\).
• \(20\%\) số điểm khác có yêu cầu loại \(1\) xuất hiện trước các yêu cầu loại \(2\) và \(3\).
• \(20\%\) số điểm khác không có yêu cầu loại \(3\).
• \(20\%\) số điểm còn lại không có giới hạn gì thêm.