题目描述

给定一个整数 (N) 表示二维数组的维度，接下来输入一个 \(N \times N\) 的整数矩阵。请你计算并输出这个矩阵的二维前缀和矩阵。

二维前缀和矩阵 (P) 定义为：
$ \ P[i][j] = \sum_{x=1}^{i} \sum_{y=1}^{j} A[x][y] \ $

其中 (A) 表示原始矩阵，且下标均从 1 开始。

输入格式

• 第一行输入一个整数 \(N\)（\(1 \le N \le 1000\)）。
• 接下来 (N) 行，每行包含 (N) 个整数，表示原始矩阵的元素。

输出格式

• 输出 (N) 行，每行 (N) 个整数，表示对应位置的二维前缀和，每两个数字之间用空格隔开。

样例

输入样例

3
1 2 3
4 5 6
7 8 9

输出样例

1 3 6
5 12 21
12 27 45

说明

• 第一行前缀和：
  (P[1][1] = 1)
  (P[1][2] = 1 + 2 = 3)
  (P[1][3] = 1 + 2 + 3 = 6)
• 第二行前缀和：
  (P[2][1] = 1 + 4 = 5)
  (P[2][2] = 1 + 2 + 4 + 5 = 12)
  (P[2][3] = 1 + 2 + 3 + 4 + 5 + 6 = 21)
• 第三行前缀和：
  (P[3][1] = 1 + 4 + 7 = 12)
  (P[3][2] = 1 + 2 + 4 + 5 + 7 + 8 = 27)
  (P[3][3] = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45)