GOODF - Good Aim

no tags 

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 $1..10^6$, and the desk in the $x$th column and $y$th row is considered to have coordinates ($x$,$y$). The Team is sitting at coordinates ($X$,$Y$). There are $N$ ($1 \leq N \leq 10^6$) opposing teams (conveniently numbered $1..N$), with team $i$ having $m_i$ ($1 \leq m_i \leq 10^6$) members, all sitting at coordinates ($x_i$,$y_i$). 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 $Q$ ($1 \leq Q \leq 10^6$) queries - for the $i$th query, how many balloons it would theoretically take to take out all of the members of team $q_i$?

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 $j$ lies exactly on the line segment from The Team to team $i$, then every member of team $j$ must be dispatched before any members of team $i$ 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 with 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

First line: 4 integers, $N$, $Q$, $X$, and $Y$

Next $N$ lines: 3 integers, $x_i$, $y_i$, and $m_i$, for $i = 1..N$

Next $Q$ lines: 1 integer, $t_i$, for $i = 1..Q$

Output

$Q$ lines: 1 integer, the number of balloons that would be required to take out team $t_i$, for $i = 1..Q$.

Example

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
Output:
4
3
1
2
5
5
Explanation of Sample:

The following grid shows the positions of the $N$ 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 $1+2+1=4$ balloons in total. Similarly, team 5 is blocked by team 4, and requires $1+2=3$ 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 $2+3=5$ balloons to dispose of.



Added by:SourSpinach
Date:2013-05-09
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem