Falling Cards

Time limit1sMemory limit128 MB

Summary

Simulate a row of non-intersecting standing cards: when a card falls it sweeps a rectangle of height H, knocking over any card it touches, and each touched card topples away from the pusher.

Level: Medium6 of 10
Topics: Geometry, Simulation, BFS
Solved: No attempts yet

Problem

Standing a playing card on its edge is hard, but someone patiently stood $N$ cards on a desk, each resting on its shorter edge. Seen from above, each card is a line segment on the desk; card $i$ runs from $(x_i, y_i)$ to $(v_i, w_i)$ . Every card has the same height $H$ , 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 $H$ 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 $(x_1, y_1) \to (v_1, w_1)$ by $90^\circ$ counter-clockwise.

When a falling card $A$ touches a standing card $B$ , card $B$ 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 $A$ 's segment; that is, $B$ topples away from the card that pushed it.

The input never contains:

a card that falls exactly perpendicular to the card that pushed it, or
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 $N$ and the card height $H$ ( $1 \le N \le 100$ , $H > 0$ ; $H$ is a real number). Each of the next $N$ lines contains four real numbers $x_i\ y_i\ v_i\ w_i$ , separated by spaces — the endpoint coordinates of card $i$ 's segment.

Output

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

Examples5

Example 1

Input

3 100
10 10 50 40
10 0 50 30
20 90 20 20

Expected output

1 3

Example 2
Input
```
1 10
0 0 10 0
```
Expected output
```
1
```
Example 3
Input
```
2 10
0 0 10 0
2 5 8 5
```
Expected output
```
1 2
```
Example 4
Input
```
3 10
0 0 10 0
2 5 8 5
3 12 7 12
```
Expected output
```
1 2 3
```

Example 5

Input

Expected output

1 2 3 4 5 6