Suppose there is a X x Y x Z 3D matrix A of numbers having coordinates (i, j, k) where 0 ≤ i < X, 0 ≤ j < Y, 0 ≤ k < Z. Now another X x Y x Z matrix B is defined from A such that the (i, j, k) element of B is the sum of all the the numbers in A in the cuboid defined by the (0, 0, 0) and (i, j, k) elements as the diagonally opposite vertices. In other word (i, j, k) in B is the sum of numbers of A having coordinates (a, b, c) such that 0 ≤ a ≤ i, 0 ≤ b ≤ j, 0 ≤ c ≤ k. The problem is that given B, you have to find out A.

------ Input ------ 

The first line of input will contain the number of test cases ( ≤ 10). That many test cases will follow in subsequent lines. The first line of each test case will contain the numbers X Y Z (0 ≤ X, Y, Z ≤ 100). After that there will be X x Y lines each containing Z numbers of B. The first line contains the numbers (0, 0, 0), (0, 0, 1)..., (0, 0, Z-1). The second line has the numbers (0, 1, 0), (0, 1, 1)..., (0, 1, Z-1) and so on. The (Y+1)^{th} line will have the numbers (1, 0, 0), (1, 0, 1)..., (1, 0, Z-1) and so on.

------ Output ------ 

For each test case print the numbers of A in exactly the same fashion as the input.

----- Sample Input 1 ------ 
2
3 1 1
1 
8 
22 
1 2 3
0 9 13 
18 45 51
----- Sample Output 1 ------ 
1 
7 
14 
0 9 4 
18 18 2

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Data structures

Mathematics

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
for i in range(int(input())):
	(x, y, z) = input().split()
	(x, y, z) = (int(x), int(y), int(z))
	l = [[0 for i in range(z)] for j in range(x * y)]
	l1 = []
	for i in range(x * y):
		l1.append(list(map(int, input().split())))
	for i in range(x):
		for j in range(y):
			for k in range(z):
				if i == 0 and j == 0 and (k == 0):
					l[i * y + j][k] = l1[i * y + j][k]
				elif i == 0 and j == 0:
					l[i * y + j][k] = l1[i * y + j][k] - l1[i * y + j][k - 1]
				elif i == 0 and k == 0:
					l[i * y + j][k] = l1[i * y + j][k] - l1[i * y + (j - 1)][k]
				elif j == 0 and k == 0:
					l[i * y + j][k] = l1[i * y + j][k] - l1[(i - 1) * y + j][k]
				elif i == 0:
					l[i * y + j][k] = l1[i * y + j][k] - l1[i * y + (j - 1)][k] - l1[i * y + j][k - 1] + l1[i * y + (j - 1)][k - 1]
				elif j == 0:
					l[i * y + j][k] = l1[i * y + j][k] - l1[(i - 1) * y + j][k] - l1[i * y + j][k - 1] + l1[(i - 1) * y + j][k - 1]
				elif k == 0:
					l[i * y + j][k] = l1[i * y + j][k] - l1[(i - 1) * y + j][k] - l1[i * y + (j - 1)][k] + l1[(i - 1) * y + (j - 1)][k]
				else:
					l[i * y + j][k] = l1[i * y + j][k] - l1[(i - 1) * y + j][k] - l1[i * y + (j - 1)][k] - l1[i * y + j][k - 1] + l1[(i - 1) * y + (j - 1)][k] + l1[(i - 1) * y + j][k - 1] + l1[i * y + (j - 1)][k - 1] - l1[(i - 1) * y + (j - 1)][k - 1]
	for i in l:
		for j in i:
			print(j, '', end='')
		print()


import copy
for _ in range(int(input())):
	(x, y, z) = map(int, input().split())
	a = []
	for i in range(x):
		t1 = []
		for j in range(y):
			t2 = list(map(int, input().split()))
			t1.append(t2)
		a.append(t1)
	d = copy.deepcopy(a)

	def solve(p, q, r):
		ans = 0
		if p > 0:
			if q > 0:
				if r > 0:
					ans -= d[p - 1][q - 1][r - 1]
					ans += d[p - 1][q - 1][r]
					ans += d[p - 1][q][r - 1]
					ans -= d[p - 1][q][r]
					ans += d[p][q - 1][r - 1]
					ans -= d[p][q - 1][r]
					ans -= d[p][q][r - 1]
					ans += d[p][q][r]
				if r <= 0:
					ans += d[p - 1][q - 1][r]
					ans -= d[p - 1][q][r]
					ans -= d[p][q - 1][r]
					ans += d[p][q][r]
			if q <= 0:
				if r > 0:
					ans += d[p - 1][q][r - 1]
					ans -= d[p - 1][q][r]
					ans -= d[p][q][r - 1]
					ans += d[p][q][r]
				if r <= 0:
					ans -= d[p - 1][q][r]
					ans += d[p][q][r]
		if p <= 0:
			if q > 0:
				if r > 0:
					ans += d[p][q - 1][r - 1]
					ans -= d[p][q - 1][r]
					ans -= d[p][q][r - 1]
					ans += d[p][q][r]
				if r <= 0:
					ans -= d[p][q - 1][r]
					ans += d[p][q][r]
			if q <= 0:
				if r > 0:
					ans -= d[p][q][r - 1]
					ans += d[p][q][r]
				if r <= 0:
					ans += d[p][q][r]
		return ans
	for i in range(x):
		for j in range(y):
			for k in range(z):
				a[i][j][k] = solve(i, j, k)
	for i in range(x):
		for j in range(y):
			for k in range(z):
				print(a[i][j][k], end=' ')
			print('')


def solve():
	for i in range(1, X + 1):
		for j in range(1, Y + 1):
			for k in range(1, Z + 1):
				print(A[i][j][k] - A[i - 1][j][k] - A[i][j - 1][k] - A[i][j][k - 1] + A[i - 1][j - 1][k] + A[i - 1][j][k - 1] + A[i][j - 1][k - 1] - A[i - 1][j - 1][k - 1], end=' ')
			print()
t = int(input())
for _ in range(t):
	(X, Y, Z) = list(map(int, input().split()))
	A = [[[0 for k in range(Z + 1)] for j in range(Y + 1)] for i in range(X + 1)]
	for i in range(1, X + 1):
		for j in range(1, Y + 1):
			temp = list(map(int, input().split()))
			for k in range(1, Z + 1):
				A[i][j][k] = temp[k - 1]
	solve()


T = int(input())
for _ in range(T):
	(x, y, z) = list(map(int, input().split()))
	B = [[] for r in range(x)]
	for k in range(0, x * y):
		temp = list(map(int, input().split()))
		row = k // y
		B[row].append(temp)
	for i in range(x - 1, 0, -1):
		for j in range(y):
			for k in range(z):
				B[i][j][k] -= B[i - 1][j][k]
	for i in range(x):
		for j in range(y - 1, 0, -1):
			for k in range(z):
				B[i][j][k] -= B[i][j - 1][k]
	for i in range(x):
		for j in range(y):
			for k in range(z - 1, 0, -1):
				B[i][j][k] -= B[i][j][k - 1]
	for i in range(x):
		for j in range(y):
			print(' '.join(list(map(str, B[i][j]))))


def fun(b, x, y, z):
	a = [[0] * z for i in range(x * y)]
	for i in range(x * y):
		if i % y == 0:
			for j in range(z):
				a[i][j] = f(i, j) + f(i - y, j - 1) - f(i, j - 1) - f(i - y, j)
		else:
			for j in range(z):
				a[i][j] = f(i, j) + f(i - 1, j - 1) + f(i - y, j - 1) + f(i - y - 1, j) - f(i, j - 1) - f(i - 1, j) - f(i - y, j) - f(i - y - 1, j - 1)
	return a

def f(i, j):
	if i >= 0 and j >= 0:
		return b[i][j]
	else:
		return 0
t = int(input())
for i in range(t):
	(x, y, z) = list(map(int, input().split()))
	b = [[0] * z for i in range(x * y)]
	for i in range(x * y):
		t = list(map(int, input().split()))
		b[i] = t[:]
	a = fun(b, x, y, z)
	for i in range(x * y):
		for j in range(z):
			print(a[i][j], end=' ')
		print()


for _ in range(int(input())):
	(i, j, k) = tuple(map(int, input().split()))
	m = [[[0 for z in range(k + 1)] for y in range(j + 1)]]
	for x in range(i):
		semi_matrix = [[0 for z in range(k + 1)]]
		for y in range(j):
			semi_matrix.append(list(map(int, ['0'] + input().split())))
		m.append(semi_matrix)
	for x in range(1, i + 1):
		for y in range(1, j + 1):
			for z in range(1, k + 1):
				print(m[x][y][z] - m[x][y][z - 1] - m[x - 1][y][z] - m[x][y - 1][z] + m[x - 1][y - 1][z] + m[x - 1][y][z - 1] + m[x][y - 1][z - 1] - m[x - 1][y - 1][z - 1], end=' ')
			print()


import math

def Solve():
	(x, y, z) = [int(x) for x in input().split()]
	arr = [[] for _ in range(x)]
	for idx in range(x * y):
		temp = [int(x) for x in input().split()]
		row = math.floor(idx / y)
		arr[row].append(temp)
	for i in range(x - 1, 0, -1):
		for j in range(y):
			for k in range(z):
				arr[i][j][k] -= arr[i - 1][j][k]
	for i in range(x):
		for j in range(y - 1, 0, -1):
			for k in range(z):
				arr[i][j][k] -= arr[i][j - 1][k]
	for i in range(x):
		for j in range(y):
			for k in range(z - 1, 0, -1):
				arr[i][j][k] -= arr[i][j][k - 1]
	for i in range(x):
		for j in range(y):
			print(' '.join([str(t) for t in arr[i][j]]))
test_cases = int(input())
while test_cases:
	test_cases -= 1
	Solve()


def b(B, i, j, k):
	if i >= 0 and j >= 0 and (k >= 0):
		return B[i][j][k]
	else:
		return 0
for t in range(int(input())):
	(X, Y, Z) = map(int, input().split())
	B = [[0 for j in range(Y)] for i in range(X)]
	for i in range(X):
		for j in range(Y):
			B[i][j] = list(map(int, input().split()))
	A = [[[0 for k in range(Z)] for j in range(Y)] for i in range(X)]
	for i in range(X):
		for j in range(Y):
			for k in range(Z):
				A[i][j][k] = b(B, i, j, k) - b(B, i - 1, j, k) - b(B, i, j - 1, k) - b(B, i, j, k - 1) + b(B, i - 1, j - 1, k) + b(B, i - 1, j, k - 1) + b(B, i, j - 1, k - 1) - b(B, i - 1, j - 1, k - 1)
	for i in range(X):
		for j in range(Y):
			print(*A[i][j])


t = int(input())
for _ in range(t):
	(x, y, z) = list(map(int, input().split()))
	a = [[0] * z for _ in range(y)]
	for i in range(x):
		b = [0] * z
		for j in range(y):
			l = list(map(int, input().split()))
			print(l[0] - b[0] - a[j][0], end=' ')
			s = l[0] - b[0] - a[j][0]
			b[0] += s
			for k in range(1, z):
				e = l[k] - b[k] - a[j][k] - s
				print(e, end=' ')
				s += e
				b[k] += s
			print()
			a[j] = l


def check(B, i, j, k):
	if i >= 0 and j >= 0 and (k >= 0):
		return B[i][j][k]
	return 0
for _ in range(int(input())):
	(x, y, z) = map(int, input().split())
	B = [[[] for i in range(y)] for j in range(x)]
	for i in range(x):
		for j in range(y):
			B[i][j] = list(map(int, input().split()))
	A = [[[0 for i in range(z)] for j in range(y)] for k in range(x)]
	for i in range(x):
		for j in range(y):
			for k in range(z):
				A[i][j][k] = check(B, i, j, k) - check(B, i - 1, j, k) - check(B, i, j - 1, k) - check(B, i, j, k - 1) + check(B, i - 1, j - 1, k) + check(B, i, j - 1, k - 1) + check(B, i - 1, j, k - 1) - check(B, i - 1, j - 1, k - 1)
	for i in range(x):
		for j in range(y):
			print(*A[i][j])