Under construction

Still being built. Things may change

Restore the Array

Interview

Time limit2sMemory limit512 MB

Summary
Recover grid A from grid B, where B is built by overlapping A with A shifted down X and right Y so overlapping cells are summed.
Level

Medium5 of 10

Topics
Matrix, Simulation, Implementation, Dynamic programming
Solved
No attempts yet

Problem

Given an array AA of size H×WH \times W and two integers XX and YY, an array BB of size (H+X)×(W+Y)(H + X) \times (W + Y) can be made by overlapping the array AA with the array AA shifted down by XX cells and right by YY cells. Where numbers overlap, they are added together.

That is, the value at (i,j)(i, j) of array BB is one of the following three.

  • If (i,j)(i, j) lies in neither array, Bi,j=0B_{i,j} = 0.
  • If (i,j)(i, j) lies in both arrays, Bi,j=Ai,j+Ai−X,j−YB_{i,j} = A_{i,j} + A_{i-X,j-Y}.
  • If (i,j)(i, j) lies in exactly one of the arrays, Bi,j=Ai,jB_{i,j} = A_{i,j} or Ai−X,j−YA_{i-X,j-Y}.

Given the array BB and the integers XX and YY, find the array AA.

Input

The first line contains four integers HH, WW, XX, YY. The next H+XH + X lines give the elements of array BB.

The input is always given such that array AA exists.

Output

Print the elements of array AA over HH lines.

Constraints

  • 2≤H,W≤3002 \le H, W \le 300
  • 1≤X<H1 \le X < H
  • 1≤Y<W1 \le Y < W
  • 0≤Bi,j≤1,0000 \le B_{i,j} \le 1,000

Examples2

  1. Example 1

    Input
    2 4 1 1
1 2 3 4 0
5 7 9 11 4
0 5 6 7 8
    Expected output
    1 2 3 4
5 6 7 8

  2. Example 2

    Input
    3 3 2 1
1 2 3 0
4 5 6 0
7 9 11 3
0 4 5 6
0 7 8 9
    Expected output
    1 2 3
4 5 6
7 8 9