Median filter

A digital signal is a function that assigns an integer $u[k]$ to every integer $k$. To describe an endless signal with finitely many numbers, you give some values explicitly and compute the rest by linear interpolation.

The signal in the picture above can be described by the points $(-2, 3)$, $(0, 1)$, $(3, 7)$, $(5, 7)$. Only $u[-2] = 3$, $u[0] = 1$, $u[3] = 7$, $u[5] = 7$ are given explicitly, and every other value lies on the line through two neighbouring points.

• The values on $(-\infty, 0]$ come from the line through $(-2, 3)$ and $(0, 1)$.
• The values on $[0, 3]$ come from the line through $(0, 1)$ and $(3, 7)$.
• The values on $[3, \infty)$ come from the line through $(3, 7)$ and $(5, 7)$.

The same signal can be described by arbitrarily many points, as long as the lines through neighbouring points interpolate the signal exactly.

Median filters are common for removing noise from a signal. A median filter of width $2d + 1$ reads the signal $u[k]$ and outputs the signal $y[k] = \operatorname{median}\{u[k - i] : -d \le i \le d\}$. In other words, sort $u[k - d], u[k - d + 1], \ldots, u[k + d]$ and take the value in the middle of the sorted sequence.

Below, the pictures on the left show input signals and the pictures on the right show the output of a filter of width 5.

Write a program that computes the output of the median filter of width $2d + 1$ when the input signal is given by points.

The first line contains an integer $N$ ($2 \le N \le 50$), the number of points that describe the input signal.

Each of the next $N$ lines contains two integers, the coordinates of one point. Both coordinates are at most $10^9$ in absolute value. The points are given by increasing first coordinate, and two different points have different first coordinates. Every interpolated value is an integer.

The last line contains an integer $d$ ($0 \le d \le 50$), where $2d + 1$ is the width of the filter.

Describe the output signal $y$ by its corners. An integer $k$ is a corner of $y$ if $y[k + 1] - y[k] \ne y[k] - y[k - 1]$. The signal $y$ has finitely many corners.

If $y$ has at least one corner, let the corners be $k_1 < k_2 < \cdots < k_m$. Print $M = m + 2$ on the first line, then print the following $M$ points in this order, two integers per line.

$(k_1 - 1,\ y[k_1 - 1]),\ (k_1,\ y[k_1]),\ (k_2,\ y[k_2]),\ \ldots,\ (k_m,\ y[k_m]),\ (k_m + 1,\ y[k_m + 1])$

The slope of $y$ is constant on $(-\infty, k_1]$ and on $[k_m, \infty)$, so these points interpolate $y$ exactly.

If $y$ has no corner, then it is a single line. Print $2$ on the first line, then print the two points $(x_1, y[x_1])$ and $(x_1 + 1, y[x_1 + 1])$, where $x_1$ is the first coordinate of the first input point.

Every printed number fits in a signed 64-bit integer type.