문제

ALOHA의 봄 대회 벚꽃컵이 끝나고, 바닥에 꾸며진 벚꽃잎을 치워야 할 때가 되었다. 바닥은 크기의 정사각형 배열로 표현할 수 있다.

벚꽃잎을 치우기 위해, 성준이는 다음 그림과 같이 각 개의 오른쪽 아래(↘) 방향으로 진행하는 각 대각선마다 바닥에 꾸며진 벚꽃잎 개수의 합을 구하려고 한다. 즉, 바닥의 맨 왼쪽 위 칸의 좌표가 이라고 할 때, 에서 좌표애 해당하는 칸과 좌표에 해당하는 칸이 같은 대각선에 속한다.

바닥의 각 칸마다 꾸며진 벚꽃잎의 개수가 주어질 때, 각 대각선마다 벚꽃잎 개수의 합을 구하시오.

예제 1의 설명 그림이다.

입력

첫째 줄에 이 주어진다.

다음 개의 줄에 배열 가 주어진다.

입력되는 모든 수는 정수이다.

출력

오른쪽 위에 가까운 대각선부터 순서대로 각 대각선의 합을 출력한다. 위에 설명한 그림에서는 빨간색 대각선부터 보라색 대각선 순서이다.