Sculpture

Interview

Time limit2sMemory limit512 MB

Summary

Given a grid of distinct neighboring heights, mark each interior cell with 1 if all four adjacent cells are higher, otherwise 0.

Level: Easy2 of 10
Topics: Array, Implementation, Matrix
Solved: No attempts yet

Problem

A modern artist has created a large outdoor sculpture. It consists of a rectangular grid, where each cell of the grid is raised to a different height. Because the sculpture is to be placed outdoors, the artist is worried about rainwater pooling in the lower cells. He needs to figure out which cells need to have drains installed. A cell needs a drain if the four cells above, below, left, and right are all higher. A cell on the edge or corner of the grid never needs a drain.

Input

Each input consists of a single test case. Your program may be run multiple times on different inputs.

Each test case begins with a line with two space-separated integers r and c (1 ≤ r,c ≤ 100), which are the dimensions of the artist's grid.

Each of the next r rows contains c space-separated integers h (0 ≤ h ≤ 1,000), which are the heights of the cells in inches. Every cell's height is different from those immediately above, below, to the left, and to the right.

Output

Output r lines with c space-separated integers each. Output a 1 if that cell needs a drain, 0 if it doesn't.

Examples1

Example 1

Input

7 10
4 5 6 5 7 8 9 3 2 4
9 1 3 4 6 2 0 5 6 1
7 8 1 3 8 7 5 4 3 2
9 3 4 2 7 6 8 2 8 7
8 5 3 6 4 0 7 9 6 3
3 8 4 8 3 7 4 2 5 7
9 3 0 4 5 6 7 8 4 3

Expected output

0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0 0 0
0 1 0 1 0 0 0 1 0 0
0 0 1 0 0 1 0 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0