Chinese Version

Russian Version

Define a 3-D Matrix in which each block contains 0 initially. The first block is defined by the coordinates (1,1,1) and the last block is defined by the coordinates (n,n,n). There are two types of queries.

UPDATE x y z W

Update the value of block (x,y,z) to W.

QUERY x1 y1 z1 x2 y2 z2

Calculate the sum of the values of blocks whose x coordinate is between x1 and x2 (inclusive), y coordinate between y1 and y2 (inclusive) and z coordinate between z1 and z2 (inclusive). 

Function Description  

Complete the cubeSum function in the editor below.  

cubeSum has the following parameters:
- *int n: the dimensions of the 3-d matrix
- string operations[m]: the operations to perform  

Returns 

- int[]: the results of each QUERY operation  

Input Format 

The first line contains an integer $\mathbf{T}$, the number of test-cases. $\mathbf{T}$ testcases follow.  

For each test case, the first line contains two space-separated integers, $n$ and $m$. 
    $n$ defines the $n\times n\times n$ matrix. 

$m$ defines the number of operations. 

The next $m$ lines will contain an operation either of these forms:  

 1. UPDATE x y z W
 2. QUERY  x1 y1 z1 x2 y2 z2 

Constraints 

$1\leq T\leq50$ 

$1\leq n\leq100$ 

$1\leq m\leq1000$ 

$1\leq x1\leq x2\leq n$ 

$1\le y1\le y2\le n$ 

$1\le z1\le z2\le n$ 

$1\leq x,y,z\leq n$ 

-10^{9} \le W \le 10^{9}  

Sample Input

2
4 5
UPDATE 2 2 2 4
QUERY 1 1 1 3 3 3
UPDATE 1 1 1 23
QUERY 2 2 2 4 4 4
QUERY 1 1 1 3 3 3
2 4
UPDATE 2 2 2 1
QUERY 1 1 1 1 1 1
QUERY 1 1 1 2 2 2
QUERY 2 2 2 2 2 2

Sample Output

4
4
27
0
1
1

Explanation 

In the first test case, there is a cube of 4 * 4 * 4 and there are 5 queries.  Initially all the cells (1,1,1) to (4,4,4) are 0. 

UPDATE 2 2 2 4 makes the cell (2,2,2) = 4 

QUERY 1 1 1 3 3 3. As (2,2,2) is updated to 4 and the rest are all 0. The answer to this query is 4. 

UPDATE 1 1 1 23. updates the cell (1,1,1) to 23. 
QUERY 2 2 2 4 4 4. Only the cell (1,1,1) and (2,2,2) are non-zero and (1,1,1) is not between (2,2,2) and (4,4,4). So, the answer is 4. 

QUERY 1 1 1 3 3 3. 2 cells are non-zero and their sum is 23+4 = 27.

Difficulty: MEDIUM_HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
import sys
for t in range(int(sys.stdin.readline().strip())):
	(n, m) = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	nonzero = {}
	for i in range(m):
		parts = sys.stdin.readline().strip().split(' ')
		t = parts[0]
		vals = [int(x) for x in parts[1:]]
		if t == 'UPDATE':
			coords = tuple(vals[:3])
			nonzero[coords] = vals[-1]
		elif t == 'QUERY':
			total = 0
			lower = vals[:3]
			upper = vals[3:]
			for (coords, val) in nonzero.items():
				in_bounds = True
				for j in range(3):
					if not lower[j] <= coords[j] <= upper[j]:
						in_bounds = False
				if in_bounds:
					total += val
			print(total)
		else:
			raise Exception('Input Fubar')


import sys
source = sys.stdin

def update(A, x, y, z, val):
	for a in A:
		if a[0] == x and a[1] == y and (a[2] == z):
			a[3] = val
			return
	A.append([x, y, z, val])

def query(A, x1, y1, z1, x2, y2, z2):
	total = 0
	for a in A:
		if a[0] >= x1 and a[0] <= x2 and (a[1] >= y1) and (a[1] <= y2) and (a[2] >= z1) and (a[2] <= z2):
			total += a[3]
	return total
A = []
T = int(source.readline())
for t in range(T):
	[N, M] = [int(s) for s in source.readline().split()]
	A.clear()
	for _ in range(M):
		c = source.readline().split()
		args = [int(s) for s in c[1:]]
		if c[0] == 'UPDATE':
			update(A, *args)
		else:
			val = query(A, *args)
			print(val)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	updates = {}
	for ic in range(m):
		parts = input().strip().split()
		if parts[0] == 'UPDATE':
			(i, j, k, w) = map(int, parts[1:])
			updates[i, j, k] = w
		else:
			(i1, j1, k1, i2, j2, k2) = map(int, parts[1:])
			print(sum((w for (c, w) in updates.items() if i1 <= c[0] <= i2 and j1 <= c[1] <= j2 and (k1 <= c[2] <= k2))))


T = int(input())
for test_case in range(T):
	values = {}
	(N, M) = [int(i) for i in input().split()]
	for line in range(M):
		command = input().split()
		command = [command[0]] + [int(i) for i in command[1:]]
		if command[0] == 'UPDATE':
			values[tuple(command[1:4])] = command[4]
		elif command[0] == 'QUERY':
			(x1, y1, z1, x2, y2, z2) = command[1:]
			print(sum([values[key] for key in values if x1 <= key[0] <= x2 and y1 <= key[1] <= y2 and (z1 <= key[2] <= z2)]))


d = dict()

def do_update(x, y, z, w):
	if not d.__contains__(x):
		d[x] = dict()
	if not d[x].__contains__(y):
		d[x][y] = dict()
	d[x][y][z] = w

def do_query(x1, y1, z1, x2, y2, z2):
	s = 0
	for x_val in d.items():
		if x_val[0] < x1 or x_val[0] > x2:
			continue
		for y_val in x_val[1].items():
			if y_val[0] < y1 or y_val[0] > y2:
				continue
			for z_val in y_val[1].items():
				if z_val[0] < z1 or z_val[0] > z2:
					continue
				s += z_val[1]
	print(int(s))
t = int(input())
for i in range(0, t):
	(N, M) = map(int, input().split())
	d = dict()
	for j in range(0, M):
		ln = input().split()
		if ln[0] == 'UPDATE':
			do_update(*list(map(float, ln[1:])))
		else:
			do_query(*list(map(float, ln[1:])))


T = int(input())
for t in range(0, T):
	(N, M) = list(map(int, input().strip().split(' ')))
	updates = {}
	queries = []
	for m in range(0, M + 1):
		if len(queries) != 0:
			sums = [0] * len(queries)
			for (k, v) in updates.items():
				for (i, q) in enumerate(queries):
					if q[0] <= k[0] <= q[3] and q[1] <= k[1] <= q[4] and (q[2] <= k[2] <= q[5]):
						sums[i] += v
			[print(s) for s in sums]
			queries = []
		if m < M:
			l = list(input().strip().split(' '))
			if l[0] == 'UPDATE':
				(x, y, z, v) = map(int, l[1:])
				updates[tuple((x, y, z))] = v
			elif l[0] == 'QUERY':
				(x1, y1, z1, x2, y2, z2) = map(int, l[1:])
				queries.append(tuple((x1, y1, z1, x2, y2, z2)))


class FenwickTree3D:

	def __init__(self, n):
		sz = 1
		while n >= sz:
			sz *= 2
		self.size = sz
		self.data = [[[0] * sz for i in range(sz)] for j in range(sz)]

	def sum(self, x1, y1, z1):
		if min(x1, y1, z1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				z = z1
				while z >= 0:
					s += self.data[x][y][z]
					z = (z & z + 1) - 1
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, z1, x2, y2, z2):
		return self.sum(x2, y2, z2) - self.sum(x1 - 1, y2, z2) - self.sum(x2, y1 - 1, z2) - self.sum(x2, y2, z1 - 1) + self.sum(x1 - 1, y1 - 1, z2) + self.sum(x1 - 1, y2, z1 - 1) + self.sum(x2, y1 - 1, z1 - 1) - self.sum(x1 - 1, y1 - 1, z1 - 1)

	def add(self, x1, y1, z1, w):
		assert min(x1, y1, z1) > 0
		x = x1
		while x < self.size:
			y = y1
			while y < self.size:
				z = z1
				while z < self.size:
					self.data[x][y][z] += w
					z |= z + 1
				y |= y + 1
			x |= x + 1
for case in range(int(input())):
	(N, M) = map(int, input().split())
	t = FenwickTree3D(N)
	ops = [tuple(input().split()) for _ in range(M)]
	for op in ops:
		if op[0] == 'UPDATE':
			curr = t.sumrange(int(op[1]), int(op[2]), int(op[3]), int(op[1]), int(op[2]), int(op[3]))
			t.add(int(op[1]), int(op[2]), int(op[3]), int(op[4]) - curr)
		else:
			assert op[0] == 'QUERY'
			print(t.sumrange(int(op[1]), int(op[2]), int(op[3]), int(op[4]), int(op[5]), int(op[6])))


cases = int(input())
for i in range(cases):
	(N, M) = list(map(int, input().split()))
	updates = []
	for j in range(M):
		command = input().split()
		if command[0] == 'UPDATE':
			update = []
			x = int(command[1])
			y = int(command[2])
			z = int(command[3])
			value = int(command[4])
			for elem in updates:
				if elem[0] == x and elem[1] == y and (elem[2] == z):
					updates.remove(elem)
					break
			update = (x, y, z, value)
			updates.append(update)
		elif command[0] == 'QUERY':
			x1 = int(command[1])
			y1 = int(command[2])
			z1 = int(command[3])
			x2 = int(command[4])
			y2 = int(command[5])
			z2 = int(command[6])
			total = 0
			for update in updates:
				x = int(update[0])
				y = int(update[1])
				z = int(update[2])
				value = int(update[3])
				if (x >= x1 and x <= x2) and (y >= y1 and y <= y2) and (z >= z1 and z <= z2):
					total += value
			print(total)


class val:

	def __init__(self, x, y, z, value):
		self.x = x
		self.y = y
		self.z = z
		self.value = value

	def __repr__(self):
		return 'x: ' + str(self.x) + ' y: ' + str(self.y) + ' z: ' + str(self.z) + ' value: ' + str(self.value)

def add(val_list, x, y, z, new_val):
	for value in val_list:
		if value.x == x and value.y == y and (value.z == z):
			value.value = new_val
			return
	val_list.append(val(x, y, z, new_val))
cnt = int(input())
for idx in range(cnt):
	val_lst = []
	(size, cnt_1) = [int(x) for x in input().split()]
	for i in range(cnt_1):
		lst = input().split()
		if lst[0] == 'UPDATE':
			add(val_lst, int(lst[1]), int(lst[2]), int(lst[3]), int(lst[4]))
		if lst[0] == 'QUERY':
			res = 0
			for value in val_lst:
				if value.x >= int(lst[1]) and value.x <= int(lst[4]) and (value.y >= int(lst[2])) and (value.y <= int(lst[5])) and (value.z >= int(lst[3])) and (value.z <= int(lst[6])):
					res += value.value
			print(res)


numTests = int(input())
cube = []
for i in range(0, 100):
	cube.append([])
	for j in range(0, 100):
		cube[i].append([])
		for k in range(0, 100):
			cube[i][j].append(0)
while numTests != 0:
	indexList = [[0, 0, 0, 0]]
	line = input()
	tokens = line.split(' ')
	N = int(tokens[0])
	numOp = int(tokens[1])
	while numOp != 0:
		query = input()
		tokens = query.split(' ')
		if tokens[0] == 'UPDATE':
			x = int(tokens[1]) - 1
			y = int(tokens[2]) - 1
			z = int(tokens[3]) - 1
			w = int(tokens[4])
			cube[x][y][z] = w
			tempList = []
			tempList.append(x)
			tempList.append(y)
			tempList.append(z)
			tempList.append(w)
			flag = 0
			for index in indexList:
				if index[0] == x and index[1] == y and (index[2] == z):
					index[3] = w
					flag = 1
			if flag == 0:
				indexList.append(tempList)
		elif tokens[0] == 'QUERY':
			x1 = int(tokens[1]) - 1
			y1 = int(tokens[2]) - 1
			z1 = int(tokens[3]) - 1
			x2 = int(tokens[4]) - 1
			y2 = int(tokens[5]) - 1
			z2 = int(tokens[6]) - 1
			sum = 0
			for index in indexList:
				if index[0] >= x1 and index[0] <= x2:
					if index[1] >= y1 and index[1] <= y2:
						if index[2] >= z1 and index[2] <= z2:
							sum += index[3]
			print(sum)
		numOp -= 1
	numTests -= 1


def getTests():
	T = int(input())
	for _ in range(T):
		(_, M) = map(int, input().split())

		def lines():
			for _ in range(M):
				yield input()
		yield lines()

def debug(*args):
	return
	print(*args)

def main():
	for queries in getTests():
		cube = {}

		def processUpdate(q):
			(x, y, z, w) = map(int, q.split()[1:])
			cube[x, y, z] = w

		def processQuery(q):
			(x1, y1, z1, x2, y2, z2) = map(int, q.split()[1:])
			sum = 0
			for ((x, y, z), w) in cube.items():
				if all([x1 <= x <= x2, y1 <= y <= y2, z1 <= z <= z2]):
					debug(x, y, z, x1, y1, z1, x2, y2, z2)
					sum += w
			print(sum)
		for q in queries:
			if q.startswith('UPDATE'):
				processUpdate(q)
			else:
				processQuery(q)
			debug('=' * 40)
main()


from array import array
n_tests = int(input())
for t in range(n_tests):
	(n, m) = map(int, input().split())
	row = array('l', [0] * n)
	data = {}
	for _ in range(m):
		s = input().split()
		if s[0] == 'UPDATE':
			(x, y, z, w) = map(int, s[1:])
			data.setdefault(x, dict()).setdefault(y, row[:])[z - 1] = w
		elif s[0] == 'QUERY':
			(x1, y1, z1, x2, y2, z2) = map(int, s[1:])
			total = 0
			for i in range(x1, x2 + 1):
				if i in data:
					di = data[i]
					for j in range(y1, y2 + 1):
						if j in di:
							dj = di[j]
							total += sum(dj[z1 - 1:z2])
			print(total)


triple_to_w_dict = dict()

def query(x1, y1, z1, x2, y2, z2):
	triples = triple_to_w_dict.keys()
	triples = filter(lambda triple: x1 <= triple[0] and triple[0] <= x2 and (y1 <= triple[1]) and (triple[1] <= y2) and (z1 <= triple[2]) and (triple[2] <= z2), triples)
	ret = 0
	for triple in triples:
		ret += triple_to_w_dict[triple]
	return ret

def update(x, y, z, W):
	triple_to_w_dict[x, y, z] = W
T = int(input())
for _ in range(T):
	triple_to_w_dict = dict()
	(N, M) = [int(x) for x in input().split()]
	for i in range(M):
		tokens = input().split()
		if tokens[0] == 'UPDATE':
			(x, y, z, W) = tuple([int(x) for x in tokens[1:]])
			update(x, y, z, W)
		if tokens[0] == 'QUERY':
			(x1, y1, z1, x2, y2, z2) = tuple([int(x) for x in tokens[1:]])
			print(query(x1, y1, z1, x2, y2, z2))


class binaryindextree3d:

	def __init__(self, size):
		self.size = size
		self.l = [[[0] * size for _ in range(size)] for _ in range(size)]
		self.r = [[[0] * (size + 1) for _ in range(size + 1)] for _ in range(size + 1)]

	def __setitem__(self, ind, v):
		assert len(ind) == 3
		assert all(map(lambda a: a < self.size, ind))
		d = v - self.l[ind[0]][ind[1]][ind[2]]
		self.l[ind[0]][ind[1]][ind[2]] = v
		ind = tuple(map(lambda a: a + 1, ind))
		for x in self.unode(ind[0]):
			for y in self.unode(ind[1]):
				for z in self.unode(ind[2]):
					self.r[x][y][z] += d

	def __getitem__(self, ind):
		assert len(ind) == 3
		assert all(map(lambda a: a < self.size, ind))
		ind = tuple(map(lambda a: a + 1, ind))
		s = 0
		for x in self.pnode(ind[0]):
			for y in self.pnode(ind[1]):
				for z in self.pnode(ind[2]):
					s += self.r[x][y][z]
		return s

	def query(self, ind1, ind2):
		assert len(ind1) == 3
		assert all(map(lambda a: a < self.size, ind1))
		assert len(ind2) == 3
		assert all(map(lambda a: a < self.size, ind2))
		ind1 = tuple(map(lambda a: a - 1, ind1))
		return self[ind2] - self[ind1[0], ind2[1], ind2[2]] - self[ind2[0], ind1[1], ind2[2]] - self[ind2[0], ind2[1], ind1[2]] + self[ind2[0], ind1[1], ind1[2]] + self[ind1[0], ind2[1], ind1[2]] + self[ind1[0], ind1[1], ind2[2]] - self[ind1]

	def __len__(self):
		return self.size

	def pnode(self, n):
		while n > 0:
			yield n
			n -= -n & n

	def unode(self, n):
		while n < len(self.r):
			yield n
			n += -n & n
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = binaryindextree3d(n)
	for _ in range(m):
		inp = input().split()
		if inp[0] == 'UPDATE':
			p = tuple(map(lambda a: int(a) - 1, inp[1:4]))
			l[p] = int(inp[4])
		elif inp[0] == 'QUERY':
			p1 = tuple(map(lambda a: int(a) - 1, inp[1:4]))
			p2 = tuple(map(lambda a: int(a) - 1, inp[4:7]))
			print(l.query(p1, p2))


from sys import stdin
import re
T = int(stdin.readline())
for _ in range(T):
	(N, M) = [int(x) for x in stdin.readline().strip().split(' ')]
	operations = [stdin.readline().strip() for _ in range(M)]
	blocks = {}
	for o in operations:
		m = re.search('UPDATE\\s+(\\d+)\\s+(\\d+)\\s+(\\d+)\\s+(\\d+)', o)
		if m:
			(x, y, z, w) = [int(i) for i in m.groups()]
			blocks[x, y, z] = w
		m = re.search('QUERY\\s+(\\d+)\\s+(\\d+)\\s+(\\d+)\\s+(\\d+)\\s+(\\d+)\\s+(\\d+)', o)
		if m:
			(x1, y1, z1, x2, y2, z2) = [int(i) for i in m.groups()]
			print(sum([w for ((x, y, z), w) in blocks.items() if x1 <= x <= x2 and y1 <= y <= y2 and (z1 <= z <= z2)]))


def update(tree, x, y, z, val, N):
	while x <= N:
		y1 = y
		while y1 <= N:
			z1 = z
			while z1 <= N:
				tree[x, y1, z1] += val
				z1 += z1 & -z1
			y1 += y1 & -y1
		x += x & -x

def summ(tree, x, y, z):
	res = 0
	while x > 0:
		y1 = y
		while y1 > 0:
			z1 = z
			while z1 > 0:
				res += tree[x, y1, z1]
				z1 -= z1 & -z1
			y1 -= y1 & -y1
		x -= x & -x
	return res
from collections import defaultdict
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	vals = defaultdict(int)
	tree = defaultdict(int)
	for _ in range(M):
		query = input().split()
		if query[0] == 'UPDATE':
			(x, y, z, value) = map(int, query[1:])
			update(tree, x, y, z, value - vals[x, y, z], N)
			vals[x, y, z] = value
		else:
			(x0, y0, z0, x, y, z) = map(int, query[1:])
			value1 = summ(tree, x, y, z)
			value1 -= summ(tree, x0 - 1, y, z)
			value1 -= summ(tree, x, y0 - 1, z)
			value1 += summ(tree, x0 - 1, y0 - 1, z)
			value2 = summ(tree, x, y, z0 - 1)
			value2 -= summ(tree, x0 - 1, y, z0 - 1)
			value2 -= summ(tree, x, y0 - 1, z0 - 1)
			value2 += summ(tree, x0 - 1, y0 - 1, z0 - 1)
			print(value1 - value2)


T = int(input())

def update(matrix, vals):
	x = int(vals[0])
	y = int(vals[1])
	z = int(vals[2])
	w = int(vals[3])
	matrix[x, y, z] = w

def query(matrix, vals):
	x1 = int(vals[0])
	y1 = int(vals[1])
	z1 = int(vals[2])
	x2 = int(vals[3])
	y2 = int(vals[4])
	z2 = int(vals[5])
	vSum = 0
	keys = matrix.keys()
	for (i, j, k) in keys:
		if x1 <= i <= x2 and y1 <= j <= y2 and (z1 <= k <= z2):
			vSum += matrix[i, j, k]
	print(vSum)
operation = {'UPDATE': update, 'QUERY': query}
for count in range(T):
	line = str(input()).split()
	N = int(line[0])
	M = int(line[1])
	matrix = dict()
	for ops in range(M):
		line = str(input()).split()
		func = operation[str(line[0]).upper().strip()]
		func(matrix, line[1:])


t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	repeat = range(1, n + 1)
	matrix = {}
	for _ in range(m):
		(command, *numbers) = input().split()
		if command == 'UPDATE':
			(x, y, z, value) = [int(x) for x in numbers]
			matrix[x, y, z] = value
		elif command == 'QUERY':
			(x1, y1, z1, x2, y2, z2) = [int(x) for x in numbers]
			print(sum((value for (key, value) in matrix.items() if x1 <= key[0] <= x2 and y1 <= key[1] <= y2 and (z1 <= key[2] <= z2))))


t = int(input())
for _ in range(t):
	(n, m) = (int(x) for x in input().strip().split(' '))
	cube = {}
	for _2 in range(m):
		(query, *values) = input().strip().split(' ')
		total = 0
		if query == 'QUERY':
			(x1, y1, z1, x2, y2, z2) = [int(x) for x in values]
			for (point, v) in cube.items():
				if point[0] >= min(x1, x2) and point[0] <= max(x1, x2) and (point[1] >= min(y1, y2)) and (point[1] <= max(y1, y2)) and (point[2] >= min(z1, z2)) and (point[2] <= max(z1, z2)):
					total += v
			print(total)
		else:
			(*pos, v1) = [int(x) for x in values]
			pos = tuple(pos)
			cube[pos] = v1


class Node:

	def __init__(self, l, h, v=0):
		(self.l, self.h) = map(tuple, (l, h))
		self.v = v
		self.is_split = False
		self.c = []

	def split(self):
		self.is_split = True
		(lx, ly, lz) = self.l
		(hx, hy, hz) = self.h
		(mx, my, mz) = map(lambda x, y: x + y >> 1, self.l, self.h)
		self.c.append(Node((lx, ly, lz), (mx, my, mz), self.v))
		if lz != hz:
			self.c.append(Node((lx, ly, mz + 1), (mx, my, hz), self.v))
		if ly != hy:
			if lz != hz:
				self.c.append(Node((lx, my + 1, mz + 1), (mx, hy, hz), self.v))
			self.c.append(Node((lx, my + 1, lz), (mx, hy, mz), self.v))
		if lx != hx:
			self.c.append(Node((mx + 1, ly, lz), (hx, my, mz), self.v))
			if lz != hz:
				self.c.append(Node((mx + 1, ly, mz + 1), (hx, my, hz), self.v))
			if ly != hy:
				if lz != hz:
					self.c.append(Node((mx + 1, my + 1, mz + 1), (hx, hy, hz), self.v))
				self.c.append(Node((mx + 1, my + 1, lz), (hx, hy, mz), self.v))

	def get(self, l, h):
		if any((self.l[i] > h[i] or self.h[i] < l[i] for i in range(3))):
			return 0
		if all((self.l[i] >= l[i] and self.h[i] <= h[i] for i in range(3))) or not self.is_split:
			return self.v
		return sum(map(lambda x: x.get(l, h), self.c))

	def set(self, p, v):
		if all((self.l[i] <= p[i] <= self.h[i] for i in range(3))):
			if self.l == self.h:
				self.v = v
			else:
				if not self.is_split:
					self.split()
				self.v = 0
				for c in self.c:
					self.v += c.set(p, v)
		return self.v
for T in range(int(input())):
	(N, Q) = map(int, input().split())
	a = Node((1, 1, 1), (N, N, N))
	for q in range(Q):
		x = input().split()
		if x[0] == 'UPDATE':
			x = list(map(int, x[1:]))
			a.set(x[:3], x[3])
		else:
			x = list(map(int, x[1:]))
			print(a.get(x[:3], x[3:]))


import fileinput
import decimal

class Query:

	def __init__(self, query):
		self.src = query.rstrip()
		parts = query.split()
		if len(parts) < 5:
			raise ValueError('Bad query: ' + query)
		if parts[0] == 'UPDATE':
			self.q = 'UPDATE'
			if len(parts) != 5:
				raise ValueError('Bad UPDATE length: ' + query)
			self.x = int(parts[1])
			self.y = int(parts[2])
			self.z = int(parts[3])
			self.value = int(parts[4])
		elif parts[0] == 'QUERY':
			if len(parts) != 7:
				raise ValueError('Bad QUERY length: ' + query)
			self.q = 'QUERY'
			self.x = int(parts[1])
			self.y = int(parts[2])
			self.z = int(parts[3])
			self.x2 = int(parts[4])
			self.y2 = int(parts[5])
			self.z2 = int(parts[6])
		else:
			raise ValueError('Unknown query: ' + query)

	def __str__(self):
		return self.src

class Cube:

	def __init__(self):
		self.a = {}

	@staticmethod
	def format_index(x, y, z):
		return (x, y, z)

	def update(self, query):
		self.a[self.format_index(query.x, query.y, query.z)] = query.value

	def sum_straight(self, query):
		result = 0
		for x in range(query.x, query.x2 + 1):
			for y in range(query.y, query.y2 + 1):
				for z in range(query.z, query.z2 + 1):
					index = self.format_index(x, y, z)
					result += self.a.get(index, 0)
		return result

	def sum_sparse(self, query):
		result = 0
		for (x, y, z) in self.a.keys():
			if query.x <= x <= query.x2 and query.y <= y <= query.y2 and (query.z <= z <= query.z2):
				result += self.a[x, y, z]
		return result

	def query(self, query):
		volume = (query.x2 - query.x + 1) * (query.y2 - query.y + 1) * (query.z2 - query.z + 1)
		if len(self.a) <= volume:
			return self.sum_sparse(query)
		return self.sum_straight(query)

def solve_case(string_iter):
	a = Cube()
	answer = []
	(n, m) = next(string_iter).split()
	n = int(n)
	m = int(m)
	queries = []
	for i in range(0, m):
		q = Query(next(string_iter))
		if q.q == 'UPDATE':
			a.update(q)
		if q.q == 'QUERY':
			result = str(a.query(q))
			answer.append(result)
		queries.append(q)
	return answer

def solve(string_iter):
	t = int(next(string_iter))
	answer = []
	for i in range(0, t):
		answer.extend(solve_case(string_iter))
	return answer
answer = solve(fileinput.input())
print('\n'.join(answer))


import sys
testCases = None
matrix = None

def update(x, y, z, value):
	matrix[x, y, z] = value

def query(x1, y1, z1, x2, y2, z2):
	s = 0
	for key in matrix.keys():
		if x1 <= key[0] and key[0] <= x2 and (y1 <= key[1]) and (key[1] <= y2) and (z1 <= key[2]) and (key[2] <= z2):
			s += matrix.get(key)
	return s
for line in sys.stdin:
	if testCases is None:
		testCases = int(line)
	if line.startswith('UPDATE'):
		update(*[int(x) for x in line.split()[1:]])
	elif line.startswith('QUERY'):
		q = query(*[int(x) for x in line.split()[1:]])
		print(q)
	else:
		matrix = dict()


def assert_arg_count(argc, args):
	assert len(args) == argc, 'args needs to be exactly %d was %d' % (argc, len(args))

def update(updated, matrix, args):
	assert_arg_count(4, args)
	x = args[0] - 1
	y = args[1] - 1
	z = args[2] - 1
	w = args[3]
	matrix[x][y][z] = w
	updated.add((x, y, z))

def query(updated, matrix, args):
	assert_arg_count(6, args)

	def find_in_bounds(updated, args):
		(x1, y1, z1, x2, y2, z2) = args
		coords = []
		for (x, y, z) in updated:
			if x >= x1 - 1 and x < x2 and (y >= y1 - 1) and (y < y2) and (z >= z1 - 1) and (z < z2):
				coords.append((x, y, z))
		return coords
	coords = find_in_bounds(updated, args)
	sum = 0
	for (x, y, z) in coords:
		sum += matrix[x][y][z]
	print(sum)

def exec_command(line, updated, matrix):

	def to_int(args):
		return [int(x) for x in args]
	args = to_int(line.split(' ')[1:])
	if line.startswith('UPDATE'):
		update(updated, matrix, args)
	elif line.startswith('QUERY'):
		query(updated, matrix, args)
	else:
		assert false

def create_matrix(n):
	return [[[0 for k in range(n)] for j in range(n)] for i in range(n)]

def main():
	test_cases = int(input())
	for case in range(0, test_cases):
		line = input()
		n = int(line.split(' ')[0])
		m = int(line.split(' ')[1])
		updated = set()
		matrix = create_matrix(n)
		for k in range(m):
			exec_command(input(), updated, matrix)
main()


for _ in range(int(input())):
	(__, M) = map(int, input().split())
	cube = {}
	for __ in range(M):
		command = input().split()
		if command[0] == 'UPDATE':
			cube[int(command[1]), int(command[2]), int(command[3])] = int(command[4])
		else:
			result = 0
			for (key, value) in cube.items():
				if key[0] in range(int(command[1]), int(command[4]) + 1) and key[1] in range(int(command[2]), int(command[5]) + 1) and (key[2] in range(int(command[3]), int(command[6]) + 1)):
					result += value
			print(result)


from collections import deque
t = int(input())
for _ in range(t):
	updateList = deque()
	(n, m) = [int(x) for x in input().strip().split(' ')]
	for _ in range(m):
		query = input().strip().split(' ')
		command = query[0]
		if command == 'UPDATE':
			(x, y, z, arg) = [int(i) for i in query[1:]]
			for (i, update) in enumerate(updateList):
				if update[0:3] == [x, y, z]:
					updateList[i][3] = arg
					break
			else:
				updateList.append([x, y, z, arg])
		else:
			(x1, y1, z1, x2, y2, z2) = [int(i) for i in query[1:]]
			ans = 0
			for update in updateList:
				if update[0] >= x1 and update[0] <= x2 and (update[1] >= y1) and (update[1] <= y2) and (update[2] >= z1) and (update[2] <= z2):
					ans += update[3]
			print(ans)


import sys
input = [l.strip() for l in sys.stdin]
cases = int(input.pop(0))

def ck(a, s):
	return all([int(e) in range(s + 1) for e in a])
for c in range(cases):
	(s, o) = [int(i) for i in input.pop(0).split(' ')]
	data = {}
	for q in range(o):
		cmd = input.pop(0).split(' ')
		if cmd[0] == 'UPDATE':
			(x, y, z, v) = [int(i) for i in cmd[1:]]
			if ck(cmd[1:4], s):
				data[x, y, z] = v
		elif cmd[0] == 'QUERY':
			sm = 0
			(x1, y1, z1, x2, y2, z2) = [int(i) for i in cmd[1:]]
			if ck(cmd[1:], s):
				for (k, v) in data.items():
					(x, y, z) = k
					if x in range(x1, x2 + 1) and y in range(y1, y2 + 1) and (z in range(z1, z2 + 1)):
						sm += v
				print(sm)
			else:
				print('Out of bound error!!')


t = int(input().strip())
for l in range(t):
	(n, m) = input().strip().split()
	n = int(n)
	m = int(m)
	table = dict()
	for i in range(0, m):
		query = input().strip().split()
		if query[0] == 'UPDATE':
			table[int(query[1]), int(query[2]), int(query[3])] = int(query[4])
		elif query[0] == 'QUERY':
			x1 = int(query[1])
			y1 = int(query[2])
			z1 = int(query[3])
			x2 = int(query[4])
			y2 = int(query[5])
			z2 = int(query[6])
			sum = 0
			for (index, value) in table.items():
				if index[0] >= x1 and index[0] <= x2 and (index[1] >= y1) and (index[1] <= y2) and (index[2] >= z1) and (index[2] <= z2):
					sum += value
			print(sum)


T = int(input())
for t in range(T):
	map = {}
	(N, M) = [int(i) for i in input().split(' ')]
	for m in range(M):
		q = input()
		if q[0] == 'U':
			(x, y, z, v) = [int(i) for i in q.split(' ')[1:]]
			map[x, y, z] = v
		else:
			(x1, y1, z1, x2, y2, z2) = [int(i) for i in q.split(' ')[1:]]
			sum = 0
			for key in map.keys():
				if x1 <= key[0] <= x2 and y1 <= key[1] <= y2 and (z1 <= key[2] <= z2):
					sum += map[key]
			print(sum)


from itertools import product

def update(dict, tup, value):
	dict[tup] = value

def querySum(dict, l):
	total = 0
	for keyTup in dict.keys():
		if keyTup[0] in range(l[0], l[3] + 1) and keyTup[1] in range(l[1], l[4] + 1) and (keyTup[2] in range(l[2], l[5] + 1)):
			total += dict[keyTup]
	print(total)
T = int(input())
for i in range(T):
	(N, numQ) = [int(x) for x in input().strip().split(' ')]
	pp = product(range(1, N + 1), repeat=3)
	d = dict()
	for i in range(numQ):
		line = input().strip().split(' ')
		if line[0] == 'UPDATE':
			t = tuple([int(x) for x in line[1:4]])
			val = int(line[4])
			update(d, t, val)
		else:
			blockList = [int(x) for x in line[1:]]
			querySum(d, blockList)


import sys
from collections import defaultdict

class Query:
	__slots__ = ['bounds', 'total']

	def __init__(self, bounds):
		self.bounds = bounds
		self.total = 0

	def update(self, spot, diff, verbose=False):
		bounds = self.bounds
		if bounds[0] <= spot[0] <= bounds[3] and bounds[1] <= spot[1] <= bounds[4] and (bounds[2] <= spot[2] <= bounds[5]):
			self.total += diff

	def evaluate(self):
		return self.total

class QueryList:

	def __init__(self, size):
		self.events = []
		self.size = size

	def solve(self):
		values = {}
		queries = [Query(nums) for (_, nums) in reversed([e for e in self.events if e[0] == 'QUERY'])]
		for (kind, nums) in self.events:
			if kind == 'QUERY':
				print(queries.pop().evaluate())
			elif kind == 'UPDATE':
				diff = nums[3] - values.get(tuple(nums[:3]), 0)
				values[tuple(nums[:3])] = nums[3]
				for query in queries:
					query.update(nums, diff)

def main(file):
	num_tests = int(file.readline().strip())
	current = None
	for line in file:
		if line.strip()[0].isdigit():
			size = int(line.split()[0])
			if current:
				current.solve()
			current = QueryList(size)
		elif line.startswith('UPDATE'):
			nums = [int(x) for x in line.split()[1:]]
			current.events.append(('UPDATE', nums))
		elif line.startswith('QUERY'):
			nums = [int(x) for x in line.split()[1:]]
			current.events.append(('QUERY', nums))
		else:
			print('Could not parse line:', line)
	if current:
		current.solve()
import sys
main(sys.stdin)


import sys
T = int(sys.stdin.readline())
for t in range(T):
	values = {}
	(N, M) = map(int, sys.stdin.readline().split())
	for m in range(M):
		line = sys.stdin.readline().split()
		if line[0] == 'UPDATE':
			(x, y, z, v) = map(int, line[1:])
			values[x, y, z] = v
		else:
			(x1, y1, z1, x2, y2, z2) = map(int, line[1:])
			s = 0
			for (key, value) in values.items():
				if x1 <= key[0] <= x2 and y1 <= key[1] <= y2 and (z1 <= key[2] <= z2):
					s += value
			print(s)


states = {}

def run_action(action, p1, p2):
	if action == 'UPDATE':
		states[p1] = p2[0]
	else:
		s = sum([value for (key, value) in states.items() if p1[0] <= key[0] <= p2[0] and p1[1] <= key[1] <= p2[1] and (p1[2] <= key[2] <= p2[2])])
		print(s)
T = int(input())
for i in range(T):
	(N, M) = [int(x) for x in input().split()]
	states.clear()
	for j in range(M):
		tmp = input().split()
		action = tmp[0]
		p1 = tuple([int(x) for x in tmp[1:4]])
		p2 = tuple([int(x) for x in tmp[4:]])
		run_action(action, p1, p2)


T = int(input())
for _ in range(T):
	(N, M) = [int(x) for x in input().split()]
	points = {}
	for _ in range(M):
		cmd = input().split()
		if cmd[0] == 'UPDATE':
			(x, y, z) = [int(x) - 1 for x in cmd[1:-1]]
			value = int(cmd[-1])
			points[x, y, z] = value
		else:
			pointA = [int(x) - 1 for x in cmd[1:4]]
			pointB = [int(x) - 1 for x in cmd[4:]]
			total = 0
			for k in points:
				(x, y, z) = k
				value = points[k]
				if pointA[0] <= x and x <= pointB[0] and (pointA[1] <= y) and (y <= pointB[1]) and (pointA[2] <= z) and (z <= pointB[2]):
					total += value
			print(total)


T = int(input())
for t in range(T):
	(N, M) = map(int, input().split())
	cube = {}
	for m in range(M):
		inputs = input().split()
		op = inputs[0]
		args = [int(s) for s in inputs[1:]]
		if op == 'UPDATE':
			(x, y, z, W) = args
			cube[x, y, z] = W
		elif op == 'QUERY':
			(x1, y1, z1, x2, y2, z2) = args
			res = sum((v for ((x, y, z), v) in cube.items() if x1 <= x <= x2 and y1 <= y <= y2 and (z1 <= z <= z2)))
			print(res)


t = int(input().strip())
for _ in range(t):
	(m, n) = map(int, input().strip().split())
	d = {}
	for notused in range(n):
		c = input().split()
		c1 = list(map(int, c[1:]))
		if c[0] == 'UPDATE':
			d[c1[0], c1[1], c1[2]] = c1[3]
		else:
			s = 0
			for k in d.keys():
				if k[0] >= c1[0] and k[0] <= c1[3] and (k[1] >= c1[1]) and (k[1] <= c1[4]) and (k[2] >= c1[2]) and (k[2] <= c1[5]):
					s += d[k]
			print(s)
pass


from collections import defaultdict

class cubestore(object):

	def __init__(self):
		self.__s = defaultdict(int)

	def update(self, x, y, z, v):
		self.__s[x, y, z] = v

	def query(self, x1, y1, z1, x2, y2, z2):
		sum = 0
		for (k, v) in self.__s.items():
			(x, y, z) = k
			if x1 <= x <= x2 and y1 <= y <= y2 and (z1 <= z <= z2):
				sum += v
		return sum
t = int(input().strip())
for t1 in range(0, t):
	cs = cubestore()
	(n, m) = map(int, input().strip().split())
	for c1 in range(0, m):
		c = input().strip().split()
		if c[0] == 'UPDATE':
			cs.update(int(c[1]), int(c[2]), int(c[3]), int(c[4]))
		elif c[0] == 'QUERY':
			print(cs.query(int(c[1]), int(c[2]), int(c[3]), int(c[4]), int(c[5]), int(c[6])))


import sys, re

class Cube:

	def __init__(self):
		self.values = {}

	def add(self, x, y, z, value):
		key = '%d %d %d' % (x, y, z)
		self.values[str(key)] = value

	def overlap(self, j, k, l, a, b, c, x, y, z):
		return j >= a and j <= x and (k >= b) and (k <= y) and (l >= c) and (l <= z)

	def getsum(self, a, b, c, x, y, z):
		total = 0
		for coords in self.values:
			(j, k, l) = [int(x) for x in coords.split()]
			if self.overlap(j, k, l, a, b, c, x, y, z):
				total += self.values[coords]
		return total

	def clear(self):
		self.values = {}
testcases = sys.stdin.readlines()[1:]
cube = Cube()
for line in testcases:
	(command, args) = (line.split()[0], line.split()[1:])
	if re.match('[0-9]', command):
		cube.clear()
	elif command == 'UPDATE':
		(x, y, z, value) = [int(x) for x in args]
		cube.add(x, y, z, value)
	elif command == 'QUERY':
		(x, y, z, a, b, c) = [int(x) for x in args]
		print(cube.getsum(x, y, z, a, b, c))


T = int(input())
for i in range(T):
	(N, M) = [int(s) for s in input().split()]
	data = {}
	for j in range(M):
		info = input().split()
		if info[0] == 'UPDATE':
			data[info[1] + ' ' + info[2] + ' ' + info[3]] = int(info[4])
		else:
			x1 = int(info[1])
			y1 = int(info[2])
			z1 = int(info[3])
			x2 = int(info[4])
			y2 = int(info[5])
			z2 = int(info[6])
			res = 0
			for (k, v) in data.items():
				corr = [int(s) for s in k.split()]
				if corr[0] <= x2 and x1 <= corr[0] and (corr[1] <= y2) and (y1 <= corr[1]) and (corr[2] <= z2) and (z1 <= corr[2]):
					res += v
			print(res)


def run(n):
	for _ in range(n):
		(size, n_queries) = (int(n) for n in input().split(' '))
		if size < 1 or size > 100 or n_queries < 1 or (n_queries > 1000):
			return
		process_queries(size, n_queries)

def process_queries(size, n_queries):
	matrix = create_3d_matrix(size)
	updates_cache = [set(), set(), set()]
	queries_cache = dict()
	for _ in range(n_queries):
		query_parts = input().split(' ')
		operation = query_parts[0]
		if operation == 'UPDATE':
			(x, y, z, w) = (int(n) for n in query_parts[1:])
			if w < -10 ** 9 or w > 10 ** 9:
				return
			if x < 1 or x > size or y < 1 or (y > size) or (z < 1) or (z > size):
				return
			old_w = matrix[x - 1][y - 1][z - 1]
			matrix[x - 1][y - 1][z - 1] = w
			updates_cache[0].add(x)
			updates_cache[1].add(y)
			updates_cache[2].add(z)
			for (parameters, old_result) in queries_cache.items():
				(x1, y1, z1, x2, y2, z2) = parameters
				if x >= x1 and x <= x2 and (y >= y1) and (y <= y2) and (z >= z1) and (z <= z2):
					new_result = old_result - old_w + w
					queries_cache[parameters] = new_result
		elif operation == 'QUERY':
			query_params = tuple([int(n) for n in query_parts[1:]])
			(x1, y1, z1, x2, y2, z2) = query_params
			if x1 < 1 or x1 > size or y1 < 1 or (y1 > size) or (z1 < 1) or (z1 > size):
				return
			if x2 < 1 or x2 > size or y2 < 1 or (y2 > size) or (z2 < 1) or (z2 > size):
				return
			result = None
			if query_params in queries_cache:
				result = queries_cache[query_params]
			else:
				result = query_matrix(matrix, updates_cache, query_params)
				queries_cache[query_params] = result
			print(result)

def create_3d_matrix(n):
	return [[[0 for z in range(n)] for y in range(n)] for x in range(n)]

def query_matrix(matrix, cache, query_params):
	(x1, y1, z1, x2, y2, z2) = query_params
	result = 0
	for x in cache[0]:
		if x < x1 or x > x2:
			continue
		for y in cache[1]:
			if y < y1 or y > y2:
				continue
			for z in cache[2]:
				if z >= z1 and z <= z2:
					result += matrix[x - 1][y - 1][z - 1]
	return result
n_tests = int(input())
if n_tests >= 1 and n_tests <= 50:
	run(n_tests)


def cube_sum(n, ops):
	cube = {}
	for op in ops:
		spaced = op.split()
		if spaced[0] == 'UPDATE':
			(x, y, z, w) = tuple((int(x) for x in spaced[1:]))
			cube[x, y, z] = w
		elif spaced[0] == 'QUERY':
			(x1, y1, z1) = tuple((int(x) for x in spaced[1:4]))
			(x2, y2, z2) = tuple((int(x) for x in spaced[4:]))
			totes = 0
			for (p1, p2, p3) in cube:
				if (p1 >= x1 and p1 <= x2) and (p2 >= y1 and p2 <= y2) and (p3 >= z1 and p3 <= z2):
					totes += cube[p1, p2, p3]
			print(totes)
t = int(input().strip())
for a0 in range(t):
	(n, m) = tuple(input().strip().split(' '))
	(n, m) = (int(n), int(m))
	ops = []
	for a1 in range(m):
		ops.append(input().strip())
	cube_sum(n, ops)


def isn(a, b, c):
	return int(a) >= int(b) and int(a) <= int(c)
for adsf in range(int(input())):
	(n, m) = map(int, input().split())
	a = {}
	for fasdf in range(m):
		q = list(input().split())
		if q[0] == 'QUERY':
			rest = list(map(int, q[1:]))
			sum = 0
			for x in a:
				cont = True
				for i in range(3):
					if not isn(x[i], rest[i], rest[i + 3]):
						cont = False
				if cont:
					sum += a[x]
			print(sum)
		else:
			rest = list(map(int, q[1:]))
			a[rest[0], rest[1], rest[2]] = rest[3]


T = int(input().strip())
for t_ in range(T):
	(N, M) = [int(s) for s in input().strip().split()]
	cube = {}
	for m_ in range(M):
		tokens = [s for s in input().strip().split()]
		operation = tokens[0]
		values = [int(t) for t in tokens[1:]]
		if operation == 'UPDATE':
			cube[tuple(values[:3])] = values[3]
		elif operation == 'QUERY':
			total = 0
			for (key, value) in cube.items():
				if values[0] <= key[0] <= values[3] and values[1] <= key[1] <= values[4] and (values[2] <= key[2] <= values[5]):
					total += value
			print(total)


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().strip().split(' '))
	d = {}
	for _ in range(M):
		inp = [int(x) if x != 'UPDATE' and x != 'QUERY' else x for x in input().strip().split(' ')]
		if inp[0] == 'UPDATE':
			d[inp[1], inp[2], inp[3]] = inp[4]
		else:
			ans = 0
			for k in d.keys():
				flag = True
				for i in range(1, 4):
					if not k[i - 1] >= inp[i] or not k[i - 1] <= inp[3 + i]:
						flag = False
						break
				if flag:
					ans += d[k]
			print(ans)


ncubes = int(input())
for _ in range(ncubes):
	(d, ncom) = list(map(int, input().split(' ')))
	cube = {}
	for _ in range(ncom):
		(command, *args) = input().split(' ')
		args = list(map(int, args))
		if command == 'UPDATE':
			(x, y, z, val) = args
			cube[x, y, z] = val
		elif command == 'QUERY':
			(x1, y1, z1, x2, y2, z2) = args
			tot = 0
			for ((x, y, z), val) in cube.items():
				if x1 <= x <= x2 and y1 <= y <= y2 and (z1 <= z <= z2):
					tot += val
			print(tot)


T = int(input())
for i in range(T):
	commands = dict()
	(N, M) = tuple([int(i) for i in input().split()])
	for j in range(M):
		line = input().split()
		if line[0] == 'UPDATE':
			(x, y, z) = (int(line[1]), int(line[2]), int(line[3]))
			W = int(line[4])
			commands[x, y, z] = W
		elif line[0] == 'QUERY':
			(x1, y1, z1) = (int(line[1]), int(line[2]), int(line[3]))
			(x2, y2, z2) = (int(line[4]), int(line[5]), int(line[6]))
			tot = 0
			for t in commands:
				(x_t, y_t, z_t) = (t[0], t[1], t[2])
				if x1 <= x_t <= x2 and y1 <= y_t <= y2 and (z1 <= z_t <= z2):
					tot += commands[t]
			print(tot)


import sys
import bisect
t = int(input().strip())
for _ in range(t):
	(n, m) = [int(x) for x in input().strip().split(' ')]
	updates = {}
	by_x = []
	by_y = []
	by_z = []
	length = 0
	for _ in range(m):
		command_parts = input().strip().split(' ')
		if command_parts[0] == 'UPDATE':
			(x, y, z, w) = [int(x) for x in command_parts[1:]]
			updates[x, y, z] = w
			by_x = sorted([(x[0], x) for x in updates.keys()])
			by_y = sorted([(x[1], x) for x in updates.keys()])
			by_z = sorted([(x[2], x) for x in updates.keys()])
			length = len(by_x)
		elif command_parts[0] == 'QUERY':
			(x1, y1, z1, x2, y2, z2) = [int(x) for x in command_parts[1:]]
			x_l = bisect.bisect_left(by_x, (x1,))
			x_r = bisect.bisect_left(by_x, (x2 + 1,))
			y_l = bisect.bisect_left(by_y, (y1,))
			y_r = bisect.bisect_left(by_y, (y2 + 1,))
			z_l = bisect.bisect_left(by_z, (z1,))
			z_r = bisect.bisect_left(by_z, (z2 + 1,))
			x_range = set([x[1] for x in by_x[x_l:x_r]])
			y_range = set([x[1] for x in by_y[y_l:y_r]])
			z_range = set([x[1] for x in by_z[z_l:z_r]])
			indexes = x_range.intersection(y_range).intersection(z_range)
			print(sum([updates[i] for i in indexes]))


tc = int(input())
for i in range(0, tc):
	nm = input()
	nm = nm.split(' ')
	n = int(nm[0])
	m = int(nm[1])
	grid = []
	for j in range(0, n):
		temp1 = []
		for k in range(0, n):
			temp2 = []
			for l in range(0, n):
				temp2.append(0)
			temp1.append(temp2)
		grid.append(temp1)
	updates = {}
	for op in range(0, m):
		ins = input()
		temp = ins.split(' ')
		if 'UPDATE' in temp:
			w = int(temp[-1])
			x = int(temp[1]) - 1
			y = int(temp[2]) - 1
			z = int(temp[3]) - 1
			grid[x][y][z] = w
			updates[str(x) + ',' + str(y) + ',' + str(z)] = {'coord': [x, y, z], 'weight': w}
		if 'QUERY' in temp:
			x1 = int(temp[1]) - 1
			y1 = int(temp[2]) - 1
			z1 = int(temp[3]) - 1
			x2 = int(temp[4]) - 1
			y2 = int(temp[5]) - 1
			z2 = int(temp[6]) - 1
			total = 0
			for (k, u) in updates.items():
				coord = u['coord']
				if coord[0] >= x1 and coord[0] <= x2 and (coord[1] >= y1) and (coord[1] <= y2) and (coord[2] >= z1) and (coord[2] <= z2):
					total += u['weight']
			print(total)


from itertools import product
T = int(input())
for t in range(T):
	(N, M) = tuple(map(int, input().split()))
	cube = {}
	for m in range(M):
		line = input().split()
		query = line.pop(0)
		if query == 'UPDATE':
			(x, y, z, W) = list(map(int, line))
			cube[x, y, z] = W
		elif query == 'QUERY':
			(x1, y1, z1, x2, y2, z2) = tuple(map(int, line))
			print(sum((W if x1 <= x <= x2 and y1 <= y <= y2 and (z1 <= z <= z2) else 0 for ((x, y, z), W) in cube.items())))


test_cases = int(input())
for i in range(test_cases):
	(n, queries) = [int(x) for x in input().split()]
	sparse_list = dict()
	for j in range(queries):
		query = input().split()
		if query[0] == 'UPDATE':
			query = [int(x) for x in query[1:]]
			(x, y, z, value) = query
			sparse_list[x, y, z] = value
		elif query[0] == 'QUERY':
			query = [int(x) for x in query[1:]]
			(x1, y1, z1, x2, y2, z2) = query
			sum = 0
			for (key, value) in sparse_list.items():
				if x1 <= key[0] <= x2 and y1 <= key[1] <= y2 and (z1 <= key[2] <= z2):
					sum += value
			print(sum)


class CubeBinaryTree:

	def __init__(self, n):
		self.binarytree = [[[0 for k in range(n + 1)] for j in range(n + 1)] for i in range(n + 1)]
		self.lenght = n

	def update(self, x, y, z, val):
		while z <= self.lenght:
			xtemp = x
			while xtemp <= self.lenght:
				ytemp = y
				while ytemp <= self.lenght:
					self.binarytree[xtemp][ytemp][z] += val
					ytemp += ytemp & -ytemp
				xtemp += xtemp & -xtemp
			z += z & -z

	def sumToZeroAxis(self, x, y, z):
		sum = 0
		while z > 0:
			xtemp = x
			while xtemp > 0:
				ytemp = y
				while ytemp > 0:
					sum += self.binarytree[xtemp][ytemp][z]
					ytemp -= ytemp & -ytemp
				xtemp -= xtemp & -xtemp
			z -= z & -z
		return sum

class CubeSummation:

	def __init__(self, n):
		self.cubeBinaryTree = CubeBinaryTree(n)

	def query(self, x0, y0, z0, x, y, z):
		val1 = self.cubeBinaryTree.sumToZeroAxis(x, y, z) - self.cubeBinaryTree.sumToZeroAxis(x0 - 1, y, z) - self.cubeBinaryTree.sumToZeroAxis(x, y0 - 1, z) + self.cubeBinaryTree.sumToZeroAxis(x0 - 1, y0 - 1, z)
		val2 = self.cubeBinaryTree.sumToZeroAxis(x, y, z0 - 1) - self.cubeBinaryTree.sumToZeroAxis(x0 - 1, y, z0 - 1) - self.cubeBinaryTree.sumToZeroAxis(x, y0 - 1, z0 - 1) + self.cubeBinaryTree.sumToZeroAxis(x0 - 1, y0 - 1, z0 - 1)
		return val1 - val2

	def update(self, x, y, z, val):
		val1 = self.cubeBinaryTree.sumToZeroAxis(x, y, z) - self.cubeBinaryTree.sumToZeroAxis(x - 1, y, z) - self.cubeBinaryTree.sumToZeroAxis(x, y - 1, z) + self.cubeBinaryTree.sumToZeroAxis(x - 1, y - 1, z)
		val2 = self.cubeBinaryTree.sumToZeroAxis(x, y, z - 1) - self.cubeBinaryTree.sumToZeroAxis(x - 1, y, z - 1) - self.cubeBinaryTree.sumToZeroAxis(x, y - 1, z - 1) + self.cubeBinaryTree.sumToZeroAxis(x - 1, y - 1, z - 1)
		self.cubeBinaryTree.update(x, y, z, val - val1 + val2)

	def match(self):
		line = input()
		data = line.split()
		types = data[0]
		if types == 'QUERY':
			print(self.query(int(data[1]), int(data[2]), int(data[3]), int(data[4]), int(data[5]), int(data[6])))
		else:
			self.update(int(data[1]), int(data[2]), int(data[3]), int(data[4]))
cases = int(input())
while cases != 0:
	line = input()
	data = line.split()
	n = int(data[0])
	m = int(data[1])
	cubesumm = CubeSummation(n)
	while m != 0:
		cubesumm.match()
		m -= 1
	cases -= 1


num_test = int(input())
for _ in range(num_test):
	(n, m) = list(map(int, input().split()))
	three_d_dict = {}
	for x in range(m):
		r_input = list(map(int, input().split()[1:]))
		if len(r_input) == 4:
			indices = (r_input[0], r_input[1])
			slice = r_input[2]
			value = r_input[3]
			if slice not in three_d_dict:
				three_d_dict[slice] = {indices: value}
			else:
				three_d_dict[slice].update({indices: value})
		else:
			query = r_input
			m_2d_start = (query[0], query[1])
			m_2d_end = (query[3], query[4])
			slice_start = query[2]
			slice_end = query[5]
			total = 0
			for x in range(slice_start, slice_end + 1):
				if x in three_d_dict:
					total += sum([v for (k, v) in three_d_dict[x].items() if (k[0] >= m_2d_start[0] and k[1] >= m_2d_start[1]) and (k[0] <= m_2d_end[0] and k[1] <= m_2d_end[1])])
			print(total)


t = int(input())
for ti in range(t):
	(n, m) = map(int, input().split())
	ps = {}
	for qi in range(m):
		toks = input().split()
		if toks[0] == 'UPDATE':
			(x, y, z, v) = map(int, toks[1:])
			ps[x, y, z] = v
		else:
			(x1, y1, z1, x2, y2, z2) = map(int, toks[1:])
			s = 0
			for ((x, y, z), v) in ps.items():
				if x >= x1 and y >= y1 and (z >= z1) and (x <= x2) and (y <= y2) and (z <= z2):
					s += v
			print(s)


def assert_arg_count(argc, args):
	assert len(args) == argc, 'args needs to be exactly %d was %d' % (argc, len(args))

def update(updated, matrix, args):
	assert_arg_count(4, args)
	x = args[0] - 1
	y = args[1] - 1
	z = args[2] - 1
	w = args[3]
	matrix[x][y][z] = w
	updated.add((x, y, z))

def query(updated, matrix, args):
	assert_arg_count(6, args)

	def find_in_bounds(updated, args):
		(x1, y1, z1, x2, y2, z2) = args
		coords = []
		for (x, y, z) in updated:
			if x >= x1 - 1 and x < x2 and (y >= y1 - 1) and (y < y2) and (z >= z1 - 1) and (z < z2):
				coords.append((x, y, z))
		return coords
	coords = find_in_bounds(updated, args)
	sum = 0
	for (x, y, z) in coords:
		sum += matrix[x][y][z]
	print(sum)

def exec_command(line, updated, matrix):

	def to_int(args):
		return [int(x) for x in args]
	args = to_int(line.split(' ')[1:])
	if line.startswith('UPDATE'):
		update(updated, matrix, args)
	elif line.startswith('QUERY'):
		query(updated, matrix, args)
	else:
		assert false

def create_matrix(n):
	return [[[0 for k in range(n)] for j in range(n)] for i in range(n)]

def main():
	test_cases = int(input())
	for case in range(0, test_cases):
		line = input()
		n = int(line.split(' ')[0])
		m = int(line.split(' ')[1])
		updated = set()
		matrix = create_matrix(n)
		for k in range(m):
			exec_command(input(), updated, matrix)
main()


__author__ = 'Ward'
import sys

class FT:

	def __init__(self, N):
		self.data = [[[0] * (N + 1) for i in range(0, N + 1)] for j in range(0, N + 1)]

	def add(self, x, y, z, w):
		X = x
		while X <= N:
			Y = y
			while Y <= N:
				Z = z
				while Z <= N:
					self.data[X][Y][Z] += w
					Z += Z & -Z
				Y += Y & -Y
			X += X & -X

	def read(self, x, y, z):
		Ans = 0
		X = x
		while X > 0:
			Y = y
			while Y > 0:
				Z = z
				while Z > 0:
					Ans += self.data[X][Y][Z]
					Z -= Z & -Z
				Y -= Y & -Y
			X -= X & -X
		return Ans

	def query(self, x1, y1, z1, x2, y2, z2):
		return self.read(x2, y2, z2) - self.read(x1 - 1, y2, z2) - self.read(x2, y1 - 1, z2) - self.read(x2, y2, z1 - 1) + self.read(x1 - 1, y1 - 1, z2) + self.read(x1 - 1, y2, z1 - 1) + self.read(x2, y1 - 1, z1 - 1) - self.read(x1 - 1, y1 - 1, z1 - 1)

	def update(self, x, y, z, w):
		prev = self.query(x, y, z, x, y, z)
		self.add(x, y, z, w - prev)
T = int(sys.stdin.readline())
for i in range(0, T):
	(N, M) = map(int, sys.stdin.readline().split())
	tree = FT(N)
	for q in range(0, M):
		Input = sys.stdin.readline().split()
		if Input[0] == 'UPDATE':
			(x, y, z, W) = map(int, Input[1:])
			tree.update(x, y, z, W)
		if Input[0] == 'QUERY':
			(x1, y1, z1, x2, y2, z2) = map(int, Input[1:])
			print(tree.query(x1, y1, z1, x2, y2, z2))


import sys
fname = ''

def Update(arr, x, y, z, v):
	key = str(x) + '-' + str(y) + '-' + str(z)
	arr[key] = v

def Query(arr, x1, y1, z1, x2, y2, z2):
	c = 0
	for (k, v) in arr.items():
		(x, y, z) = [int(i) for i in k.split('-')]
		if x >= x1 and x <= x2 and (y >= y1) and (y <= y2) and (z >= z1) and (z <= z2):
			c += v
	return c

def getFileHandle():
	if fname:
		fh = open(fname, 'r')
	else:
		fh = sys.stdin
	return fh
fh = getFileHandle()
T = int(fh.readline())
for t in range(T):
	(N, M) = [int(i) for i in fh.readline().split()]
	dArray = {}
	for q in range(M):
		op = fh.readline().split()
		params = [int(x) for x in op[1:]]
		if op[0] == 'UPDATE':
			Update(dArray, *params)
		elif op[0] == 'QUERY':
			rtn = Query(dArray, *params)
			print(rtn)
		else:
			print('Invalid Operations:', op[0])
fh.close()


reps = int(input())
sums = []
for _ in range(reps):
	(n, ops) = map(int, input().split())
	a = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
	updated = set()
	for op in range(ops):
		s = input()
		if s[0] == 'U':
			(x, y, z, value) = list(map(int, s[6:].split()))
			a[x - 1][y - 1][z - 1] = value
			updated.add((x - 1, y - 1, z - 1))
		else:
			suma = 0
			p = list(map(int, s[5:].split()))
			(x1, y1, z1, x2, y2, z2) = p
			cells = []
			for (x, y, z) in updated:
				if x1 - 1 <= x and x2 > x and (y1 - 1 <= y) and (y2 > y) and (z >= z1 - 1) and (z < z2):
					cells.append((x, y, z))
			for (x, y, z) in cells:
				suma += a[x][y][z]
			sums.append(suma)
for i in sums:
	print(i)


class Cube:

	def __init__(self, n):
		self._n = n
		self._values = dict()

	def update(self, x, y, z, value):
		if x not in self._values:
			self._values[x] = dict()
		if y not in self._values[x]:
			self._values[x][y] = dict()
		self._values[x][y][z] = value

	def _sum(self, x1, y1, z1, x2, y2, z2):
		return sum(map(lambda x: self._sumx(x, y1, z1, y2, z2), (x for x in self._values if x1 <= x <= x2)))

	def _sumx(self, x, y1, z1, y2, z2):
		return sum(map(lambda y: self._sumxy(x, y, z1, z2), (y for y in self._values[x] if y1 <= y <= y2)))

	def _sumxy(self, x, y, z1, z2):
		return sum((v for (z, v) in self._values[x][y].items() if z1 <= z <= z2))

	def query(self, x1, y1, z1, x2, y2, z2):
		s = self._sum(x1, y1, z1, x2, y2, z2)
		print(s)

def main():
	t = int(input())
	for _ in range(t):
		(n, m) = list(map(int, input().split()))
		cube = Cube(n)
		for _ in range(m):
			(qtype, *args) = input().split()
			args = map(int, args)
			if qtype == 'UPDATE':
				cube.update(*args)
			elif qtype == 'QUERY':
				cube.query(*args)
main()


def updateFen(N, Fen, x, y, z, val):
	while x <= N:
		tempy = y
		while tempy <= N:
			tempz = z
			while tempz <= N:
				Fen[x][tempy][tempz] += val
				tempz += tempz & -tempz
			tempy += tempy & -tempy
		x += x & -x

def GetFenSum(Fen, x, y, z):
	sum = 0
	while x > 0:
		tempy = y
		while tempy > 0:
			tempz = z
			while tempz > 0:
				sum += Fen[x][tempy][tempz]
				tempz -= tempz & -tempz
			tempy -= tempy & -tempy
		x -= x & -x
	return sum

def FenRangeSum(Fen, x1, y1, z1, x2, y2, z2):
	return GetFenSum(Fen, x2, y2, z2) + GetFenSum(Fen, x2, y1 - 1, z1 - 1) + GetFenSum(Fen, x1 - 1, y2, z1 - 1) + GetFenSum(Fen, x1 - 1, y1 - 1, z2) - GetFenSum(Fen, x2, y2, z1 - 1) - GetFenSum(Fen, x2, y1 - 1, z2) - GetFenSum(Fen, x1 - 1, y2, z2) - GetFenSum(Fen, x1 - 1, y1 - 1, z1 - 1)
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	Tree = [[[0 for z in range(n + 1)] for y in range(n + 1)] for x in range(n + 1)]
	for _ in range(m):
		query = input().split()
		if query[0] == 'UPDATE':
			(x, y, z, new_val) = [int(query[i]) for i in range(1, 5)]
			current_val = FenRangeSum(Tree, x, y, z, x, y, z)
			update_val = new_val - current_val
			updateFen(n, Tree, x, y, z, update_val)
		elif query[0] == 'QUERY':
			(x1, y1, z1, x2, y2, z2) = [int(query[i]) for i in range(1, 7)]
			print(FenRangeSum(Tree, x1, y1, z1, x2, y2, z2))


from collections import defaultdict
T = int(input())
for _ in range(T):
	(n, m) = [int(i) for i in input().split()]
	cube = defaultdict(lambda : defaultdict(lambda : defaultdict(lambda : 0)))
	for _ in range(m):
		q = input().split()
		q_type = q.pop(0)
		if q_type == 'UPDATE':
			(x, y, z, W) = [int(i) for i in q]
			cube[x][y][z] = W
		elif q_type == 'QUERY':
			(x1, y1, z1, x2, y2, z2) = [int(i) for i in q]
			total = 0
			for x in cube:
				if x >= x1 and x <= x2:
					for y in cube[x]:
						if y >= y1 and y <= y2:
							for (z, v) in cube[x][y].items():
								if z >= z1 and z <= z2:
									total += v
			print(total)
		else:
			raise Exception('Invalid query type:{}'.format(q_type))


def solve(Q):
	cube = {}
	for q in Q:
		if q[0] == 'UPDATE':
			(x, y, z, w) = q[1:]
			if x not in cube:
				cube[x] = {y: {z: w}}
			elif y not in cube[x]:
				cube[x][y] = {z: w}
			else:
				cube[x][y][z] = w
		else:
			(x1, y1, z1, x2, y2, z2) = q[1:]
			total = 0
			for x in cube:
				if not x1 <= x <= x2:
					continue
				for y in cube[x]:
					if not y1 <= y <= y2:
						continue
					for z in cube[x][y]:
						if z1 <= z <= z2:
							total += cube[x][y][z]
			yield total
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	Q = []
	for _ in range(M):
		q = input().split()
		Q.append(q[:1] + list(map(int, q[1:])))
	print('\n'.join(map(str, solve(Q))))


T = int(input())
for t in range(T):
	(N, M) = [int(x) for x in input().split()]
	a = {}
	for m in range(M):
		s = input().split()
		if s[0][0] == 'U':
			(p, q, r, w) = s[1:]
			a[int(p), int(q), int(r)] = int(w)
		else:
			(x1, y1, z1, x2, y2, z2) = s[1:]
			sm = sum((x for ((p, q, r), x) in a.items() if int(x1) <= p <= int(x2) and int(y1) <= q <= int(y2) and (int(z1) <= r <= int(z2))))
			print(sm)


import sys
sys.setrecursionlimit(1000000)

class Node:

	def __init__(self, x1, x2, y1, y2, z1, z2):
		(self.x1, self.x2) = (x1, x2)
		(self.y1, self.y2) = (y1, y2)
		(self.z1, self.z2) = (z1, z2)
		self.s = 0
		self.f = [None] * 8

def update(r, x, y, z, w):
	if r.x1 == r.x2 and r.y1 == r.y2 and (r.z1 == r.z2):
		r.s = w
		return
	mx = (r.x1 + r.x2) // 2
	my = (r.y1 + r.y2) // 2
	mz = (r.z1 + r.z2) // 2
	if r.x1 <= x <= mx and r.y1 <= y <= my and (r.z1 <= z <= mz):
		if not r.f[0]:
			r.f[0] = Node(r.x1, mx, r.y1, my, r.z1, mz)
		update(r.f[0], x, y, z, w)
	elif r.x1 <= x <= mx and r.y1 <= y <= my and (mz + 1 <= z <= r.z2):
		if not r.f[1]:
			r.f[1] = Node(r.x1, mx, r.y1, my, mz + 1, r.z2)
		update(r.f[1], x, y, z, w)
	elif r.x1 <= x <= mx and my + 1 <= y <= r.y2 and (r.z1 <= z <= mz):
		if not r.f[2]:
			r.f[2] = Node(r.x1, mx, my + 1, r.y2, r.z1, mz)
		update(r.f[2], x, y, z, w)
	elif r.x1 <= x <= mx and my + 1 <= y <= r.y2 and (mz + 1 <= z <= r.z2):
		if not r.f[3]:
			r.f[3] = Node(r.x1, mx, my + 1, r.y2, mz + 1, r.z2)
		update(r.f[3], x, y, z, w)
	elif mx + 1 <= x <= r.x2 and r.y1 <= y <= my and (r.z1 <= z <= mz):
		if not r.f[4]:
			r.f[4] = Node(mx + 1, r.x2, r.y1, my, r.z1, mz)
		update(r.f[4], x, y, z, w)
	elif mx + 1 <= x <= r.x2 and r.y1 <= y <= my and (mz + 1 <= z <= r.z2):
		if not r.f[5]:
			r.f[5] = Node(mx + 1, r.x2, r.y1, my, mz + 1, r.z2)
		update(r.f[5], x, y, z, w)
	elif mx + 1 <= x <= r.x2 and my + 1 <= y <= r.y2 and (r.z1 <= z <= mz):
		if not r.f[6]:
			r.f[6] = Node(mx + 1, r.x2, my + 1, r.y2, r.z1, mz)
		update(r.f[6], x, y, z, w)
	elif mx + 1 <= x <= r.x2 and my + 1 <= y <= r.y2 and (mz + 1 <= z <= r.z2):
		if not r.f[7]:
			r.f[7] = Node(mx + 1, r.x2, my + 1, r.y2, mz + 1, r.z2)
		update(r.f[7], x, y, z, w)
	r.s = 0
	for i in range(8):
		if r.f[i]:
			r.s += r.f[i].s

def query(r, x1, x2, y1, y2, z1, z2):
	if not r:
		return 0
	if x1 == r.x1 and x2 == r.x2 and (y1 == r.y1) and (y2 == r.y2) and (z1 == r.z1) and (z2 == r.z2):
		return r.s
	ans = 0
	mx = (r.x1 + r.x2) // 2
	my = (r.y1 + r.y2) // 2
	mz = (r.z1 + r.z2) // 2
	if x1 <= mx and y1 <= my and (z1 <= mz):
		ans += query(r.f[0], x1, min(mx, x2), y1, min(my, y2), z1, min(mz, z2))
	if x1 <= mx and y1 <= my and (z2 > mz):
		ans += query(r.f[1], x1, min(mx, x2), y1, min(my, y2), max(mz + 1, z1), z2)
	if x1 <= mx and y2 > my and (z1 <= mz):
		ans += query(r.f[2], x1, min(mx, x2), max(my + 1, y1), y2, z1, min(mz, z2))
	if x1 <= mx and y2 > my and (z2 > mz):
		ans += query(r.f[3], x1, min(mx, x2), max(my + 1, y1), y2, max(mz + 1, z1), z2)
	if x2 > mx and y1 <= my and (z1 <= mz):
		ans += query(r.f[4], max(mx + 1, x1), x2, y1, min(my, y2), z1, min(mz, z2))
	if x2 > mx and y1 <= my and (z2 > mz):
		ans += query(r.f[5], max(mx + 1, x1), x2, y1, min(my, y2), max(mz + 1, z1), z2)
	if x2 > mx and y2 > my and (z1 <= mz):
		ans += query(r.f[6], max(mx + 1, x1), x2, max(my + 1, y1), y2, z1, min(mz, z2))
	if x2 > mx and y2 > my and (z2 > mz):
		ans += query(r.f[7], max(mx + 1, x1), x2, max(my + 1, y1), y2, max(mz + 1, z1), z2)
	return ans
for _ in range(int(input().strip())):
	[n, m] = map(int, input().strip().split())
	r = Node(1, n, 1, n, 1, n)
	for _ in range(m):
		s = input().strip().split()
		if s[0] == 'UPDATE':
			update(r, int(s[1]), int(s[2]), int(s[3]), int(s[4]))
		else:
			print(query(r, int(s[1]), int(s[4]), int(s[2]), int(s[5]), int(s[3]), int(s[6])))


import sys

def query(P, q):
	(x1, y1, z1, x2, y2, z2) = q
	s = 0
	for ((x, y, z), w) in P.items():
		if x in range(x1, x2 + 1) and y in range(y1, y2 + 1) and (z in range(z1, z2 + 1)):
			s += w
	return s
T = int(sys.stdin.readline())
for i in range(T):
	(N, M) = (int(j) for j in sys.stdin.readline().split())
	P = dict()
	Q = []
	for j in range(M):
		line = sys.stdin.readline().rstrip().split()
		if line[0] == 'UPDATE':
			(x, y, z, w) = (int(k) - 1 for k in line[1:])
			P[x, y, z] = w + 1
		else:
			(x1, y1, z1, x2, y2, z2) = (int(k) - 1 for k in line[1:])
			Q.append((x1, y1, z1, x2, y2, z2))
			print(query(P, (x1, y1, z1, x2, y2, z2)))


def do_update(slices, action):
	(x, y, z, W) = (int(a) for a in action)
	rel_slice = slices[z]
	for i in range(1, len(slices)):
		for j in range(1, len(slices)):
			if i >= x or j >= y:
				rel_slice[i, j] += W

def do_update_cube(cube, action):
	(x, y, z, W) = (int(a) for a in action)
	cube[x, y, z] = W

def do_query(slices, action):
	sum = 0
	(x1, y1, z1, x2, y2, z2) = (int(a) for a in action)
	for k in range(z1, z2 + 1):
		rel_slice = slices[k]
		sum += rel_slice[x2, y2] + rel_slice[x1 - 1, y1 - 1] - rel_slice[x1 - 1, y2] - rel_slice[x2, y1 - 1]
	if sum < 0:
		sum *= -1
	return sum

def do_query_cube(cube, action):
	sum = 0
	(x1, y1, z1, x2, y2, z2) = (int(a) for a in action)
	for coord in cube.keys():
		if coord[0] in range(x1, x2 + 1):
			if coord[1] in range(y1, y2 + 1):
				if coord[2] in range(z1, z2 + 1):
					sum += cube[coord]
	return sum

def make_slices(size):
	N = size + 1
	return [{(i, j): 0 for i in range(N) for j in range(N)} for k in range(N)]
num_cases = int(input())
for _ in range(num_cases):
	(N, M) = (int(a) for a in input().split(' '))
	cube = dict()
	for x in range(M):
		action = input().split(' ')
		if action[0] == 'UPDATE':
			do_update_cube(cube, action[1:])
		if action[0] == 'QUERY':
			print(do_query_cube(cube, action[1:]))


T = int(input().strip())
for t in range(T):
	(N, M) = map(lambda x: int(x), input().strip().split(' '))
	arr = []
	queries = {}
	for m in range(M):
		tmp = input().strip().split()
		for i in range(1, len(tmp)):
			tmp[i] = int(tmp[i])
		arr.append(tuple(tmp))
		if arr[m][0] == 'QUERY':
			queries[arr[m]] = 0
	data = [[[0] * (N + 1) for i in range(N + 1)] for j in range(N + 1)]
	for line in arr:
		if line[0] == 'QUERY':
			print(queries[line])
		else:
			for key in queries:
				if key[1] <= line[1] and key[4] >= line[1] and (key[2] <= line[2]) and (key[5] >= line[2]) and (key[3] <= line[3]) and (key[6] >= line[3]):
					queries[key] += line[4] - data[line[1]][line[2]][line[3]]
			data[line[1]][line[2]][line[3]] = line[4]


from collections import defaultdict
import sys

def query(cube, x1, y1, z1, x2, y2, z2):
	answer = 0
	for x in cube.keys():
		if x >= x1 and x <= x2:
			for y in cube[x].keys():
				if y >= y1 and y <= y2:
					for z in cube[x][y].keys():
						if z >= z1 and z <= z2:
							answer = answer + cube[x][y][z]
	return answer
input = sys.stdin.read().split('\n')
tests = int(input.pop(0))
for test in range(0, tests):
	(cube_size, ops) = [int(x) for x in input.pop(0).split(' ')]
	cube = defaultdict(lambda : defaultdict(dict))
	for op in range(0, ops):
		line = input.pop(0)
		if 'UPDATE' in line:
			(x, y, z, w) = [int(x) for x in line[7:].split(' ')]
			if x > 0 and y > 0 and (z > 0) and (x <= cube_size) and (y <= cube_size) and (z <= cube_size):
				cube[x][y][z] = w
		else:
			(x1, y1, z1, x2, y2, z2) = [int(x) for x in line[6:].split(' ')]
			print(query(cube, x1, y1, z1, x2, y2, z2))


def execute(command):
	com = command.split()
	if com[0] == 'UPDATE':
		key = tuple(map(int, com[1:4]))
		value = int(com[4])
		if key not in vis:
			vis[key] = value
			lst.append(tuple(map(int, com[1:])))
		else:
			oldval = vis[key]
			lst.remove(key + (oldval,))
			vis[key] = value
			lst.append(key + (value,))
		return
	else:
		mysum = 0
		(x1, y1, z1, x2, y2, z2) = list(map(int, com[1:]))
		for item in lst:
			if x1 <= item[0] <= x2 and y1 <= item[1] <= y2 and (z1 <= item[2] <= z2):
				mysum += item[3]
	print(mysum)
t = int(input().strip())
for i in range(t):
	lst = []
	vis = dict()
	(n, m) = [int(item) for item in input().strip().split()]
	for j in range(m):
		command = input().strip()
		execute(command)


def assert_arg_count(argc, args):
	assert len(args) == argc, 'args needs to be exactly %d was %d' % (argc, len(args))

def update(updated, matrix, args):
	assert_arg_count(4, args)
	x = args[0] - 1
	y = args[1] - 1
	z = args[2] - 1
	w = args[3]
	matrix[x][y][z] = w
	updated.add((x, y, z))

def query(updated, matrix, args):
	assert_arg_count(6, args)

	def find_in_bounds(updated, args):
		(x1, y1, z1, x2, y2, z2) = args
		coords = []
		for (x, y, z) in updated:
			if x >= x1 - 1 and x < x2 and (y >= y1 - 1) and (y < y2) and (z >= z1 - 1) and (z < z2):
				coords.append((x, y, z))
		return coords
	coords = find_in_bounds(updated, args)
	sum = 0
	for (x, y, z) in coords:
		sum += matrix[x][y][z]
	print(sum)

def exec_command(line, updated, matrix):

	def to_int(args):
		return [int(x) for x in args]
	args = to_int(line.split(' ')[1:])
	if line.startswith('UPDATE'):
		update(updated, matrix, args)
	elif line.startswith('QUERY'):
		query(updated, matrix, args)
	else:
		assert false

def create_matrix(n):
	return [[[0 for k in range(n)] for j in range(n)] for i in range(n)]

def main():
	test_cases = int(input())
	for case in range(0, test_cases):
		line = input()
		n = int(line.split(' ')[0])
		m = int(line.split(' ')[1])
		updated = set()
		matrix = create_matrix(n)
		for k in range(m):
			exec_command(input(), updated, matrix)
main()


t = int(input().strip())
for case in range(t):
	(n, m) = [int(i) for i in input().strip().split()]
	updates = {}
	for i in range(m):
		line = input().strip().split()
		if line[0] == 'UPDATE':
			(x, y, z, w) = [int(i) for i in line[1:]]
			updates[x, y, z] = w
		elif line[0] == 'QUERY':
			(x1, y1, z1, x2, y2, z2) = [int(i) for i in line[1:]]
			summation = 0
			for (x, y, z) in updates:
				if x1 <= x <= x2 and y1 <= y <= y2 and (z1 <= z <= z2):
					summation += updates[x, y, z]
			print(summation)


t = int(input().strip())
for _ in range(t):
	(n, m) = [int(x) for x in input().strip().split(' ')]
	V = {}
	for _ in range(m):
		command = input().strip()
		if command.startswith('UPDATE'):
			(x, y, z, w) = [int(x) for x in command.split(' ')[1:]]
			V[x, y, z] = w
		elif command.startswith('QUERY'):
			(x1, y1, z1, x2, y2, z2) = [int(x) for x in command.split(' ')[1:]]
			total = 0
			for ((x, y, z), value) in V.items():
				if x >= x1 and x <= x2 and (y >= y1) and (y <= y2) and (z >= z1) and (z <= z2):
					total += value
			print(total)
		else:
			raise ValueError('Invalid command')


class Node(object):

	def __init__(self, x, y, z, value):
		self.x = x
		self.y = y
		self.z = z
		self.value = value

class Cube(object):

	def __init__(self, size):
		self._by_x = []
		self._by_y = []
		self._by_z = []

	def update(self, x, y, z, value):
		xs = self._find_one(x, self._by_x)
		ys = self._find_one(y, self._by_y)
		zs = self._find_one(z, self._by_z)
		nodes = xs.intersection(ys.intersection(zs))
		if nodes:
			nodes.pop().value = value
		else:
			node = Node(x, y, z, value)
			if not xs:
				self._by_x.append((x, set([node])))
			else:
				xs.add(node)
			if not ys:
				self._by_y.append((y, set([node])))
			else:
				ys.add(node)
			if not zs:
				self._by_z.append((z, set([node])))
			else:
				zs.add(node)

	def _find_one(self, value, lis):
		for (index, nodes) in lis:
			if index == value:
				return nodes
		return set()

	def query(self, x1, y1, z1, x2, y2, z2):
		xs = self._find_many(x1, x2, self._by_x)
		ys = self._find_many(y1, y2, self._by_y)
		zs = self._find_many(z1, z2, self._by_z)
		nodes = xs.intersection(ys.intersection(zs))
		return sum((node.value for node in nodes)) if nodes else 0

	def _find_many(self, val1, val2, lis):
		ret = set()
		(lower, upper) = (min(val1, val2), max(val1, val2))
		for (index, nodes) in lis:
			if index <= upper and index >= lower:
				ret.update(nodes)
		return ret
for _ in range(int(input().strip())):
	(size, num_operations) = input().strip().split(' ')
	(size, num_operations) = (int(size), int(num_operations))
	cube = Cube(size)
	for _ in range(num_operations):
		ip = input().strip()
		ips = ip.split(' ')
		args = [int(x) - 1 for x in ips[1:]]
		if ips[0] == 'UPDATE':
			args[-1] += 1
			cube.update(*args)
		else:
			print(cube.query(*args))


_bit = list()
_olds = list()
_size = 0

def init(size):
	global _bit, _olds, _size
	_bit = [[[0] * (size + 1) for _ in range(size + 1)] for _ in range(size + 1)]
	_olds = [[[0] * (size + 1) for _ in range(size + 1)] for _ in range(size + 1)]
	_size = size + 1

def update(x, y, z, w):
	global _bit, _olds, _size
	v = w - _olds[z][y][x]
	_olds[z][y][x] = w
	(_z, _y, _x) = (z, y, x)
	while _z < _size:
		_y = y
		while _y < _size:
			_x = x
			while _x < _size:
				_bit[_z][_y][_x] += v
				_x += _x & -_x
			_y += _y & -_y
		_z += _z & -_z

def read(x, y, z):
	global _bit, _olds, _size
	if 0 in (x, y, z):
		return 0
	res = 0
	(_z, _y, _x) = (z, y, x)
	while _z > 0:
		_y = y
		while _y > 0:
			_x = x
			while _x > 0:
				res += _bit[_z][_y][_x]
				_x -= _x & -_x
			_y -= _y & -_y
		_z -= _z & -_z
	return res
T = int(input())
for _ in range(T):
	(N, Q) = tuple(map(int, input().strip().split()))
	init(N)
	for _ in range(Q):
		stin = list(input().strip().split())
		op = stin[0]
		if op == 'UPDATE':
			(x, y, z, w) = tuple(map(int, stin[1:]))
			update(x, y, z, w)
		else:
			(x0, y0, z0, x1, y1, z1) = tuple(map(int, stin[1:]))
			(x0, y0, z0) = (x0 - 1, y0 - 1, z0 - 1)
			res = read(x1, y1, z1)
			res -= read(x1, y1, z0) + read(x1, y0, z1) + read(x0, y1, z1)
			res += read(x1, y0, z0) + read(x0, y1, z0) + read(x0, y0, z1)
			res -= read(x0, y0, z0)
			print(res)


N = 101

def f1():
	return [0] * N

def f2():
	return [f1() for _ in range(N)]

def f3():
	return [f2() for _ in range(N)]

def f1add(f, i, val):
	i += 1
	while i <= N:
		f[i - 1] += val
		i += i & -i

def f2add(f, i, j, val):
	i += 1
	while i <= N:
		f1add(f[i - 1], j, val)
		i += i & -i

def f3add(f, i, j, k, val):
	i += 1
	while i <= N:
		f2add(f[i - 1], j, k, val)
		i += i & -i

def f1get(f, i):
	i += 1
	ans = 0
	while i:
		ans += f[i - 1]
		i -= i & -i
	return ans

def f2get(f, i, j):
	i += 1
	ans = 0
	while i:
		ans += f1get(f[i - 1], j)
		i -= i & -i
	return ans

def f3get(f, i, j, k):
	i += 1
	ans = 0
	while i:
		ans += f2get(f[i - 1], j, k)
		i -= i & -i
	return ans
from itertools import product
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	f = f3()
	for _ in range(m):
		inp = input().split()
		if inp[0] == 'UPDATE':
			(i, j, k, v) = map(int, inp[1:])
			val = 0
			for ((ii, si), (jj, sj), (kk, sk)) in product([(i - 1, -1), (i, 1)], [(j - 1, -1), (j, 1)], [(k - 1, -1), (k, 1)]):
				val += si * sj * sk * f3get(f, ii, jj, kk)
			f3add(f, i, j, k, v - val)
		else:
			(i1, j1, k1, i2, j2, k2) = map(int, inp[1:])
			i1 -= 1
			j1 -= 1
			k1 -= 1
			ans = 0
			for ((i, si), (j, sj), (k, sk)) in product([(i1, -1), (i2, 1)], [(j1, -1), (j2, 1)], [(k1, -1), (k2, 1)]):
				ans += si * sj * sk * f3get(f, i, j, k)
			print(ans)


T = int(input())

def inorder(a, b, c):
	for i in range(3):
		if a[i] > b[i] or b[i] > c[i]:
			return False
	return True
for _ in range(T):
	valuedict = {}
	(N, M) = [int(num) for num in input().split()]
	for _ in range(M):
		i = input().split()
		for j in range(1, len(i)):
			i[j] = int(i[j])
		if i[0] == 'UPDATE':
			w = (i[1], i[2], i[3])
			valuedict[w] = i[4]
		else:
			total = 0
			w1 = (i[1], i[2], i[3])
			w2 = (i[4], i[5], i[6])
			for w in valuedict:
				if inorder(w1, w, w2):
					total += valuedict[w]
			print(total)


for tc in range(int(input().strip())):
	inserted = dict()
	(N, M) = tuple((int(i) for i in input().strip().split(' ')))
	for q in range(M):
		queryParams = [x for x in input().strip().split(' ')]
		iqp = [int(x) for x in queryParams[1:]]
		if queryParams[0] == 'UPDATE':
			inserted[iqp[0], iqp[1], iqp[2]] = iqp[3]
			continue
		s = 0
		for key in inserted:
			if key[0] >= iqp[0] and key[0] <= iqp[3] and (key[1] >= iqp[1]) and (key[1] <= iqp[4]) and (key[2] >= iqp[2]) and (key[2] <= iqp[5]):
				s += inserted[key]
		print(s)


t = int(input().strip())
for i in range(t):
	(n, m) = [int(i) for i in input().strip().split()]
	cube = {}
	for i in range(m):
		inp = input().strip().split()
		if inp[0] == 'UPDATE':
			cube[int(inp[1]), int(inp[2]), int(inp[3])] = int(inp[-1])
		elif inp[0] == 'QUERY':
			(x1, y1, z1, x2, y2, z2) = [int(i) for i in inp[1:]]
			count = 0
			for key in cube.keys():
				if key[0] >= x1 and key[0] <= x2 and (key[1] >= y1) and (key[1] <= y2) and (key[2] >= z1) and (key[2] <= z2):
					count += cube[key]
			print(count)


def is_in_bounds(location, bounds):
	is_in_x = location[0] >= bounds[0] and location[0] <= bounds[3]
	is_in_y = location[1] >= bounds[1] and location[1] <= bounds[4]
	is_in_z = location[2] >= bounds[2] and location[2] <= bounds[5]
	return is_in_x and is_in_y and is_in_z
num_tests = int(input().strip())
for test in range(num_tests):
	(n, m) = [int(arr_temp) for arr_temp in input().strip().split(' ')]
	actions = [input().strip().split(' ') for i in range(m)]
	queries = []
	for action in reversed(actions):
		if action[0] == 'UPDATE':
			location = tuple((int(i) for i in action[1:4]))
			value = int(action[4])
			for query in queries:
				(bounds, updates) = query
				if is_in_bounds(location, bounds) and location not in updates:
					updates[location] = value
		if action[0] == 'QUERY':
			bounds = tuple((int(i) for i in action[1:]))
			queries.append((bounds, {}))
	for query in reversed(queries):
		print(sum(query[1].values()))


def run():
	T = int(input().strip())
	for t in range(T):
		run_test_case()

def run_test_case():
	(N, M) = map(int, input().strip().split())
	points = {}
	for m in range(M):
		line = input().strip().split()
		if line.pop(0) == 'UPDATE':
			(x, y, z, W) = map(int, line)
			points[x, y, z] = W
		else:
			(x1, y1, z1, x2, y2, z2) = map(int, line)
			result = 0
			for (x, y, z) in points:
				if x1 <= x <= x2 and y1 <= y <= y2 and (z1 <= z <= z2):
					result += points[x, y, z]
			print(result)
run()


T = int(input())
for t1 in range(T):
	(N, M) = input().split(' ', 2)
	N = int(N)
	M = int(M)
	Matrix = dict()
	for t2 in range(M):
		cmd = input().split(' ')
		if cmd[0] == 'UPDATE':
			(x, y, z) = (int(cmd[1]), int(cmd[2]), int(cmd[3]))
			Matrix[x, y, z] = int(cmd[4])
		elif cmd[0] == 'QUERY':
			sum = 0
			(x1, y1, z1, x2, y2, z2) = (int(cmd[1]), int(cmd[2]), int(cmd[3]), int(cmd[4]), int(cmd[5]), int(cmd[6]))
			for (k, v) in Matrix.items():
				if k[0] >= x1 and k[0] <= x2 and (k[1] >= y1) and (k[1] <= y2) and (k[2] >= z1) and (k[2] <= z2):
					sum += Matrix[k]
			print(sum)


def normalize(a, b):
	if a < b:
		return (a, b)
	else:
		return (b, a)

def isPointInQuery(p, q1, q2):
	result = True
	for i in range(3):
		if p[i] < q1[i] or p[i] > q2[i]:
			result = False
	return result
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split(' '))
	updates = {}
	for _ in range(M):
		operation = input().split(' ')
		if operation[0] == 'UPDATE':
			(x, y, z, W) = map(int, operation[1:])
			updates[x, y, z] = W
		else:
			(x1, y1, z1, x2, y2, z2) = map(int, operation[1:])
			(x1, x2) = normalize(x1, x2)
			(y1, y2) = normalize(y1, y2)
			(z1, z2) = normalize(z1, z2)
			amount = 0
			for (key, value) in updates.items():
				if isPointInQuery(key, (x1, y1, z1), (x2, y2, z2)):
					amount += value
			print(amount)


def assert_arg_count(argc, args):
	assert len(args) == argc, 'args needs to be exactly %d was %d' % (argc, len(args))

def update(updated, matrix, args):
	assert_arg_count(4, args)
	x = args[0] - 1
	y = args[1] - 1
	z = args[2] - 1
	w = args[3]
	matrix[x][y][z] = w
	updated.add((x, y, z))

def query(updated, matrix, args):
	assert_arg_count(6, args)

	def find_in_bounds(updated, args):
		(x1, y1, z1, x2, y2, z2) = args
		coords = []
		for (x, y, z) in updated:
			if x >= x1 - 1 and x < x2 and (y >= y1 - 1) and (y < y2) and (z >= z1 - 1) and (z < z2):
				coords.append((x, y, z))
		return coords
	coords = find_in_bounds(updated, args)
	sum = 0
	for (x, y, z) in coords:
		sum += matrix[x][y][z]
	print(sum)

def exec_command(line, updated, matrix):

	def to_int(args):
		return [int(x) for x in args]
	args = to_int(line.split(' ')[1:])
	if line.startswith('UPDATE'):
		update(updated, matrix, args)
	elif line.startswith('QUERY'):
		query(updated, matrix, args)
	else:
		assert false

def create_matrix(n):
	return [[[0 for k in range(n)] for j in range(n)] for i in range(n)]

def main():
	test_cases = int(input())
	for case in range(0, test_cases):
		line = input()
		n = int(line.split(' ')[0])
		m = int(line.split(' ')[1])
		updated = set()
		matrix = create_matrix(n)
		for k in range(m):
			exec_command(input(), updated, matrix)
main()


T = int(input().strip())
for t in range(T):
	(N, M) = map(int, input().split(' '))
	arr = {}
	for m in range(M):
		cmd = input().split(' ')
		if cmd[0] == 'UPDATE':
			(x, y, z, w) = map(int, cmd[1:])
			if x in arr:
				if y in arr[x]:
					arr[x][y][z] = w
				else:
					arr[x][y] = {z: w}
			else:
				arr[x] = {y: {z: w}}
		elif cmd[0] == 'QUERY':
			(x1, y1, z1, x2, y2, z2) = map(int, cmd[1:])
			sum_ = 0
			for x in arr:
				if x >= x1 and x <= x2:
					for y in arr[x]:
						if y >= y1 and y <= y2:
							for z in arr[x][y]:
								if z >= z1 and z <= z2:
									sum_ += arr[x][y][z]
			print(sum_)


def testcase():
	(n, m) = map(int, input().split())
	vals = {}
	for _ in range(m):
		op = input()
		if 'UPDATE' in op:
			(_, x, y, z, W) = op.split()
			vals[int(x), int(y), int(z)] = int(W)
		else:
			(_, x1, y1, z1, x2, y2, z2) = op.split()
			res = 0
			for ((x, y, z), W) in vals.items():
				if int(x1) <= x <= int(x2) and int(y1) <= y <= int(y2) and (int(z1) <= z <= int(z2)):
					res += W
			print(res)
for i in range(int(input())):
	testcase()


T = int(input())
for _ in range(T):
	blocks = dict()
	(N, M) = map(int, input().split())
	for _ in range(M):
		command = input().split()
		if command[0] == 'UPDATE':
			(x, y, z) = map(int, command[1:4])
			W = int(command[4])
			blocks[x, y, z] = W
		elif command[0] == 'QUERY':
			(x1, y1, z1) = map(int, command[1:4])
			(x2, y2, z2) = map(int, command[4:7])
			result = 0
			for (x, y, z) in blocks:
				if x1 <= x <= x2 and y1 <= y <= y2 and (z1 <= z <= z2):
					result += blocks[x, y, z]
			print(result)


def update(map, x, y, z, val):
	if x not in map:
		map[x] = {}
	if y not in map[x]:
		map[x][y] = {}
	map[x][y][z] = val
t = int(input())
for t0 in range(t):
	(n, m) = input().split(' ')
	(n, m) = [int(n), int(m)]
	graph = {}
	for m0 in range(m):
		l = input().split(' ')
		if len(l) == 5:
			update(graph, int(l[1]), int(l[2]), int(l[3]), int(l[4]))
		else:
			sum = 0
			(s, x1, y1, z1, x2, y2, z2) = l
			(x1, y1, z1, x2, y2, z2) = [int(x1), int(y1), int(z1), int(x2), int(y2), int(z2)]
			for x in graph:
				if x >= x1 and x2 >= x:
					for y in graph[x]:
						if y >= y1 and y2 >= y:
							for z in graph[x][y]:
								if z >= z1 and z2 >= z:
									sum = sum + graph[x][y][z]
			print(sum)


import collections
for _ in range(int(input())):
	(n, m) = (int(i) for i in input().split())
	matrix = collections.defaultdict(int)
	for __ in range(m):
		command = input().split()
		(command, params) = (command[0], command[1:])
		if command == 'UPDATE':
			(x, y, z, w) = (int(i) for i in params)
			matrix[x, y, z] = w
		elif command == 'QUERY':
			(x1, y1, z1, x2, y2, z2) = (int(i) for i in params)
			print(sum((v for (k, v) in matrix.items() if k[0] in range(x1, x2 + 1) and k[1] in range(y1, y2 + 1) and (k[2] in range(z1, z2 + 1)))))


def assert_arg_count(argc, args):
	assert len(args) == argc, 'args needs to be exactly %d was %d' % (argc, len(args))

def update(updated, matrix, args):
	assert_arg_count(4, args)
	x = args[0] - 1
	y = args[1] - 1
	z = args[2] - 1
	w = args[3]
	matrix[x][y][z] = w
	updated.add((x, y, z))

def query(updated, matrix, args):
	assert_arg_count(6, args)

	def find_in_bounds(updated, args):
		(x1, y1, z1, x2, y2, z2) = args
		coords = []
		for (x, y, z) in updated:
			if x >= x1 - 1 and x < x2 and (y >= y1 - 1) and (y < y2) and (z >= z1 - 1) and (z < z2):
				coords.append((x, y, z))
		return coords
	coords = find_in_bounds(updated, args)
	sum = 0
	for (x, y, z) in coords:
		sum += matrix[x][y][z]
	print(sum)

def exec_command(line, updated, matrix):

	def to_int(args):
		return [int(x) for x in args]
	args = to_int(line.split(' ')[1:])
	if line.startswith('UPDATE'):
		update(updated, matrix, args)
	elif line.startswith('QUERY'):
		query(updated, matrix, args)
	else:
		assert false

def create_matrix(n):
	return [[[0 for k in range(n)] for j in range(n)] for i in range(n)]

def main():
	test_cases = int(input())
	for case in range(0, test_cases):
		line = input()
		n = int(line.split(' ')[0])
		m = int(line.split(' ')[1])
		updated = set()
		matrix = create_matrix(n)
		for k in range(m):
			exec_command(input(), updated, matrix)
main()


import sys
ntests = int(sys.stdin.readline())
for test in range(ntests):
	(n, nops) = list(map(int, sys.stdin.readline().split()))
	cube = {}
	for op in range(nops):
		line = []
		line = sys.stdin.readline().split()
		if line[0] == 'UPDATE':
			cube[tuple((int(x) for x in line[1:4]))] = int(line[4])
		elif line[0] == 'QUERY':
			(x1, y1, z1, x2, y2, z2) = [int(x) for x in line[1:]]
			total = sum([v for (k, v) in cube.items() if x1 <= k[0] and k[0] <= x2 and (y1 <= k[1]) and (k[1] <= y2) and (z1 <= k[2]) and (k[2] <= z2)])
			print(total)


class MyCube:

	def __init__(self, size):
		self.updates = dict()

	def update(self, x, y, z, value):
		self.updates[x, y, z] = value

	def query(self, coord1, coord2):
		return sum((value for (coord, value) in self.updates.items() if between(coord, coord1, coord2)))

def between(coord, coord1, coord2):
	return all((i1 <= i <= i2 for (i, i1, i2) in zip(coord, coord1, coord2)))
t = int(input())
for testcase in range(t):
	(n, m) = [int(i) for i in input().split()]
	cube = MyCube(n)
	for _ in range(m):
		(typ, *numbers) = input().split(' ')
		numbers = [int(i) for i in numbers]
		if typ == 'UPDATE':
			cube.update(*numbers)
		elif typ == 'QUERY':
			coord1 = numbers[:3]
			coord2 = numbers[3:]
			print(cube.query(coord1, coord2))


class Matrix:

	def __init__(self):
		self.matrix = {}

	def update(self, arr):
		arr = [int(x) for x in arr]
		self.matrix.setdefault(arr[0], {}).setdefault(arr[1], {})[arr[2]] = arr[3]

	def query(self, arr):
		mat = self.matrix
		arr = [int(x) for x in arr]
		total = 0
		for x in mat.keys():
			if arr[0] <= x <= arr[3]:
				for y in mat[x].keys():
					if arr[1] <= y <= arr[4]:
						for z in mat[x][y].keys():
							if arr[2] <= z <= arr[5]:
								total += mat[x][y][z]
		return total

	def read_all_queries(self, num_of_queries):
		num_of_queries = int(num_of_queries)
		for _ in range(num_of_queries):
			line = input().split(' ')
			if line[0] == 'UPDATE':
				self.update(line[1:])
			else:
				print(self.query(line[1:]))
num_of_tc = int(input())
for i in range(num_of_tc):
	matrix = Matrix()
	input_line = input().split(' ')
	mtx_limit = input_line[0]
	num_of_queries = input_line[1]
	matrix.read_all_queries(num_of_queries)


testCases = int(input())
for i in range(0, testCases):
	line = input().split(' ')
	dim = int(line[0])
	query_count = int(line[1])
	matrix = {}
	for i in range(0, query_count):
		query = input().split(' ')
		if query[0] == 'UPDATE':
			x_cor = int(query[1])
			y_cor = int(query[2])
			z_cor = int(query[3])
			new_val = int(query[4])
			exist = False
			for k in matrix:
				if k[0] == x_cor and k[1] == y_cor and (k[2] == z_cor):
					matrix[k] = new_val
					exist = True
					pass
				pass
			if not exist:
				matrix[x_cor, y_cor, z_cor] = new_val
				pass
		else:
			total = 0
			startX = min(int(query[1]), int(query[4]))
			endX = max(int(query[1]), int(query[4]))
			startY = min(int(query[2]), int(query[5]))
			endY = max(int(query[2]), int(query[5]))
			startZ = min(int(query[3]), int(query[6]))
			endZ = max(int(query[3]), int(query[6]))
			for key in matrix:
				if key[0] >= startX and key[0] <= endX and (key[1] >= startY) and (key[1] <= endY) and (key[2] >= startZ) and (key[2] <= endZ):
					total += matrix[key]
			print(total)


from collections import defaultdict
T = int(input().strip())
base = defaultdict(int)
for _ in range(T):
	(N, M) = list(map(int, input().strip().split()))
	base.clear()
	for i in range(M):
		c = input().strip().split()
		if c[0] == 'UPDATE':
			(x, y, z, w) = [int(p) for p in c[1:]]
			base[x, y, z] = w
		else:
			r = [int(p) for p in c[1:]]
			(X, Y, Z) = [range(r[i], r[i + 3] + 1) for i in range(3)]
			print(sum((base[x, y, z] for (x, y, z) in base if x in X and y in Y and (z in Z))))


from collections import defaultdict
t = int(input())
for i in range(t):
	dd = defaultdict(int)
	(n, m) = [int(i) for i in input().split(' ')]
	for j in range(m):
		a = input().split(' ')
		if a[0] == 'UPDATE':
			dd[int(a[1]), int(a[2]), int(a[3])] = int(a[4])
		else:
			(x1, y1, z1, x2, y2, z2) = (int(a[1]), int(a[2]), int(a[3]), int(a[4]), int(a[5]), int(a[6]))
			sum = 0
			for k in dd.keys():
				if k[0] >= x1 and k[0] <= x2 and (k[1] >= y1) and (k[1] <= y2) and (k[2] >= z1) and (k[2] <= z2):
					sum += dd[k]
			print(sum)


total_case = int(input())
for case in range(total_case):
	(n, total_q) = [int(s) for s in str(input()).split()]
	data = {}
	for i in range(total_q):
		query = str(input()).split()
		cmd = query[0]
		param = [int(d) for d in query[1:]]
		if cmd == 'UPDATE':
			data[tuple(param[:3])] = param[-1]
		elif cmd == 'QUERY':
			(x, y, z) = param[:3]
			(xx, yy, zz) = param[3:]
			print(sum([v for ((i, j, k), v) in data.items() if i >= x and i <= xx and (j >= y) and (j <= yy) and (k >= z) and (k <= zz)]))


import math
numero = int(input())
for cont in range(0, numero):
	(N, query) = input().split()
	N = int(N)
	query = int(query)
	dizio = {}
	for q in range(0, query):
		a = input().split()
		tipo = a[0]
		if tipo == 'UPDATE':
			x = a[1]
			y = a[2]
			z = a[3]
			val = int(a[4])
			dizio[x + ' ' + y + ' ' + z] = val
		else:
			x_min = int(a[1])
			y_min = int(a[2])
			z_min = int(a[3])
			x_max = int(a[4])
			y_max = int(a[5])
			z_max = int(a[6])
			somma = 0
			for key in dizio.keys():
				(x, y, z) = key.split()
				x = int(x)
				y = int(y)
				z = int(z)
				if x >= x_min and x <= x_max and (y >= y_min) and (y <= y_max) and (z >= z_min) and (z <= z_max):
					somma = somma + dizio[key]
			print(somma)


def update_cube(cube, x, y, z, val):
	cube[x][y][z] = val

def query_cube(cube, x1, y1, z1, x2, y2, z2):
	sumi = 0
	for i in range(x1, x2 + 1):
		for j in range(y1, y2 + 1):
			for k in range(z1, z2 + 1):
				sumi += cube[i][j][k]
	return sumi

def query_dict(dic, x1, y1, z1, x2, y2, z2):
	sumi = 0
	for key in dic.keys():
		(x, y, z) = key
		if x1 <= x <= x2 and y1 <= y <= y2 and (z1 <= z <= z2):
			sumi += dic[key]
	return sumi
tc = int(input())
for _ in range(tc):
	(n, m) = (int(x) for x in input().split())
	cube = []
	for i in range(n + 1):
		matrix = []
		for j in range(n + 1):
			matrix.append([0] * (n + 1))
		cube.append(matrix)
	updates_dict = {}
	for i in range(m):
		(query, *params) = input().split()
		params = [int(x) for x in params]
		if query == 'UPDATE':
			(x, y, z, val) = params
			updates_dict[x, y, z] = val
		elif query == 'QUERY':
			query_res = query_dict(updates_dict, *params)
			print(query_res)


class Matrix:

	def __init__(self, n):
		self.n = n
		self.locations = {}

	def __str__(self):
		response = ''
		for x in self.mat:
			for y in x:
				for z in y:
					response += '{:4} '.format(z)
				response += '\n'
			response += '\n'
		return response

	def get_key(self, x, y, z):
		return z + y * 101 + x * 101 * 101

	def update(self, x, y, z, val):
		key = self.get_key(x, y, z)
		self.locations[key] = (x, y, z, val)

	def query(self, x1, y1, z1, x2, y2, z2):
		sum = 0
		for key in self.locations:
			(x, y, z, val) = self.locations[key]
			if x >= x1 and x <= x2 and (y >= y1) and (y <= y2) and (z >= z1) and (z <= z2):
				sum += val
		return sum
t = int(input())
for i in range(0, t):
	(n, m) = [int(z) for z in input().split(' ')]
	matrix = Matrix(n)
	for j in range(0, m):
		line = input().split(' ')
		if line[0] == 'UPDATE':
			(x, y, z, val) = [int(k) for k in line[1:]]
			matrix.update(x, y, z, val)
		elif line[0] == 'QUERY':
			(x1, y1, z1, x2, y2, z2) = [int(k) for k in line[1:]]
			print(str(matrix.query(x1, y1, z1, x2, y2, z2)))
			pass
		else:
			print('invalid command')


from collections import defaultdict

def isWithinRange(start, end, x):
	return x >= start and x <= end

class Loc:

	def __init__(self, x, y, z):
		self.x = x
		self.y = y
		self.z = z

	def key(self):
		return (self.x, self.y, self.z)

class Cube:

	def __init__(self, start, end):
		self.start = start
		self.end = end

	def containsLoc(self, loc):
		return isWithinRange(self.start.x, self.end.x, loc.x) and isWithinRange(self.start.y, self.end.y, loc.y) and isWithinRange(self.start.z, self.end.z, loc.z)

class Query:

	def __init__(self, queryType):
		self.queryType = queryType

	def update(self, loc, value):
		self.loc = loc
		self.value = value
		return self

	def query(self, cube):
		self.cube = cube
		return self

def processTest(queries):
	values = defaultdict(int)
	cubeCounts = dict()

	def update(count, loc):
		for cube in cubeCounts.keys():
			if cube.containsLoc(loc):
				cubeCounts[cube] += count - values[loc.key()]
		values[loc.key()] = count

	def query(cube):
		print(cubeCounts[cube])

	def getCubes(queries):
		for q in queries:
			if q.queryType == 'U':
				pass
			if q.queryType == 'Q':
				yield q.cube
	for cube in getCubes(queries):
		cubeCounts[cube] = 0
	for q in queries:
		if q.queryType == 'U':
			update(q.value, q.loc)
		if q.queryType == 'Q':
			query(q.cube)
T = int(input())
for i in range(T):
	(N, M) = input().strip().split(' ')
	(N, M) = [int(N), int(M)]
	queries = []
	for j in range(M):
		inputStr = input().strip().split(' ')
		for k in range(1, len(inputStr)):
			inputStr[k] = int(inputStr[k])
		if inputStr[0] == 'UPDATE':
			queries.append(Query('U').update(Loc(*inputStr[1:4]), inputStr[-1]))
		elif inputStr[0] == 'QUERY':
			queries.append(Query('Q').query(Cube(Loc(*inputStr[1:4]), Loc(*inputStr[4:]))))
	processTest(queries)


def update(c, op):
	(x, y, z, v) = op
	if x not in c:
		c[x] = {}
	if y not in c[x]:
		c[x][y] = {}
	if z not in c[x][y]:
		c[x][y][z] = {}
	c[x][y][z] = v
	return c

def query(c, op):
	(x1, y1, z1, x2, y2, z2) = op
	total = 0
	for x in c:
		if x1 <= x <= x2:
			for y in c[x]:
				if y1 <= y <= y2:
					for z in c[x][y]:
						if z1 <= z <= z2:
							total += c[x][y][z]
	return total

def cube(N, M):
	c = {}
	for i in range(M):
		op = input().split()
		if op[0] == 'QUERY':
			print(query(c, map(int, op[1:])))
		else:
			c = update(c, map(int, op[1:]))
cases = int(input())
for i in range(cases):
	(N, M) = input().split()
	cube(int(N), int(M))


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	cube = {}
	for _ in range(M):
		(action, *args) = input().split()
		args = list(map(int, args))
		if action == 'UPDATE':
			(x, y, z, W) = args
			cube[x, y, z] = W
		else:
			(x1, y1, z1, x2, y2, z2) = args
			print(sum((v for ((x, y, z), v) in cube.items() if x1 <= x <= x2 and y1 <= y <= y2 and (z1 <= z <= z2))))