Tết đến gần, Tít hứng khởi nhận những bao lì xì đầu tiên trong dịp tết. Hiện tại Tít có tổng cộng bao lì xì, trong đó bao lì xì thứ có số tiền là . Vui chơi không quên kiến thức, cậu bé liền ôn lại một chút ít kiến thức toán học và cậu đã sử dụng đến những bao lì xì để làm điều đó. Cậu xếp bao lì xì thành hàng ngang và đánh số từ 1 đến từ trái qua phải. Tít định nghĩa giá trị “Phú Quý” của đoạn là giá trị hay đó là tổng số tiền mừng tuổi trong các bao lì xì từ vị trí đến vị trí . Tiếp theo, cậu chọn sẵn một số nguyên dương và nhờ bố chuẩn bị cho cậu ta yêu cầu, và trong yêu cầu này thì có hai loại như sau:
(với ): yêu cầu này đề nghị cậu bé xếp lại vị trí của bao lì xì theo vị trí chỉ định theo cách “dịch sang trái”. Tức là ban đầu bao lì xì này xét theo thứ tự là thì sau đó Tít phải sắp xếp lại thành theo thứ tự vị trí đó.
(với ): nếu gặp yêu cầu này của bố, Tít sẽ phải đưa ra tổng của tất cả các giá trị “Phú Quý” của các đoạn mà thỏa mãn .
Ban đầu, các câu hỏi của bố khá đơn giản, Tít có thể trả lời dễ dàng. Nhưng càng về sau, khi càng có nhiều bao lì xì hơn, Tít cảm thấy khó khăn và việc tính toán trở nên chậm hơn. Do đó, bạn hãy giúp Tít thực hiện các yêu cầu của bố.
Dữ liệu:
Dòng đầu gồm hai số nguyên dương và ().
Dòng thứ hai gồm giá trị () – biểu thị số tiền mừng tuổi trong các bao lì xì của Tít.
Dòng thứ ba gồm một số nguyên dương () – số lượng yêu cầu của bố.
dòng tiếp theo, mỗi dòng biểu diễn một trong hai loại yêu cầu kể trên.
Kết quả: Với mỗi yêu cầu loại , hãy giúp Tít đưa ra kết quả trên một dòng.
Ví dụ:
Dữ liệu:
8 3
7 2 5 1 9 3 4 6
3
2 2 7 4
1 2 5 8
2 2 7 3
Kết quả:
52
50
Giải thích:
Với yêu cầu thứ nhất: mảng ban đầu là [7,2,5,1,9,3,4,6]. Đoạn cần xét là từ vị trí 2 đến 7, tức là [2,5,1,9,3,4]. Các đoạn con có độ dài 4 là [2,5,1,9], [5,1,9,3], [1,9,3,4]. Tổng giá trị "Phú Quý" của chúng là .
Với yêu cầu thứ hai: thực hiện phép "dịch sang trái" với các phần tử ở vị trí 2, 5, 8. Các giá trị tương ứng là . Sau khi dịch, mảng trở thành [7,9,5,1,6,3,4,2].
Với yêu cầu thứ ba: mảng hiện tại là [7,9,5,1,6,3,4,2]. Đoạn cần xét là từ vị trí 2 đến 7, tức là [9,5,1,6,3,4]. Các đoạn con có độ dài 3 là [9,5,1], [5,1,6], [1,6,3], [6,3,4]. Tổng giá trị "Phú Quý" là .
