Cho dãy ~A~ gồm ~N~ số nguyên ~a_1, a_2, \dots, a_N~ ~(|a_i| \le 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~;

• Dòng tiếp theo chứa ~q~ truy vấn loại ~1~: ~l, r~ và ~v~ ~(1 \le l \le r \le N~ và ~|v| \le 10^9)~;

• ~p~ dòng cuối chứa ~2~ số ~l~ và ~r~ ~(1 \le l \le r \le N)~.

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

Output

Gồm ~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

Sample Input 1

5 2 1
1 2 3
3 5 2
2 3

Sample Output 1

5

Sample Input 2

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

Sample Output 2

8
6