3535번 - Gadgets Factory 스페셜 저지다국어

Mr. Smith is a very rich gadgets fan. As soon as 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 production of highly technological 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 n parts needed to produce gadgets, and m factories that produce these parts. Mr. Smith wants to minimize the sum of squared distances to the nearest factories that produce each of required parts. Help him to find all the points in which that sum is minimal.

The first line of the input file contains integer numbers n and m (1 ≤ n ≤ 10 000; n ≤ m ≤ 100 000).

Next m lines contain pairs of integer numbers x_i and p_i, x_i is the coordinate of i-th factory, and p_i is the identifier of the part that it produces (|x_i| ≤ 100 000; x_i ≤ x_i+1; 1 ≤ p_i ≤ n).

For each required part there is at least one factory that produces it.

The first line of the output file should contain an integer number k — the number of points where the Gadgets Factory can be built.

Next k lines should contain these points in ascending order. The values should be accurate within an absolute error of 10⁻⁶.