## Good Aim

View as PDF

Points: 10
Time limit: 2.75s
Memory limit: 256M

Author:
Problem types

The heated competition of the ACM-ICPC World Finals continues, and The Team is at the top of their game! Well, okay, maybe they're not actually doing so well, according to the scoreboard, yet. But they have a plan!

The contest is taking place in a huge room with a regular grid of desks. The columns and rows are each numbered , and the desk in the th column and th row is considered to have coordinates . The Team is sitting at coordinates . There are opposing teams (conveniently numbered ), with team having members, all sitting at coordinates . No desk is occupied by more than one team, and all other desks are empty.

Now, The Team is interested in removing some of the more dangerous opponents from the competition. To accomplish this, they have a number of water balloons at their disposal (after all, where in the contest rules does it say that water balloons are not allowed?). Always conservative, they would first like to answer queries - for the th query, how many balloons it would theoretically take to take out all of the members of team ?

In order to do any real damage, the water balloons will of course have to be thrown extremely hard - in fact, in a perfectly straight line, and not over any obstacles besides empty desks. This means that, if team lies exactly on the line segment from The Team to team , then every member of team must be dispatched before any members of team can be hit. It takes one balloon to knock one person out (the members of The Team have received plenty of training, so they're not about to miss a throw). Note that these queries are all only theoretical (for the moment) - so each should be answered assuming that all teams are still untouched.

The members of The Team will need to carefully choose which opponents to take out, based on how well they're doing and how many balloons it would take, so they're already answered all of their queries in their heads. Maybe, if you can answer them as well, you can also adopt such techniques in the future…

#### Input Specification

First line: 4 integers, , , , and
Next lines: 3 integers, , , and , for
Next lines: 1 integer, , for

#### Output Specification

lines: 1 integer, the number of balloons that would be required to take out team , for .

#### Sample Input

6 6 3 2
5 6 3
2 1 5
4 4 2
4 3 1
5 4 2
7 6 1
6
5
4
3
2
1

#### Sample Output

4
3
1
2
5
5

#### Explanation of Sample

The following grid shows the positions of the opposing teams (marked with their numbers), as well as The Team (marked with a T). The line segments represent direct lines of sight to the opponents.

As can be seen, team 6 is blocked by teams 4 and 5. Therefore, taking them out would require balloons in total. Similarly, team 5 is blocked by team 4, and requires balloons. Teams 4, 3, and 2 are not blocked by any others, and so only require 1, 2, and 5 balloons, respectively. Finally, team 1 is blocked by team 3, and would require balloons to dispose of.