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

Cho \(m\) phép biến đổi, mỗi phép có dạng \((u, v, k)\): tăng mỗi phần tử từ vị trí \(u\) đến vị trí \(v\) lên \(k\) đơn vị.

Cho \(q\) câu hỏi, mỗi câu có dạng \((u, v)\): cho biết phần tử có giá trị lớn nhất thuộc đoạn \([u, v]\)

Giới hạn

• \(n, m, q \le 50000\)
• \(k \gt 0\)
• Giá trị của một phần tử luôn không vượt quá \(2^{31}-1\)

Dữ liệu vào

• Dòng \(1\): \(n, m\)
• \(m\) dòng tiếp theo, mỗi dòng chứa \(u, v, k\) cho biết một phép biến đổi
• Dòng thứ \(m+2\): \(p\)
• \(q\) dòng tiếp theo, mỗi dòng chứa \(u, v\) cho biết một phép biến đổi

Dữ liệu ra

Gồm \(q\) dòng chứa kết quả tương ứng cho từng câu hỏi.

Input 1

6 2
1 3 2
4 6 3
1
3 4

Output 1

3