UPIT - Sequence queries

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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 ≤ 10 5 ).
  • Dòng tiếp theo mô tả dãy số. Mỗi số không vượt quá 10 5 .
  • 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

  • Người up: khanhptnk