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:Nguyễn Xuân Khánh
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
2016-12-11 16:21:45
trâu cx AC
2016-10-10 15:42:57
làm sao vậy mọi người mình được có 41.67
2011-05-20 01:40:22 Nguyễn Phúc Bình Nguyên
Bài này dùng IT như thế nào nhỉ?? Coi bộ khó quá
2011-04-28 13:54:08 SOAP MacTavish
Thay Hoang bat dau ngam cuu bai nay :))
2011-04-28 04:40:50 kunn
đề nói 1<=x nhưng trong test 1 thì x=0 ???
trong bộ test có th nào x=0 nữa k ạ?
2011-04-22 00:39:57 Nguyễn Xuân Khánh
TLE đấy. Anh chỉnh lên 5s vậy :(
2011-04-21 17:06:17 Tue Le
Mình acc trên coci với time test lâu nhất là 0.7s. Về đây chạy vẫn lẹt đẹt 58 điểm :(
2011-04-18 16:43:39 vn_army
em nghĩ là cần nâng cấp máy chấm của vnoi,
nếu máy anh chạy 1,8s ps để 1 ->3s là khá hợp lí :))
2011-04-18 14:28:16 Tue Le
Mình cài cây cân bằng, chạy test lâu nhất trên máy mình mất 1.8s, lên đây được có 58 điểm. Mình nghĩ PS nên cân nhắc lại time limit!
2011-04-17 05:38:51 vn_army
bài này dùng interval tree được không nhỉ? thấy trâu bò quá =.=
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.