Một lần nữa Bình và An lại đặt ra bài toán để cùng nhau giải. Lần này bài toán An đặt ra bài toán để cùng nhau giải. Lần này bài toán An đặt ra cho Bình không chỉ mang tính trí tuệ mà còn như một trò chơi vận động, cụ thể như sau:

Trên con đường quê Cam Lộ rất dài và thẳng tắp. An kẻ một dây ~N~ ô vuông liên tiếp và đánh chỉ số các ô vuông lần lượt từ ~1~ đến ~N~. Sau đó An đưa ra ~M~ cặp chỉ số dạng ~(i,j)~, với mỗi cặp chỉ số dạng ~(i,j)~ đó An yêu cầu Bình đi từ ô có chỉ số ~i~ đến ô có chỉ số ~j~ và với mỗi ô đi qua thì đặt vào ô đó một hạt sỏi. Bình thực hiện yêu cầu của An xong thì đôi chân đã mỏi nhừ, cậu nghĩ rằng mình cũng nên yêu cầu An làm một việc gì đó. Sau một hồi suy nghĩ, Bình quyết định sẽ đưa ra ~K~ cặp chỉ số dạng ~(u,v)~, đề nghị An cho biết với mỗi cập chỉ số mình đưa ra thì tổng các hạt sỏi trong các ô từ ô có chỉ số ~u~ đến ô có chỉ số ~v~ là bao nhiêu?

Yêu cầu: bạn hãy viết chương trình giúp An trả lời các yêu cầu của Bình.

Input

Vào từ file văn bản DEMSOI.INP có cấu trúc:

• Dòng đầu ghi số nguyên dương ~N (2 \leq N \leq 10^5)~.

• Dòng thứ hai ghi số nguyên dương ~M (1 \leq M \leq 10^5)~.

• ~M~ dòng tiếp theo, mỗi dòng ghi hai số nguyên dương ~i~ và ~j~ cho biết một cặp chỉ số mà An đưa ra ~(1 \leq i < j \leq N)~.

• Dòng tiếp theo ghi một số nguyên dương ~K (1 \leq K \leq 10^5)~.

• ~K~ dòng tiếp theo, mỗi dòng ghi hai số nguyên dương ~u~ và ~v~ cho biết một cặp chỉ số mà Bình đưa ra ~(1 \leq u < v \leq N)~.

Output

Ghi ra file văn bản DEMSOI.OUT gồm ~K~ dòng, mỗi dòng ghi một số là tổng hạt sỏi trong các ô từ ô có chỉ số ~u~ đến ô có chỉ số ~v~ tương ứng được cho trong file dữ liệu vào.

Scoring

• Subtask ~1~ ~(40\%)~ tests tương ứng với ~40\%~ số điểm có ~N,M,K \leq 10^3~.

• Subtask ~2~ ~(30\%)~ tests tương ứng với ~30\%~ số điểm có ~N,M,K \leq 2.10^4~.

• Subtask ~3~ ~(30\%)~ tests tương ứng với ~30\%~ số điểm có ~N,M,K \leq 10^5~.

Example input 1

10
3
1 10
2 8
4 7
3
1 4
3 7
6 10

Example output 1

8
14 
10