Tèo mới lên đại học và kiểm được một công việc tại hàng trà sữa, có không quá 200000 cốc trà sữa xếp thành 1 hàng ngang, ban đầu mỗi cốc trà sữa có độ ngọt băng 0. Tèo tiến hành liên tiếp N các thao tác, mỗi thao tác anh ta sẽ thêm 1 gam đường vào các cốc trà sữa từ vị trí L tới vị trí R. Sau cùng những cốc trà sữa có lượng đường >= K gam được chuyển đi để phục vụ khách hàng. Có nhiều câu hỏi, mỗi câu hỏi yêu cầu bạn trả lời trong các cốc trà từ thứ L tới thứ R có bao nhiêu cốc đạt chuẩn để bán cho khách hàng?

Định dạng đầu vào:

Dòng 1 gồm 3 số N, K, Q với Q là số truy vẫn

N dòng tiếp theo mỗi dòng gồm 2 số L, R (thao tác)

Q dòng tiếp theo mỗi dòng là 2 số L, R (truy vẫn)

Ràng buộc:

• 1<=K<=N<=200000

• 1<=Q<=200000

• 1<=L,R<=200000

Định dạng đầu ra: Đối với mỗi truy vấn in ra số lượng cốc trà sữa đạt chuẩn

Input:

5 3 4
2 9
5 8
2 4
2 4
1 6
3 4
5 7
5 8
5 8

Output:

2
2
2
2