Avoiding the Cow Photography Lines

Farmer John’s farm is filled with lush vegetation, and every cow wants a picture of the natural scenery. Unfortunately, Bessie must travel from her starting position to her destination without disturbing any ongoing photography sessions.

Bessie starts at \((X,0)\) on the \(xy\)-plane and wants to reach \((0,Y)\) (with \(1\le X,Y\le 10^6\)). Meanwhile, \(N\) other cows (\(1 \le N \le 3\cdot10^5\)) have scheduled photography sessions. Specifically, the \(i\)th cow positions herself at \((x_i,0)\) with her photographer at \((0,y_i)\) (with \(1\le x_i,y_i\le 10^6\)) and will begin her session at time \(s_i\) (\(1\le s_i < T\)). The parameter \(T\) satisfies \(1\le T\le N+1\). Each photography session, once started, lasts indefinitely (it takes a long time to get the perfect shot!).

Bessie knows the schedule of every session. If she departs at an integer time \(t\) (with \(0\le t\le T-1\)), she will avoid all photography pairs that have started by that time (i.e. all sessions with \(s_i \le t\)). She chooses a path from \((X,0)\) to \((0,Y)\) consisting of one or more line segments that has the smallest possible Euclidean length while not crossing the line of sight (the straight line segment) between any photographer and her corresponding cow that is active.

It turns out that the direct straight line from \((X,0)\) to \((0,Y)\) is safe if and only if it does not intersect any active photography line. One may prove that for a photography session given by endpoints \((x_i,0)\) and \((0,y_i)\), the direct line is blocked if and only if \[ X\cdot y_i < Y\cdot x_i. \] In that case Bessie must take a detour. A valid detour is to follow the boundary of the farm by going through \((0,0)\), which yields a total distance of \(X+Y\). (It can be shown that if the direct line is blocked then \(X+Y\) is the shortest distance Bessie can achieve.)

Your task is: for every departure time \(t\) from \(0\) to \(T-1\), compute \(\lfloor d_t \rfloor\) where \(d_t\) is the length of the shortest path Bessie can take when avoiding all photography sessions that have started (i.e. all sessions with \(s_i\le t\)). In summary:

• If no active photography session blocks the direct line (i.e. for all active sessions, \(X\cdot y_i \ge Y\cdot x_i\)), then \(d_t=\sqrt{X^2+Y^2}\).
• If at least one active session blocks the direct line (i.e. there exists an active session with \(X\cdot y_i < Y\cdot x_i\)), then \(d_t=X+Y\).

Output \(\lfloor d_t \rfloor\) (the floor of \(d_t\)) for each time \(t\) (from \(0\) to \(T-1\)), one per line.

inputFormat

The first line contains four integers: \(X\), \(Y\), \(N\) and \(T\) (as described above).

Then \(N\) lines follow. The \(i\)th of these contains three integers \(x_i\), \(y_i\), and \(s_i\) representing the \(i\)th photography session.

outputFormat

Output \(T\) lines. The \(t\)th line (starting from \(t=0\)) should contain \(\lfloor d_t \rfloor\), the floor of the minimum distance Bessie can travel when departing at time \(t\).

sample

5 5 1 2
3 0 1

7
10