ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Junior Contest October'2001

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Branches

Time limit: 1.0 second
Memory limit: 64 MB
SKB Kontur has a lot of branches scattered all over the city. The company management decided to create a guide that will help clients to choose which of the branches they need. You are asked for help in this work.
The city is represented in the form of a grid of blocks. Each block is a square whose sides are streets and whose corners are cross-roads. We suppose that all branches are located exactly at cross-roads. The branches of SKB Kontur are of different types: service centers, warehouses, shops, training centers and so on.
Let's mark service centers with number 1, warehouses with number 2, shops with number 4, training centers with number 8 and so on. There are not more than 11 types of branches, and two branches of the same type cannot be located at the same cross-road. Each cross-road is assigned a number equal to the sum of numbers with which the branches located at this cross-road are marked. Crossroads at which there are no branches of SKB Kontur are assigned 0.
Problem illustration
Let the distance between two cross-roads be equal to the number of street segments which one has to go from the first cross-road to the second (see picture). For example, the distance from a corner of a block to the opposite corner of this block is 2. For each cross-road at which there are no branches of SKB Kontur you have to find the sum of the numbers corresponding to the types of the branches nearest to this cross-road. For example, suppose that there are no branches at a given cross-road and at distance 1 from it, there is a branch of type 16 at distance 2, there are also two branches of type 8 and one of type 4 at distance 2 in other directions and there are no more branches at distance 2 from this cross-road. Then we should output number 28=16+8+4 for this cross-road. We do not take into consideration branches that are at distances greater than 5 from a given cross-road. Thus, if a cross-road does not have branches of SKB Kontur that are located at distances less than 6 from it then we should output 0 for this cross-road.


The first line contains positive integers H and W not exceeding 150. They are numbers of "vertical" and "horizontal" streets, correspondingly. The next H lines contain W numbers each, the i-th number in the j-th line describing types of the branches located at the cross-road of the i-th "vertical" and the j-th "horizontal" street.


You should output H lines containing W numbers each, the i-th number in the j-th line being equal to the sum of the numbers corresponding to the types of the branches nearest to the corresponding cross-road if there are no branches at this cross-road and −1 otherwise.


5 5
0 0 2 0 2
0 0 0 0 0
0 0 0 0 0
0 0 0 5 0
1 0 0 4 0
2 2 -1 2 -1
3 2 2 7 2
1 7 7 5 7
1 5 5 -1 5
-1 1 4 -1 4
Problem Author: Leonid Volkov, Alexander Somov
Problem Source: USU Open Collegiate Programming Contest October'2001 Junior Session
To submit the solution for this problem go to the Problem set: 1121. Branches