Under construction

Still being built. Things may change

Edge Detection

Time limit1sMemory limit128 MB

Summary
Given an image as run-length encoded runs, set each output pixel to the largest absolute difference from its 8 neighbors, and emit the result as runs.
Level

Hard8 of 10

Topics
Simulation, Implementation, Intervals, Array
Solved
No attempts yet

Problem

A satellite-imaging company records and stores very large images using run-length encoding. Write a program that reads a compressed image, detects the edges in it (as described below), and outputs another compressed image of the detected edges.

A simple edge-detection algorithm sets each output pixel to the maximum absolute difference between that pixel and all of its surrounding pixels in the input image. Consider the input image below:

15151515100100100
100100100100100100100
1001001001001002525
1751752525252525
1751752525252525

Input image

858585858500
85858585857575
75757575757575
751501507575750
01501500000

Output image

The upper-left pixel of the output image is the maximum of ∣15−15∣|15-15|, ∣15−100∣|15-100|, and ∣15−100∣|15-100|, which is 8585.

The pixel in the 4th row, 2nd column is the maximum of ∣175−100∣|175-100|, ∣175−100∣|175-100|, ∣175−100∣|175-100|, ∣175−175∣|175-175|, ∣175−25∣|175-25|, ∣175−175∣|175-175|, ∣175−175∣|175-175|, and ∣175−25∣|175-25|, which is 150150.

Every image contains between 22 and 10910^9 pixels. Every image is encoded with run-length encoding (RLE): a sequence of pairs, each holding a pixel value (00-255255) and a run length (11-10910^9). An input image has at most 1,0001{,}000 such pairs. Consecutive pairs always have different pixel values. Every line of an image contains the same number of pixels.

Input

The input describes one or more images. Each image begins with the width, in pixels, of every image line, on its own line. This is followed by the RLE pairs, one pair (value length) per line. A line containing 0 0 marks the end of that image's data. A width of 0 indicates that there are no more images to process.

Output

For each image, in order, output its edge-detected result in the same format as an input image: the image width on its own line, then the RLE pairs (value length) one per line, and finally a line containing 0 0. The result may contain more than 1,0001{,}000 RLE pairs. Do not print a trailing width-0 line.

Hint

A brute-force solution that computes an output value for every individual pixel will likely exceed the time or memory limits.

Examples4

  1. Example 1

    Input
    7
15 4
100 15
25 2
175 2
25 5
175 2
25 5
0 0
10
35 500000000
200 500000000
0 0
3
255 1
10 1
255 2
10 1
255 2
10 1
255 1
0 0
0
    Expected output
    7
85 5
0 2
85 5
75 10
150 2
75 3
0 2
150 2
0 4
0 0
10
0 499999990
165 20
0 499999990
0 0
3
245 9
0 0

  2. Example 2

    Input
    3
50 6
0 0
0
    Expected output
    3
0 6
0 0

  3. Example 3

    Input
    2
10 1
20 1
30 1
40 1
0 0
0
    Expected output
    2
30 1
20 2
30 1
0 0

  4. Example 4

    Input
    4
1 6
9 6
0 0
0
    Expected output
    4
0 1
8 10
0 1
0 0