Falling Cards

No attempts yetTime limit1sMemory limit128 MB

Problem

Standing a playing card on its edge is hard, but someone patiently stood NN cards on a desk, each resting on its shorter edge. Seen from above, each card is a line segment on the desk; card ii runs from (xi,yi)(x_i, y_i) to (vi,wi)(v_i, w_i). Every card has the same height HH, and no two segments intersect.

The first card is pushed and falls flat. As a card falls flat, its rectangular face covers a region of the desk: the base segment stays fixed, and the card covers the rectangle obtained by extending that segment a distance HH in the falling direction (perpendicular to the segment). Any still-standing card whose segment is touched by this rectangle also falls.

The first card falls in the direction obtained by rotating the vector (x1,y1)(v1,w1)(x_1, y_1) \to (v_1, w_1) by 9090^\circ counter-clockwise.

When a falling card AA touches a standing card BB, card BB falls in whichever of the two directions perpendicular to its own segment makes the ray along its falling direction avoid crossing the line that contains card AA's segment; that is, BB topples away from the card that pushed it.

The input never contains:

  1. a card that falls exactly perpendicular to the card that pushed it, or
  2. a falling card that touches more than one still-standing card.

Determine which cards fall and which remain standing.

Input

The first line contains the number of cards NN and the card height HH (1N1001 \le N \le 100, H>0H > 0; HH is a real number). Each of the next NN lines contains four real numbers xi yi vi wix_i\ y_i\ v_i\ w_i, separated by spaces — the endpoint coordinates of card ii's segment.

Output

Print the numbers of the cards that fall, in increasing order, separated by spaces.