Keep Fit!

时间限制:30s    【提交】    空间限制:128MB

题目描述

You’re designing  a game console with a special  board which can evaluate how balance people  are. 
After the user stands on the board, it can record the movement of the user's "center of gravity". 
Technically,  the record is a sequence of  n  points  on  the  2D plane  (the user's "center of gravity" 
projected to the game board), where the origin (0,0) is the center of the game board. Samples are taken 
every 0.01 second, so if the user stands on it for one minute, your database gets 6000 sample points.  
In order to know better about his balancing status, the user can ask the game console some questions. 
Each question (i,j) means: count how many pairs of sample points, chosen from the interval between 
the i-th sample and the j-th sample (inclusive), whose Manhattan distance is no more than d, where d 
is the preset balance threshold parameter in the system. 
Your task is to write a program that can answer the questions. Note that you don't have to answer the 
questions one by one. You can read all the questions first, and then answer them. 


输入格式

There are no more than 3 test cases. The first line contains three integers n, d, q(1<=n<=200000, 
1<=d<=10^8, 1<=q<=10000), the number of points, the balance threshold and the number of queries. 
The next n lines contain the coordinates (x,y) (|x|,|y|<=10^8) of the sample points, in order. The points 
are numbered 1~n. The next q lines contain the questions (i,j) (1<=i<=j<=n). 


输出格式

For each test case, print the case number in the first line, then the answers of the questions, one on 
each line. 


样例输入

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

样例输出

Case 1: 
0 
4 
Case 2: 
3 
8 

提示

 2015年湖南省大学生程序设计竞赛


题目来源

鸣谢刘汝佳先生授权使用