Cho dãy \(A\) gồm \(N\) số nguyên \(a_1, a_2, …, a_N (|a_i| ≤ 10^9)\). Ban đầu dãy số bằng 0, với \(q\) truy vấn loại 1 cần xây dựng lại dãy số như sau: trong đoạn từ \(l\) đến \(r\) tăng thêm giá trị là \(v\). Với \(p\) truy vấn loại 2 tính tổng các giá trị trong đoạn [\(l,r\)].

Yêu cầu: Hãy viết chương trình tính tổng các giá trị trong đoạn từ [\(l,r\)] cho mỗi truy vấn loại 2.

Input:

• Dòng đầu chứa 3 số nguyên dương \(N, q\) và \(p\);
• \(q\) dòng tiếp theo, mỗi dòng chứa truy vấn loại \(1: l, r, v\) (\(1 ≤ l ≤ r ≤ N, |v| ≤ 10^9\));
• \(p\) dòng cuối, mỗi dòng chứa 2 số \(l\) và \(r\) (\(1 ≤ l ≤ r ≤ N\)).

Các số trên đề bài cách nhau một dấu cách.

Output:

• Ghi ra \(p\) dòng mỗi dòng tương ứng với kết quả tính được trong đoạn [\(l,r\)] đã cho..

Scoring

• Có 60% test tương ứng 60% số điểm với \(N, p, q ≤ 10^3\);
• Có 25% test tương ứng 25% số điểm với \(N, q ≤ 10^4, p ≤ 10^5\);
• Có 15% test khác ứng với 15% số điểm còn lại của bài với \(N, p, q ≤ 10^6\).

Example

5 2 1
1 2 3
3 5 2
2 3      

5

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

8
6