Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

UPIT - Sequence queries

Cho một dãy số và các loại truy vấn sau:

1 A B X: gán các phần từ thứ A đến thứ B trong dãy bằng X.

2 A B X: cộng phần tử thứ A cho X, thứ A + 1 cho 2X,... , thứ B cho (B - A + 1) * X.

3 C X: chèn X vào trước phần tử thứ C của dãy hiện thời.

4 A B: tính tổng từ phần tử thứ A đến thứ B.

Input

  • Dòng đầu ghi hai số nguyên N và Q, số phần tử của dãy ban đầu và số truy vấn (1 ≤ N, Q ≤ 105).
  • Dòng tiếp theo mô tả dãy số. Mỗi số không vượt quá 105.
  • Q dòng tiếp theo mô tả các truy vấn theo định dạng như trong đề bài. Trong mọi truy vấn, 0 ≤ X ≤ 100, 1 ≤ A ≤ B ≤ độ dài dãy hiện thời, 1 ≤ C ≤ độ dãy dãy hiện thời + 1.

Output

  • In ra trên từng dòng câu trả lời cho mỗi truy vấn loại 4.

Example

Input 1:
5 5 
1 2 3 4 5
1 5 5 0
4 4 5
4 5 5
2 1 5 1
4 1 5 Output 1: 4
0
25

Input 2:
1 7
100
3 1 17
3 2 27
3 4 37
4 1 1
4 2 2
4 3 3
4 4 4

Output 2:
17
27
100
37

Được gửi lên bởi:khanhptnk
Ngày:2011-04-13
Thời gian chạy:0.200s-1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED

hide comments
2011-04-16 15:02:33 T_
1s-3s
chen mat nhieu tg qua
2011-04-16 13:41:04 Nguyên
Việc gì phải xem solution cho lằng nhằng, xuất file out ra có phải lẹ hơn ko.
2011-04-16 10:14:33 TNO
COCI
chưa có solution mà
thế mới bảo chờ solution

Last edit: 2011-04-16 18:09:29
2011-04-14 15:23:07 SOAP MacTavish
For trau chay test 8 rat lau , co ve test nay nang.
Co the cai dem phan phoi :d



Last edit: 2011-04-27 14:12:10
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.