Gadgets Factory#2264
Mr. Smith is a very rich gadgets fan. Once he realized that he cannot buy all the gadgets he wants just because they are not yet produced, he decided to build his own Gadgets Factory.
The Gadgets Factory will be built at a place called "Silicon Road". This road concentrates the production of high-tech parts required to produce gadgets. The Silicon Road is straight, and the factories are placed very close to it, so the road can be considered as an axis, and factories can be considered as points on it.
There are parts needed to produce gadgets, and factories that produce these parts. Mr. Smith wants to minimize the sum of squared distances to the nearest factories that produce each of the required parts. Help him to find all the points at which that sum is minimal.
The first line of the input file contains the integer numbers and (1 \leq n \leq 10000; n \leq m \leq 100000).
Each of the next lines contains a pair of integers x_i and p_i, where x_i is the coordinate of the -th factory, and p_i is the identifier of the part that it produces (|x_i| \leq 100000; x_i \leq x_{i+1}; 1 \leq p_i \leq n).
For every required part, there is at least one factory that produces it.
The first line of the output file should contain the integer — the number of points where the Gadgets Factory can be built.
Each of the next lines should contain these points in ascending order. The values should be accurate to within an absolute error of 10^{-6}.
Example 1