Gadgets Factory

Mr. Smith is a very wealthy gadget enthusiast. When he realized that he cannot buy the gadgets he wants simply because they have not been produced yet, he decided to build his own gadget factory.

The factory will stand on a street called Silicon Road, which is lined with plants that manufacture the high-tech parts gadgets are made of. Silicon Road is perfectly straight and the plants sit right next to it, so we model the road as a number line and each plant as a point on it. We call each such plant a factory.

Producing a gadget requires $n$ different parts, and there are $m$ factories along the road, each producing exactly one kind of part. If Mr. Smith builds his gadget factory at coordinate $t$, its cost is the sum, over all $n$ required parts, of the squared distance from $t$ to the nearest factory that produces that part.

Find every coordinate $t$ at which this cost is minimized.

The first line contains two integers $n$ and $m$ ($1 \le n \le 10000$; $n \le m \le 100000$).

Each of the next $m$ lines contains two integers $x_i$ and $p_i$: the coordinate of the $i$-th factory and the identifier of the part it produces ($|x_i| \le 100000$; $x_i \le x_{i+1}$; $1 \le p_i \le n$).

Every required part is produced by at least one factory.

Let $f(t)$ be the sum, over all $n$ parts, of the squared distance from $t$ to the nearest factory producing that part. Every point at which $f$ attains its minimum is a rational number whose denominator divides $n$.

On the first line print $k$, the number of points at which $f(t)$ is minimal. Then print those $k$ points in ascending order, one per line, each written exactly as a fraction p/q in lowest terms with $q > 0$, or as the integer p when $q = 1$.