works part-time at the Centre for Disease Control and Prevention (CDC), where he researches the spread of diseases. An unknown pathogen has just broken out and is determined to save the world!
The CDC's model of the world consists of countries numbered through , represented by points on a 2-D coordinate plane. Country is located at integral coordinates .
Through extensive research, is located at and country is located at , it will take hours for country to be infected after the initial infection of country . The source of the breakout, country , is infected at the -th hour.has determined a vital piece of information: the time in hours it takes for the pathogen to spread from one country to another is equal to the square of the distance between the two countries. For example, if country
In order to take preventative measures, queries of the following form:has been tasked with projecting the rate of infection. Specifically, he has to answer
How many countries will be infected after hours?
Unfortunately,isn't taking data management this semester, so he's at a total loss. Help him save the world!
Subtask 1 [20%]
Subtask 2 [30%]
Subtask 3 [50%]
The first line of input will contain , the number of countries.
The next lines will contain and , the coordinates of the -th country, it is guaranteed that no two countries will have the same coordinates.
The next line will contain , the source of the breakout.
The next line will contain , the number of queries.
The next lines will each contain a query.
For each query, output the answer on a new line.
4 2 2 0 3 5 1 4 0 1 4 8 10 4 7
3 4 1 2
Explanation for Sample Output
After hours, the pathogen has not yet spread from its source, therefore the answer is . After hours, country is infected. After hours, country is also infected. At hours, the pathogen has spread from country to country .