提示: 欢迎访问OurACM平台。
Problem 1460 Density MapII

Accept: 24    Submit: 126
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

There are given:

1. an integer n>0;

2. F-the table n*n with the numbers from the set {0,1} and G-the table n*n with the numbers from the set {0,1...n-1,n}; Columns and lines of the tables are numbered from 1 to n; The number in i-th column and j-th line of the each table is denoted by F[i,j] and G[i,j] respectively. If [i, j] and [i', j'] are two positions in the table F, the distance between them is sum(|i - i'|, |j - j'|).

Task

The table W, n*n, should be computed, where W[i, j] (the number in i-th column and j-th line of the table W) is equal to the sum of all the numbers F[x,y], such that the distance between [x,y] and [i,j] is not greater than G[i,j].

Input

There several test cases. In the first line of each case there are one positive integer n, where 0 < n <=200. In the following 2*n lines the table F and G are described. Each of these lines contains n integers, separated by single spaces.

Output

Output of each case should contain exactly n lines. In the j-th line the values W[1, j]...W[n, j] should be written respectively; they should be separated by single spaces.Output a blank line after each case.

Sample Input

2 1 1 1 1 1 1 1 1

Sample Output

3 3 3 3

Source

FZU 2006 ICPC Qualification Round I

Submit  Back  Status  Discuss