## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Ants on a Stick Solution Round C 2022 - Kick Start 2022

### Problem

Ada has $N$ ants labelled from $1$ to $N$. She decides to test John's concentration skills. She takes a stick $L$ cm long, and drops the ants on it.

The positions on the stick at which the ants are dropped are represented by an integer array $P$, where ant $i$ is dropped at the position ${\mathbf{P}}_{\mathbf{i}}$ (that is, ${\mathbf{P}}_{\mathbf{i}}$ cm away from the left end) on the stick. Each ant travels either to the left or right with a constant speed of $1$ cm per second. The initial directions of the ants is represented by an array $D$, where the direction of ant $i$ is ${\mathbf{D}}_{\mathbf{i}}$$0$ if left, and $1$ if right. When two ants meet, they bounce off each other and reverse their directions. The ants fall off the stick when they reach either end of it.

Ada challenges John to find the exact order in which the ants fall off the stick. John needs your help!

### Input

The first line of the input gives the number of test cases, $T$$T$ test cases follow.

The first line of each test case contains two integers, $N$ and $L$: the number of ants, and the length of the stick, respectively.
The next $N$ lines describe the positions and directions of the ants. The $i$-th line contains two integers, ${\mathbf{P}}_{\mathbf{i}}$ and ${\mathbf{D}}_{\mathbf{i}}$: the position and direction of ant $i$, respectively.

### Output

For each test case, output one line containing Case #x$x$: A1A2…AN${A}_{1}{A}_{2}\dots {A}_{N}$, where $x$ is the test case number (starting from 1), and ${A}_{i}$ is the label of the $i$-th ant that falls off the stick. In other words, the first ant to fall off the stick is the ant labelled ${A}_{1}$, the second is the ant labelled ${A}_{2}$, and so on.

If multiple ants fall off at the same time, output their labels in the increasing order.

### Limits

Memory limit: 1 GB.
$1\le \mathbf{T}\le 100$.
$\mathbf{N}<\mathbf{L}$.
${\mathbf{D}}_{\mathbf{i}}\in \left\{0,1\right\}$, for all $i$.
$0<{\mathbf{P}}_{\mathbf{i}}<\mathbf{L}$, for all $i$.
All ${\mathbf{P}}_{\mathbf{i}}$ are distinct.

#### Test Set 1

Time limit: 20 seconds.
$1\le \mathbf{N}\le 10$.
$1\le \mathbf{L}\le 100$.

#### Test Set 2

Time limit: 40 seconds.
$1\le \mathbf{N}\le {10}^{3}$.
$1\le \mathbf{L}\le {10}^{9}$.

#### Test Set 3

Time limit: 40 seconds.
$1\le \mathbf{L}\le {10}^{9}$.
For at most 15 cases:
$1\le \mathbf{N}\le {10}^{5}$.
For the remaining cases:
$1\le \mathbf{N}\le {10}^{3}$.