Cho một mảng A gồm n phần tử số nguyên. Bạn cần xử lý q truy vấn thuộc một trong ba loại:

• 1 x: Thêm giá trị x vào cuối của mảng A.
• 2: Xóa giá trị cuối cùng của mảng A.
• 3 l r: Tính tổng phần tử từ chỉ số l đến r, chỉ số của mảng bắt đầu từ 1.

Input

• Dòng đầu tiên gồm hai số nguyên n, q.
• Dòng thứ hai gồm n số nguyên A_i.
• q dòng tiếp theo, mỗi dòng mô tả một truy vấn theo định dạng đã nêu ở trên.

Output

• In ra một số nguyên cho mỗi truy vấn loại 3.

Giới hạn

• \(1 \le n, q \le 10^5\)
• \(1 \le x \le 10^9\)
• \(1 \le l \le r \le |A|\), với \(|A|\) là độ dài của mảng A tại thời điểm truy vấn này xuất hiện.

Ví dụ

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

15
5