Subspecies

A university is studying a newly discovered species of annelid (a segmented worm) whose body has a very large number of segments. The research team has earned the right to name the species, and they may also split the discovered specimens into several subspecies.

For two specimens to belong to the same subspecies, their length, weight, and number of segments must not differ by too much. Specifically, the length difference may be at most $D$, the weight difference at most $W$, and the segment-count difference at most $S$.

For each specimen $o$, determine how many other specimens $p$ could belong to the same subspecies as $o$.

The first line contains the number of test cases $Z$ ($Z = 1$). Each test case follows.

The first line of a test case contains the number of specimens $N$ ($1 \le N \le 80000$). The next line contains three integers $D$, $W$, $S$ ($1 \le D, W, S \le 10^9$).

Each of the next $N$ lines contains the length $d_i$, weight $w_i$, and segment count $s_i$ of one specimen ($1 \le d_i, w_i, s_i \le 10^9$). Because the measurements were extremely precise, the lengths of any two distinct specimens are all different, and so are the weights.

Print $N$ non-negative integers on a single line, separated by spaces. The $i$-th integer is the number of specimens, other than specimen $i$ itself, that could belong to the same subspecies as specimen $i$.

In the example, specimens 1 and 3 have lengths that differ by $2$, which exceeds $D = 1$, so they can never be placed in the same subspecies. Every other pair can.