Đề bài

Cho mảng A gồm N phần tử, ban đầu tất cả bằng 0.

Có Q thao tác cộng đoạn.

Mỗi thao tác gồm:

L R X

nghĩa là cộng X vào mọi phần tử từ vị trí L đến R.

Sau khi thực hiện xong toàn bộ Q thao tác, có M truy vấn.

Mỗi truy vấn gồm hai số U, V.

Hãy tính tổng các phần tử trong đoạn:

[U, V]

Dữ liệu vào

Dòng đầu chứa ba số nguyên N, Q, M.

Q dòng tiếp theo chứa ba số nguyên L, R, X.

M dòng cuối chứa hai số nguyên U, V.

Dữ liệu ra

Với mỗi truy vấn, in ra tổng đoạn tương ứng.

Giới hạn

1 ≤ N ≤ 10⁶
1 ≤ Q, M ≤ 2×10⁵
1 ≤ X ≤ 10⁹

Ví dụ

Input

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

Output

10
7
3

Giải thích

Mảng cuối cùng là:

2 3 3 1 1

Tổng đoạn [1,5] = 10.
Tổng đoạn [2,4] = 7.
Tổng đoạn [3,3] = 3.