Counting Positions within Fields of View

All discussion in this problem is on the 2D Cartesian coordinate system.

There are \(N\) persons. The \(i\)-th person is located at \((x_i,0)\) and has a field of view represented by an angle. This field of view is abstracted as an angle whose two boundary rays are not included. When these rays are extended to the horizontal line \(y = Y\), the visible region of person \(i\) is the open interval \((l_i, r_i)\).

You are allowed to stand at any point \((a,Y)\) with \(L \le a \le R\) (where \(a\) is an integer). For every \(i\) with \(0 \le i \le N\), determine the number of positions \(a\) such that you are contained in the field of view of at most \(i\) persons.

inputFormat

The first line contains four integers: \(N\), \(L\), \(R\), and \(Y\), where \(N\) is the number of persons, \([L, R]\) is the allowed range for your \(x\)-coordinate, and \(Y\) is the fixed \(y\)-coordinate where you stand.

Each of the next \(N\) lines contains three integers: \(x_i\), \(l_i\), and \(r_i\). Person \(i\) is located at \((x_i, 0)\) and his field of view on the line \(y = Y\) is the open interval \((l_i, r_i)\) (i.e. the endpoints are not included).

outputFormat

Output \(N+1\) integers separated by spaces. The \(i\)-th number (0-indexed) represents the number of positions \(a \in [L,R]\) where you are in the field of view of at most \(i\) persons.

sample

2 1 10 5
0 2 5
3 6 9

6 10 10