This page is still under construction.

Parts of this page are still being built. What you see may change.

Cyclic Marathon

Time limit3sMemory limit256 MB

Summary
Runners spaced around a circular track catch and eliminate the runner ahead, and the program prints the elimination order and the survivors.
Level

Medium7 of 10

Topics
Heap, Linked list, Simulation, Math
Solved
No attempts yet

Problem

A cyclic marathon takes place on a circular track of length LL. One point on the track is the start and finish line. NN runners stand on the track at distances DiD_i measured clockwise from that point and receive start numbers 11 through NN, starting with the runner closest to the line.

After the start signal, each runner moves clockwise at speed SiS_i. If a runner catches the runner directly ahead, the caught runner is eliminated.

The race continues until no further eliminations are possible. Every runner still on the track is a winner. Write a program that prints the elimination order.

Input

The first line contains positive integers NN and LL (N≤500 000N \leq 500\,000, L<5 000 000L < 5\,000\,000).

Each of the next NN lines describes one runner: starting position DiD_i and speed SiS_i. The positions satisfy 0≤D1<D2<⋯<DN<L0 \leq D_1 < D_2 < \cdots < D_N < L, and each speed is a real number with two decimal places, 0<Si≤50 < S_i \leq 5. Distances are in meters and speeds are in meters per second.

Output

Print one line per eliminated runner with that runner's start number. Each of these lines ends with a single trailing space.

The last line must be Winner(s): followed by one space and the start numbers of all winners in increasing order, separated by single spaces.

Examples3

  1. Example 1

    Input
    6 150
0 1.75
30 0.80
60 0.50
70 1.00
120 0.10
140 0.90
    Expected output
    2 
3 
5 
4 
6 
Winner(s): 1

  2. Example 2

    Input
    2 100
0 2.00
50 1.00
    Expected output
    2 
Winner(s): 1

  3. Example 3

    Input
    3 100
0 1.00
30 1.00
60 1.00
    Expected output
    Winner(s): 1 2 3