Vampire Basketball

The picture shows an example. $b_1 = \frac{2}{26 \cdot 4} = \frac{1}{52}$, $b_2 = \frac{3}{40 \cdot 3} = \frac{1}{40}$, $b_3 = \frac{2}{20 \cdot 4} = \frac{1}{40}$.

Note that the hoop is a point.

Vampires love sports and are good at them. It is autumn, and playing baseball outside is too chilly, so the vampires decided to play basketball in the gym. As soon as they arrive, they split into two teams. Edward always plays point guard because he likes to make passes. For each lineup, he wants to know which of his teammates are in the most favorable position and which are not.

The court is a half-plane. Every point has integer coordinates $x$ and $y$ with $y \ge 0$. The hoop is at $(0, 0)$. The three-point arc is a semicircle with radius $r$ centered at the hoop. If a player's distance to the hoop is strictly greater than $r$, a made shot is worth three points, otherwise two. Edward knows that all players on his team shoot the same way. Each opponent has a defensive skill, given as a natural number.

Each vampire wears a jersey with a number. Numbers within a team are distinct and consecutive. For example, if Edward's team has three vampires and the opponents have two, their numbers are 1, 2, 3 and 1, 2. Edward wears jersey number 0, and his own position does not matter to him.

Edward rates the favorability of teammate $i$ with the formula

$b_i = \frac{p_i}{d_i^2 \cdot (1 + \sum z_j)}$

where $p_i$ is the number of points a shot from that spot is worth, $d_i$ is the distance from the vampire to the hoop, and $\sum z_j$ is the sum of the defensive skills of the opponents whose distance to the attacker does not exceed $l$.

To help Edward, print the jersey numbers of his teammates in decreasing order of favorability. If two favorability values are equal, the smaller number comes first.

The first line contains $n$, $m$, $r$, $l$ ($1 \le n, m \le 10^3$, $1 \le r, l \le 10^5$): the number of vampires on Edward's team, the number of opponents, the radius of the three-point arc, and the distance within which defenders affect players.

The next $n$ lines contain the coordinates $x_i$ and $y_i$ of Edward's teammates in jersey number order ($1 \le y_i \le 10^5$, $-10^5 \le x_i \le 10^5$). The next $m$ lines contain the coordinates $x_j$ and $y_j$ of the opponents in jersey number order (same bounds), followed by $z_j$ ($1 \le z_j \le 100$), the defensive skill of opponent $j$.

All player positions are distinct.

Print $n$ numbers: the jersey numbers of Edward's teammates in the required order.