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 ~p~ câu hỏi, mỗi câu có dạng (~u~, ~v~): cho biết giá trị lớn nhất của các phần tử có vị trí nằm trong đoạn [~u~, ~v~]

Input

• 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~: một số ~p~
• ~p~ dòng tiếp theo, mỗi dòng chứa 2 số ~u~, ~v~ cho biết một câu hỏi

Output

• Gồm ~p~ dòng chứa kết quả tương ứng cho từng câu hỏi.

Giới hạn

• ~n~, ~m~, ~p~ ~\leq~ ~50000~
• ~0 < k ~
• Giá trị của một phần tử luôn không vượt quá ~2^{31} -1~

Sample Input

6 2
1 3 2
4 6 3
1
3 4

Sample Output

3