Bombardment

Time limit7sMemory limit1024 MB

Summary

Simulate the greedy strategy that repeatedly picks the integer center covering the most remaining points, taking the smallest center on ties, and print the centers in order.

Level: Medium7 of 10
Topics: Greedy, Sliding window, Sorting, Array
Solved: No attempts yet

Problem

The goal of the game Bombardment is to destroy a set of points by bombarding them. The theme is not decided yet, and the core mechanic is a bombardment.

The points lie on the real number line, and each point is given only by its $x$ -coordinate. A bombardment is centered at an integer $X$ and destroys every point in the interval $[X-R, X+R]$ .

Most testers use a greedy strategy. Each bombardment is chosen to destroy the largest number of points at that moment. Because of this, players sometimes use more bombardments than the minimum possible. Write a program that simulates this strategy.

The process is as follows. While points remain, choose the center $X$ of a bombardment that destroys the maximum number of remaining points. If several centers give the maximum, choose the smallest one.

Input

The first line contains two integers $N$ ( $1 \leq N \leq 5 \times 10^5$ ) and $R$ ( $1 \leq R \leq 10^8$ ). The next line contains $N$ integers, the $x$ -coordinates of the points, each in the range $[-10^8, 10^8]$ . Several points may share the same $x$ -coordinate. The difference between the maximum and minimum $x$ -coordinate is at most $40 \cdot R$ .

Output

On the first line, print the number of bombardments $B$ . On the second line, print the $x$ -coordinates of the $B$ bombardments in the order they were performed.

Examples4

Example 1
Input
```
7 1
1 2 3 3 4 4 5
```
Expected output
```
3
3 0 4
```
Example 2
Input
```
6 1
5 -2 5 0 1 2
```
Expected output
```
3
1 4 -3
```
Example 3
Input
```
6 2
5 -2 5 0 1 2
```
Expected output
```
2
0 3
```
Example 4
Input
```
6 3
5 -2 5 0 1 2
```
Expected output
```
2
2 -5
```