경계선 검출

어느 위성 영상 회사는 매우 큰 이미지를 런 렝스 부호화(RLE)로 기록하고 저장한다. 압축된 이미지를 읽어 아래에 설명하는 방식으로 경계선을 검출한 뒤, 검출된 경계선 이미지를 다시 압축하여 출력하는 프로그램을 작성하라.

간단한 경계선 검출 알고리즘은 각 출력 픽셀의 값을, 입력 이미지에서 그 픽셀과 이웃한 모든 픽셀들과의 차이의 절댓값 중 최댓값으로 정한다. 아래 입력 이미지를 살펴보자.

입력 이미지

출력 이미지

출력 이미지의 왼쪽 위 픽셀은 $|15-15|$, $|15-100|$, $|15-100|$ 중 최댓값이므로 $85$이다.

4번째 행, 2번째 열의 픽셀은 $|175-100|$, $|175-100|$, $|175-100|$, $|175-175|$, $|175-25|$, $|175-175|$, $|175-175|$, $|175-25|$ 중 최댓값이므로 $150$이다.

모든 이미지는 $2$개 이상 $10^9$개 이하의 픽셀을 가진다. 모든 이미지는 런 렝스 부호화(RLE)로 인코딩되며, 이는 픽셀 값($0$-$255$)과 반복 길이($1$-$10^9$)로 이루어진 쌍들의 나열이다. 하나의 입력 이미지는 최대 $1{,}000$개의 쌍으로 이루어진다. 서로 이웃한 쌍은 항상 픽셀 값이 다르다. 이미지의 모든 행은 같은 수의 픽셀을 가진다.

입력은 하나 이상의 이미지 정보로 이루어진다. 각 이미지는 한 행에 들어가는 픽셀 수, 즉 너비가 한 줄에 먼저 주어진다. 그 뒤로 RLE 쌍들이 한 줄에 하나씩 (값 반복길이) 주어진다. 0 0으로 이루어진 줄은 해당 이미지 데이터의 끝을 나타낸다. 너비가 0인 줄은 더 이상 처리할 이미지가 없음을 뜻한다.

각 이미지에 대해, 주어진 순서대로 경계선 검출 결과를 입력 이미지와 같은 형식으로 출력한다. 먼저 이미지 너비를 한 줄에 출력하고, 이어서 RLE 쌍들을 (값 반복길이) 한 줄에 하나씩 출력한 뒤, 마지막에 0 0 줄을 출력한다. 결과에는 $1{,}000$개를 넘는 RLE 쌍이 포함될 수 있다. 맨 끝에 너비가 0인 줄은 출력하지 않는다.

모든 픽셀 각각에 대해 출력 값을 계산하는 완전 탐색 방식은 시간 또는 메모리 제한을 초과할 가능성이 높다.