Description

All discussions in this problem take place on the Cartesian coordinate plane.

There are $N$ people. Each person has a field of view, and each person is located at $(x_i,0)$.

A field of view can be modeled as an angle.

Note that the two rays that form the angle are not included in the field of view.

Now, you may stand at $(a,Y)$, where $L \le a \le R$.

For each $i$ $(0 \le i \le N)$, find how many positions you can stand at such that you are inside the field of view of at most $i$ people.

Input Format

The first line contains an integer $N$.

The second line contains three integers $L, R, Y$.

The next $N$ lines each contain three integers $x_i, v_i, h_i$. Here, $v_i$ and $h_i$ mean that the slopes of the two rays forming the angle are $\frac{v_i}{h_i}$ and $\frac{-v_i}{h_i}$, and one endpoint is at $(x_i,0)$.

Output Format

There are $N+1$ lines, each containing one integer. The value on line $i$ indicates the number of positions where you can stand such that you are inside the field of view of at most $i-1$ people.

3
-7 7 3
0 2 3
-4 2 1
3 3 1

5
12
15
15

Hint

Sample Explanation

Subtasks

This problem uses bundled testdata.

• Subtask 1 ($60$ points): It is guaranteed that $-10^6 \le L \le R \le 10^6$.
• Subtask 2 ($40$ points): No additional constraints.

For $100\%$ of the testdata, it is guaranteed that $1 \le N \le 10^5$, $-10^9 \le L \le R \le 10^9$, $1 \le Y \le 10^6$, $1 \le x_i \le R$, and $1 \le v_i, h_i \le 100$.

Notes

This problem is translated from Canadian Computing Olympiad 2020 Day 1 T1 A Game with Grundy.

Translated by ChatGPT 5