Canadian Computing Olympiad: 2020 Day 1, Problem 1

Grundy is playing his favourite game — hide and seek.

His ~N~ friends stand at locations on the ~x~-axis of a two-dimensional plane — the ~i~-th one is at coordinates ~(x_i,0)~. Each friend can see things in a triangular wedge extending vertically upwards from their position — the ~i~-th friend's triangular wedge of vision will be specified by two lines: one with slope of ~v_i/h_i~ and the other with slope ~-v_i/h_i~. A friend cannot see a point that lies exactly on one of these two lines.

Grundy may choose to hide at any location ~(a, Y)~, where ~a~ is an integer satisfying ~L \le a \le R~, and ~L~, ~R~, and ~Y~ are given integer constants.

Each possible location may be in view of some of Grundy's friends (namely, strictly within their triangular wedge of vision).

Grundy would like to know in how many different spots he can stand such that he will be in view of at most ~i~ of his friends, for every possible value of ~i~ from ~0~ to ~N~.

Input Specification

The first line of input contains the integer ~N~ ~(1 \le N \le 100\,000)~.

The next line contains three integers: ~L~, ~R~, and ~Y~ ~(-1\,000\,000\,000 \le L \le R \le 1\,000\,000\,000~, ~1 \le Y \le 1\,000\,000)~.

Each of the next ~N~ lines contain three integers: the ~i~-th such line contains ~x_i~ ~(L \le x_i \le R)~, the ~x~-value of the position of friend ~i~ followed by two integers ~v_i~ and ~h_i~ ~(1 \le v_i, h_i \le 100)~. The slopes ~v_i/h_i~ and ~-v_i/h_i~ define the triangular wedge of vision for friend ~i~.

For 15 of the 25 marks available, ~-1\,000\,000 \le L \le R \le 1\,000\,000~.

Output Specification

The output is ~N+1~ lines, where each line ~i~ ~(0 \le i \le N)~ contains the integer number of positions in which Grundy can stand and be in view of at most ~i~ of his friends.

Sample Input

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

Sample Output

5
12
15
15

Explanation of Output for Sample Input

There are three friends with the following triangular wedges of vision, along with the possible positions that Grundy can be placed, as shown in the diagram below:

Notice the points ~(2, 3)~ and ~(4, 3)~ are visible only by the friend at position 0, since they lie on the boundary of the triangular wedge of vision for the friend at position 3.