Cho một dãy gồm \(n\) phần tử có giá trị ban đầu bằng \(0\).

Cho \(k\) phép biến đổi, mỗi phép có dạng \((l,\ r,\ v)\): tăng mỗi phần tử trong đoạn \([l,\ r]\) lên \(v\) đơn vị.

Cho \(q\) câu hỏi, mỗi câu có dạng \((l,\ r)\): tính và in ra tổng các phần tử có vị trí nằm trong đoạn \([l,\ r]\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n,\ k\) - lần lượt là số lượng phần tử của dãy và số phép biến đổi;
• \(k\) dòng tiếp theo, mỗi dòng chứa ba số nguyên dương \(l,\ r,\ v\) thể hiện một phép biến đổi;
• Dòng tiếp theo chứa số nguyên dương \(q\) - số lượng câu hỏi;
• Sau đó là \(q\) dòng, mỗi dòng chứa hai số nguyên dương \(l,\ r\) thể hiện một câu hỏi.

Output

• Gồm \(q\) dòng, mỗi dòng là kết quả của câu hỏi tương ứng.

Ví dụ

Sample input

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

Sample output

17
21
4

Ràng buộc

• \(1\leq n,\ k,\ q\leq10^5\);
• \(1\leq v\leq 10^9\).