미디언 필터

디지털 신호는 모든 정수 $k$에 정수 $u[k]$를 대응시키는 함수다. 끝없이 이어지는 신호를 유한개의 수로 나타내려고 몇 개의 값만 직접 지정하고, 나머지 값은 선형 보간으로 구한다.

위 그림의 신호는 점 $(-2, 3)$, $(0, 1)$, $(3, 7)$, $(5, 7)$로 나타낼 수 있다. 즉 $u[-2] = 3$, $u[0] = 1$, $u[3] = 7$, $u[5] = 7$만 직접 주어지고, 나머지 값은 이웃한 두 점을 지나는 직선 위에 있다.

• 구간 $(-\infty, 0]$의 값은 $(-2, 3)$과 $(0, 1)$을 지나는 직선에서 구한다.
• 구간 $[0, 3]$의 값은 $(0, 1)$과 $(3, 7)$을 지나는 직선에서 구한다.
• 구간 $[3, \infty)$의 값은 $(3, 7)$과 $(5, 7)$을 지나는 직선에서 구한다.

이웃한 점을 지나는 직선이 신호를 정확히 보간하기만 하면, 같은 신호를 원하는 만큼 많은 점으로 나타낼 수 있다.

신호의 잡음을 없앨 때는 미디언 필터를 자주 쓴다. 너비가 $2d + 1$인 미디언 필터는 신호 $u[k]$를 입력으로 받아 $y[k] = \operatorname{median}\{u[k - i] : -d \le i \le d\}$인 신호를 출력한다. 다시 말해 $u[k - d], u[k - d + 1], \ldots, u[k + d]$를 정렬한 뒤 가운데 값을 고른 것이 $y[k]$다.

아래에서 왼쪽 그림은 입력 신호, 오른쪽 그림은 너비가 5인 필터를 지난 출력 신호다.

입력 신호가 점으로 주어질 때 너비 $2d + 1$ 미디언 필터의 출력 신호를 구하는 프로그램을 작성하시오.

첫째 줄에 입력 신호를 나타내는 점의 개수 $N$ ($2 \le N \le 50$)이 주어진다.

다음 $N$개 줄에 점의 좌표를 나타내는 두 정수가 주어진다. 두 좌표의 절댓값은 모두 $10^9$ 이하다. 점은 첫째 좌표가 작은 것부터 주어지고, 서로 다른 두 점의 첫째 좌표는 다르다. 보간으로 얻는 값은 모두 정수다.

마지막 줄에 정수 $d$ ($0 \le d \le 50$)가 주어진다. 필터의 너비는 $2d + 1$이다.

출력 신호 $y$를 꺾인점으로 나타낸다. $y[k + 1] - y[k] \ne y[k] - y[k - 1]$인 정수 $k$를 $y$의 꺾인점이라고 한다. $y$의 꺾인점은 유한개다.

꺾인점이 하나 이상이면 이를 $k_1 < k_2 < \cdots < k_m$이라 하고, 첫째 줄에 $M = m + 2$를 출력한다. 이어서 다음 $M$개의 점을 이 순서대로 한 줄에 두 정수씩 출력한다.

$(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])$

$y$의 기울기는 $(-\infty, k_1]$과 $[k_m, \infty)$에서 각각 일정하므로 이 점들은 $y$를 정확히 보간한다.

꺾인점이 없으면 $y$는 하나의 직선이다. 이때 첫째 줄에 $2$를 출력하고, 다음 두 줄에 점 $(x_1, y[x_1])$과 $(x_1 + 1, y[x_1 + 1])$을 출력한다. 여기서 $x_1$은 입력의 첫 점의 첫째 좌표다.

출력하는 수는 모두 부호 있는 64비트 정수 범위에 들어간다.