Lệnh hiệu chỉnh nhiều tầng

Bối cảnh và bài toán

Một hệ thống có n tham số. Có m lệnh hiệu chỉnh đã định nghĩa sẵn; lệnh thứ i cộng một giá trị vào một đoạn tham số. Sau đó người quản trị gửi k yêu cầu, mỗi yêu cầu không tác động trực tiếp lên dữ liệu mà yêu cầu thực thi một đoạn liên tiếp các lệnh hiệu chỉnh trong danh sách.

Nếu mô phỏng từng yêu cầu rồi từng lệnh rồi từng phần tử, số thao tác có thể bùng nổ.

Yêu cầu

Tính mảng cuối cùng sau khi thực hiện tất cả yêu cầu.

Input

• Dòng 1: n m k.
• Dòng 2: n giá trị ban đầu.
• m dòng: l r d mô tả một lệnh range-add.
• k dòng: x y, yêu cầu thực thi mọi lệnh từ x đến y thêm một lần.

Output

In n giá trị cuối cùng.

Ràng buộc

• 1 <= n, m, k <= 10^5
• |a[i]| <= 10^5
• |d[i]| <= 10^5
• 1 <= l <= r <= n
• 1 <= x <= y <= m

Chấm điểm

Ví dụ 1

Input

3 3 3
1 2 3
1 2 1
1 3 2
2 3 4
1 2
1 3
2 3

Output

9 18 17

Giải thích. Mỗi lệnh được thực thi một số lần khác nhau tùy số yêu cầu phủ chỉ số lệnh đó; sau khi gom số lần thực thi mới áp chúng lên mảng.

Ví dụ 2

Input

1 1 1
1
1 1 1
1 1

Output

2

Giải thích. Lệnh duy nhất được gọi một lần và tăng phần tử duy nhất thêm 1.

Thông tin bài tập

Nguồn: Phỏng theo Codeforces 295A — Greg and Array.

Tham khảo: https://codeforces.com/problemset/problem/295/A