*Non-maximum suppression (NMS)* has been widely used in several aspects of computer vision and is an integral part of many object detection algorithms. One of the most common problems in object detection is that an object might be detected multiple times. NMS technique ensures we get only a single detection per object.
For each class, a list of bounding boxes is proposed by the algorithm. Each box is associated with a score, indicating the confidence the algorithm thinks there is an object of the given class inside the box. Now let's see how the NMS procedure works. In the beginning, all the boxes are unselected and non-suppressed.
In this problem, we assume there is only one class, and simplify the object detection algorithm by only proposing *square shaped* boxes of the *same size*. Given the IoU threshold and a list of congruent square boxes proposed by the algorithm, can you report all selected boxes after going through the NMS procedure?
The first line of the input gives the number of test cases, $T$ ($1 <= T <= 10$). $T$ test cases follow.
For each test case, the first line contains two integers $n$, $S$ ($1 <= n <= 10^5$, $1 <= S <= 10^7$) and a floating-point number $t h r e s h o l d$ ($0. 300 <= t h r e s h o l d <= 0. 700$), indicating the number of square bounding boxes proposed by the detection algorithm, the size of the squares, and the IoU threshold. The $t h r e s h o l d$ is exact and is given to the third digit after the decimal point.
In the next $n$ lines, each line contains two integers $x$, $y$ ($0 <= x < x + S <= 10^7$, $0 <= y < y + S <= 10^7$) — the coordinates of the bottom left corner of a square box, followed by a floating point number $s c o r e$ ($0. 0 <= s c o r e <= 1. 0$) — the score of this box. Scores are exact and have at most six digits after the decimal point. Also, scores are distinct.
For each test case, the output starts with a line containing "_Case #x: y_", where _x_ is the test case number (starting from 1), and _y_ is the number of selected bounding boxes after going through the NMS procedure. The next line contains _y_ integers indicating the indices of the boxes (starting from 1) in *ascending* order.
There are $3$ boxes in the example: $[ 0, 4 ] times [ 0, 4 ]$, $[ 1, 5 ] times [ 1, 5 ]$ and $[ 2, 6 ] times [ 2, 6 ]$, which are already in descending order of score. The second box is suppressed because the IoU of the first and the second box is $frac(9, 23)$, which is strictly larger than $0. 390$, the IoU threshold. The third box is selected because the IoU of the first and the third box is $frac(1, 7)$, which is smaller than the IoU threshold.
## Input
The first line of the input gives the number of test cases, $T$ ($1 <= T <= 10$). $T$ test cases follow.For each test case, the first line contains two integers $n$, $S$ ($1 <= n <= 10^5$, $1 <= S <= 10^7$) and a floating-point number $t h r e s h o l d$ ($0. 300 <= t h r e s h o l d <= 0. 700$), indicating the number of square bounding boxes proposed by the detection algorithm, the size of the squares, and the IoU threshold. The $t h r e s h o l d$ is exact and is given to the third digit after the decimal point.In the next $n$ lines, each line contains two integers $x$, $y$ ($0 <= x < x + S <= 10^7$, $0 <= y < y + S <= 10^7$) — the coordinates of the bottom left corner of a square box, followed by a floating point number $s c o r e$ ($0. 0 <= s c o r e <= 1. 0$) — the score of this box. Scores are exact and have at most six digits after the decimal point. Also, scores are distinct.
## Output
For each test case, the output starts with a line containing "_Case #x: y_", where _x_ is the test case number (starting from 1), and _y_ is the number of selected bounding boxes after going through the NMS procedure. The next line contains _y_ integers indicating the indices of the boxes (starting from 1) in *ascending* order.
[samples]
## Note
There are $3$ boxes in the example: $[ 0, 4 ] times [ 0, 4 ]$, $[ 1, 5 ] times [ 1, 5 ]$ and $[ 2, 6 ] times [ 2, 6 ]$, which are already in descending order of score. The second box is suppressed because the IoU of the first and the second box is $frac(9, 23)$, which is strictly larger than $0. 390$, the IoU threshold. The third box is selected because the IoU of the first and the third box is $frac(1, 7)$, which is smaller than the IoU threshold.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ n \in \mathbb{Z} $ be the number of square bounding boxes.
- Let $ S \in \mathbb{Z} $ be the side length of each square box.
- Let $ \theta \in \mathbb{R} $ be the IoU threshold, with $ 0.300 \leq \theta \leq 0.700 $.
- Let $ B_k = \{ (x_i, y_i, s_i) \mid i \in \{1, \dots, n\} \} $ be the set of boxes, where:
- $ (x_i, y_i) \in \mathbb{Z}^2 $ is the bottom-left corner of box $ i $,
- $ s_i \in \mathbb{R} $ is its distinct score, with $ 0.0 < s_i < 1.0 $.
Each box $ i $ corresponds to the square region $ [x_i, x_i + S] \times [y_i, y_i + S] $.
**Constraints**
1. $ 1 \leq T \leq 10 $
2. $ 1 \leq n \leq 10^5 $, $ 1 \leq S \leq 10^7 $
3. $ 0 \leq x_i < x_i + S < 10^7 $, $ 0 \leq y_i < y_i + S < 10^7 $
4. $ 0.300 \leq \theta \leq 0.700 $, with $ \theta $ given to 3 decimal places
5. All scores $ s_i $ are distinct and given with at most 6 decimal places
**Objective**
Apply Non-Maximum Suppression (NMS) as follows:
1. Sort boxes in descending order of score: $ s_{\sigma(1)} > s_{\sigma(2)} > \dots > s_{\sigma(n)} $, where $ \sigma $ is a permutation of $ \{1, \dots, n\} $.
2. Initialize an empty set $ \mathcal{S} $ of selected boxes.
3. For each box $ i $ in sorted order:
- If no box in $ \mathcal{S} $ has IoU $ \geq \theta $ with box $ i $, add $ i $ to $ \mathcal{S} $.
4. Output the indices (1-based) of boxes in $ \mathcal{S} $ in ascending order.
**IoU Definition**
For two axis-aligned squares $ i $ and $ j $:
$$
\text{IoU}(i, j) = \frac{\text{Area}(B_i \cap B_j)}{\text{Area}(B_i \cup B_j)} = \frac{\text{Area}(B_i \cap B_j)}{2S^2 - \text{Area}(B_i \cap B_j)}
$$
where $ \text{Area}(B_i \cap B_j) = \max(0, S - |x_i - x_j|) \cdot \max(0, S - |y_i - y_j|) $.