favorite We need a little bit of your help to keep things running, click on this banner to learn more

2015 German Collegiate Programming Contest (GCPC)

Milling machines

A fab lab is an open, small-scale workshop where you can create or fabricate almost anything you want mostly by using computer controlled tools like a laser cutter or a 3D printer. The FAU fab lab recently got a CNC milling machine. Using the milling machine you can cut or remove material with different tools from the surface of a workpiece. It is controlled via a computer program.

I sometimes wondered what happens if multiple different shaped workpieces are sent through the same milling program. For simplification assume that we have only two dimensional workpieces without holes. A milling program consists of multiple steps; each step describes where the milling machine has to remove material (using different tools) from the top of the surface.


The first line consists of two integers w and s (1w, s104), where w gives the number of workpieces and s the number of steps in the milling program. The next line consists of two integers x and y (1x, y100), where x gives the width and y gives the maximal possible height of workpieces.

Then follow w lines, each describing one workpiece. Each workpiece description consists of x non-negative integers specifying the surface height in that column.

Then follow s lines, each describing one milling step of the milling program. Each milling step description consists of x non-negative integers si (0siy ) specifying the amount of surface to cut off in each column (relative to the height of the milling area, i.e. y, not relative to the top of the workpiece). See Figure for details.


For each workpiece, output one line containing x integers specifying the remaining surface heights (in the same order as in the input).


Second workpiece in first sample: initial workpiece followed by milling in each column – the value in the milling program determines the vertical position of the cutter head.


Time limit 1 second
Memory limit 128 MiB
Input example #1
2 1
3 4
4 4 4
4 2 3
2 3 0
Output example #1
2 1 4
2 1 3
Input example #2
1 3
10 100
11 22 33 44 55 66 77 88 99 100
1 100 1 100 1 100 1 100 1 100
58 58 58 58 58 58 58 58 58 58
42 42 42 42 42 42 42 42 66 42
Output example #2
11 0 33 0 42 0 42 0 34 0
Source 2015 German Collegiate Programming Contest (GCPC), June 20, Problem I