Tổng đoạn con

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$ (mọi $a_i=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$ (mỗi phần tử $a_l,a_{l+1},\dots ,a_r$ tăng thêm $v$). Với $p$ truy vấn loại $2$ tính tổng các giá trị trong đoạn $[l,r]$, tức là $a_l+a_{l+1}+\dots +a_r$.

Tất cả $q$ truy vấn loại $1$ được thực hiện trước, sau đó mới đến $p$ truy vấn loại $2$. Ràng buộc $|a_i|\le {10}^9$ áp dụng cho mọi phần tử của dãy sau khi thực hiện xong mọi truy vấn loại $1$.

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

Dữ liệu vào

• 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 một truy vấn loại $1$ gồm $3$ số nguyên $l$, $r$ và $v$ $(1\le l\le r\le N$ và $|v|\le {10}^9)$.
• $p$ dòng cuối, mỗi dòng chứa một truy vấn loại $2$ gồm $2$ số nguyên $l$ và $r$ $(1\le l\le r\le N)$.

Các số trên cùng một dòng cách nhau một dấu cách.

Dữ liệu ra

Gồm $p$ dòng, mỗi dòng là kết quả tính được trong đoạn $[l,r]$ của truy vấn loại $2$ tương ứng.

Ràng buộc

• $1\le N,q,p\le {10}^6$.
• $1\le l\le r\le N$, $|v|\le {10}^9$.
• Sau khi thực hiện mọi truy vấn loại $1$, $|a_i|\le {10}^9$ với mọi $i$.

Subtasks

• $60\%$ số test: $N,p,q\le {10}^3$.
• $25\%$ số test: $N,q\le {10}^4$, $p\le {10}^5$.
• $15\%$ số test còn lại: $N,p,q\le {10}^6$.

Ví dụ