The Cartesian coordinate system is set in the sky. There you can see n stars, the i-th has coordinates (x_{i}, y_{i}), a maximum brightness c, equal for all stars, and an initial brightness s_{i} (0 ≤ s_{i} ≤ c).

Over time the stars twinkle. At moment 0 the i-th star has brightness s_{i}. Let at moment t some star has brightness x. Then at moment (t + 1) this star will have brightness x + 1, if x + 1 ≤ c, and 0, otherwise.

You want to look at the sky q times. In the i-th time you will look at the moment t_{i} and you will see a rectangle with sides parallel to the coordinate axes, the lower left corner has coordinates (x_1i, y_1i) and the upper right — (x_2i, y_2i). For each view, you want to know the total brightness of the stars lying in the viewed rectangle.

A star lies in a rectangle if it lies on its border or lies strictly inside it.


-----Input-----

The first line contains three integers n, q, c (1 ≤ n, q ≤ 10^5, 1 ≤ c ≤ 10) — the number of the stars, the number of the views and the maximum brightness of the stars.

The next n lines contain the stars description. The i-th from these lines contains three integers x_{i}, y_{i}, s_{i} (1 ≤ x_{i}, y_{i} ≤ 100, 0 ≤ s_{i} ≤ c ≤ 10) — the coordinates of i-th star and its initial brightness.

The next q lines contain the views description. The i-th from these lines contains five integers t_{i}, x_1i, y_1i, x_2i, y_2i (0 ≤ t_{i} ≤ 10^9, 1 ≤ x_1i < x_2i ≤ 100, 1 ≤ y_1i < y_2i ≤ 100) — the moment of the i-th view and the coordinates of the viewed rectangle.


-----Output-----

For each view print the total brightness of the viewed stars.


-----Examples-----
Input
2 3 3
1 1 1
3 2 0
2 1 1 2 2
0 2 1 4 5
5 1 1 5 5

Output
3
0
3

Input
3 4 5
1 1 2
2 3 0
3 3 1
0 1 1 100 100
1 2 2 4 4
2 2 1 4 7
1 50 50 51 51

Output
3
3
5
0



-----Note-----

Let's consider the first example.

At the first view, you can see only the first star. At moment 2 its brightness is 3, so the answer is 3.

At the second view, you can see only the second star. At moment 0 its brightness is 0, so the answer is 0.

At the third view, you can see both stars. At moment 5 brightness of the first is 2, and brightness of the second is 1, so the answer is 3.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Implementation


Solutions:
from sys import stdin
(n, q, c) = map(int, stdin.readline().split())
g = [[[0] * (c + 1) for i in range(101)] for j in range(101)]
for i in range(n):
	(x, y, s) = map(int, stdin.readline().split())
	g[x][y][s] += 1
for b in range(c + 1):
	for i in range(101):
		for j in range(101):
			g[i][j][b] += g[i - 1][j][b] + g[i][j - 1][b] - g[i - 1][j - 1][b]
for _ in range(q):
	(t, l, d, r, u) = map(int, stdin.readline().split())
	res = 0
	for b in range(c + 1):
		res += (t + b) % (c + 1) * (g[r][u][b] - g[r][d - 1][b] - g[l - 1][u][b] + g[l - 1][d - 1][b])
	print(res)


(n, q, c) = list(map(int, input().split()))
stars = [list(map(int, input().split())) for i in range(n)]
queries = [list(map(int, input().split())) for i in range(q)]
prec = [[[0 for y in range(101)] for x in range(101)] for i in range(c + 1)]
for (x, y, s) in stars:
	for t in range(c + 1):
		prec[t][x][y] += s + t if s + t <= c else s + t - (c + 1)
for s in range(len(prec)):
	for x in range(len(prec[s])):
		for y in range(len(prec[s][x])):
			if x and y:
				prec[s][x][y] += prec[s][x - 1][y] + prec[s][x][y - 1] - prec[s][x - 1][y - 1]
for (t, x1, y1, x2, y2) in queries:
	s = t % (c + 1)
	res = prec[s][x2][y2] - prec[s][x1 - 1][y2] - prec[s][x2][y1 - 1] + prec[s][x1 - 1][y1 - 1]
	print(res)


from sys import stdin, stdout

def main():
	(n, q, c) = [int(_) for _ in stdin.readline().strip().split()]
	g = [[[0 for i in range(102)] for j in range(102)] for k in range(12)]
	for _ in range(n):
		(x, y, s) = [int(_) for _ in stdin.readline().strip().split()]
		for t in range(c + 1):
			brightness = (s + t) % (c + 1)
			g[t][x][y] += brightness
	dp = [[[0 for i in range(102)] for j in range(102)] for k in range(12)]
	for t in range(c + 1):
		for x in range(1, 101):
			for y in range(1, 101):
				dp[t][x][y] = dp[t][x - 1][y] + dp[t][x][y - 1] - dp[t][x - 1][y - 1] + g[t][x][y]
	for _ in range(q):
		(t, x1, y1, x2, y2) = [int(_) for _ in stdin.readline().strip().split()]
		t = t % (c + 1)
		ans = dp[t][x2][y2] - dp[t][x1 - 1][y2] - dp[t][x2][y1 - 1] + dp[t][x1 - 1][y1 - 1]
		stdout.write(str(ans) + '\n')
main()


import sys
a = [int(i) for i in sys.stdin.readline().split()]
cc = a[2]
st = []
s = []
ch = [[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] for i in range(101)] for j in range(101)]
for i in range(a[0]):
	c = [int(j) for j in sys.stdin.readline().split()]
	st.append((c[0], c[1]))
	s.append(c[2])
	ch[c[0]][c[1]][c[2]] += 1
dp = [[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] for i in range(102)] for j in range(102)]
for i in range(1, 102):
	for j in range(1, 102):
		for k in range(11):
			dp[i][j][k] = dp[i - 1][j][k] + dp[i][j - 1][k] - dp[i - 1][j - 1][k]
		for k in range(11):
			dp[i][j][k] += ch[i - 1][j - 1][k]
anss = []
for i in range(a[1]):
	ans = 0
	l = [int(j) for j in sys.stdin.readline().split()]
	pp = l[0]
	i1 = l[1]
	j1 = l[2]
	i2 = l[3]
	j2 = l[4]
	count = [dp[i2 + 1][j2 + 1][k] + dp[i1][j1][k] - dp[i2 + 1][j1][k] - dp[i1][j2 + 1][k] for k in range(11)]
	t = l[0]
	for m in range(11):
		lk = (m + t) % (cc + 1)
		ans += count[m] * lk
	anss.append(str(ans))
print('\n'.join(anss))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, q, c) = map(int, input().split())
dp = [[[0 for i in range(101)] for j in range(101)] for k in range(c + 1)]
for i in range(n):
	(x, y, s) = map(int, input().split())
	dp[s][x][y] += 1
for i in range(c + 1):
	for j in range(1, 101):
		for k in range(1, 101):
			dp[i][j][k] += dp[i][j - 1][k] + dp[i][j][k - 1] - dp[i][j - 1][k - 1]
ans = 0
for j in range(q):
	ans = 0
	(t, x, y, x1, y1) = map(int, input().split())
	for i in range(c + 1):
		bright = (i + t) % (c + 1)
		amount = dp[i][x1][y1] - dp[i][x1][y - 1] - dp[i][x - 1][y1] + dp[i][x - 1][y - 1]
		ans += bright * amount
	print(ans)


import sys
from bisect import bisect_left, bisect_right
(n, q, c) = list(map(int, input().split()))
values = [[[0 for _ in range(11)] for _ in range(0, 101)] for _ in range(0, 101)]
for i in range(n):
	(x, y, s) = list(map(int, sys.stdin.readline().split()))
	values[x][y][s] += 1
dp = [[[-1 for _ in range(11)] for _ in range(0, 101)] for _ in range(0, 101)]
for i in range(0, 101):
	for p in range(11):
		dp[0][i][p] = 0
		dp[i][0][p] = 0

def recurse(p, x, y):
	if x == 0 or y == 0:
		return 0
	if dp[x][y][p] != -1:
		return dp[x][y][p]
	if x == 1 and y == 1:
		dp[x][y][p] = values[x][y][p]
		return values[x][y][p]
	else:
		dp[x][y][p] = recurse(p, x - 1, y) + recurse(p, x, y - 1) - recurse(p, x - 1, y - 1) + values[x][y][p]
		dp[x][y][p] = max(dp[x][y][p], 0)
		return dp[x][y][p]
for i in range(1, 101):
	for j in range(1, 101):
		for p in range(0, c + 1):
			recurse(p, i, j)
for i in range(q):
	(t, x1, y1, x2, y2) = list(map(int, sys.stdin.readline().split()))
	ans = 0
	for k in range(0, c + 1):
		ans += (t + k) % (c + 1) * (dp[x2][y2][k] - dp[x1 - 1][y2][k] - dp[x2][y1 - 1][k] + dp[x1 - 1][y1 - 1][k])
	print(ans)


import sys
input = sys.stdin.readline
(n, q, c) = map(int, input().split())
g = [[[0] * 11 for i in range(101)] for i in range(101)]
for _ in range(n):
	(x, y, s) = map(int, input().split())
	g[x][y][s] += 1
for i in range(1, 101):
	for j in range(1, 101):
		for k in range(11):
			g[i][j][k] += g[i - 1][j][k] + g[i][j - 1][k] - g[i - 1][j - 1][k]
for _ in range(q):
	(t, x1, y1, x2, y2) = map(int, input().split())
	ans = 0
	for k in range(11):
		cnt = g[x2][y2][k] - g[x1 - 1][y2][k] - g[x2][y1 - 1][k] + g[x1 - 1][y1 - 1][k]
		ans += (t + k) % (c + 1) * cnt
	print(ans)


def fun(n, q, c, stars, querry):
	m = 100
	precom = [[[0] * m for _ in range(m)] for _ in range(c + 1)]
	for (x, y, p) in stars:
		for i in range(c + 1):
			temp = (p + i) % (c + 1)
			precom[i][x - 1][y - 1] += temp
	for k in range(c + 1):
		for i in range(0, m):
			for j in range(1, m):
				precom[k][i][j] += precom[k][i][j - 1]
	for k in range(c + 1):
		for j in range(0, m):
			for i in range(1, m):
				precom[k][i][j] += precom[k][i - 1][j]
	for (t, x1, y1, x2, y2) in querry:
		t = t % (c + 1)
		(x1, y1, x2, y2, a, b, C, d) = (x1 - 1, y1 - 1, x2 - 1, y2 - 1, 0, 0, 0, 0)
		a = precom[t][x2][y2]
		if x1 != 0:
			b = precom[t][x1 - 1][y2]
		if y1 != 0:
			C = precom[t][x2][y1 - 1]
		if x1 != 0 and y1 != 0:
			d = precom[t][x1 - 1][y1 - 1]
		print(a - b - C + d)
(n, q, c) = list(map(lambda x: int(x), input().split()))
stars = [list(map(lambda x: int(x), input().split())) for _ in range(n)]
querry = [list(map(lambda x: int(x), input().split())) for _ in range(q)]
fun(n, q, c, stars, querry)


from sys import stdin
input = stdin.readline
add_mod = lambda a, b: (a % c + b % c) % c
N = 101
(n, q, c) = map(int, input().split())
c += 1
star = [list(map(int, input().split())) for _ in range(n)]
view = [list(map(int, input().split())) for _ in range(q)]
dp = [[[0 for _ in range(N)] for _ in range(N)] for _ in range(11)]
for mod in range(11):
	for (i, j, k) in star:
		dp[mod][i][j] += add_mod(k, mod)
for mod in range(11):
	for i in range(1, N):
		for j in range(1, N):
			dp[mod][i][j] += dp[mod][i][j - 1]
all_res = []
for (t, x1, y1, x2, y2) in view:
	tem = 0
	for i in range(x1, x2 + 1):
		tem += dp[t % c][i][y2] - dp[t % c][i][y1 - 1]
	all_res.append(str(tem))
print('\n'.join(all_res))


import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict, deque, Counter
from math import sqrt, pi, ceil, log, inf, gcd, floor
from itertools import combinations
from bisect import *

def main():
	(n, q, c) = map(int, input().split())
	a = [[[0 for i in range(101)] for j in range(101)] for k in range(11)]
	for i in range(n):
		(x, y, s) = map(int, input().split())
		for k in range(11):
			a[k][x][y] += (s + k) % (c + 1)
	for k in range(11):
		for i in range(101):
			for j in range(1, 101):
				a[k][i][j] += a[k][i][j - 1]
	for k in range(11):
		for i in range(1, 101):
			for j in range(101):
				a[k][i][j] += a[k][i - 1][j]
	for i in range(q):
		(t, x1, y1, x2, y2) = map(int, input().split())
		z = t % (c + 1)
		print(a[z][x2][y2] - a[z][x1 - 1][y2] - a[z][x2][y1 - 1] + a[z][x1 - 1][y1 - 1])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from __future__ import print_function
from itertools import permutations as perm
from collections import *
from sys import stdin
from bisect import *
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(n, q, c) = gil()
f = [[[0 for _ in range(101)] for _ in range(101)] for _ in range(c + 1)]
for _ in range(n):
	(x, y, s) = gil()
	f[s][x][y] += 1
for y in range(1, 101):
	for x in range(1, 101):
		for ci in range(c + 1):
			f[ci][x][y] += f[ci][x][y - 1] + f[ci][x - 1][y] - f[ci][x - 1][y - 1]
for _ in range(q):
	(t, x1, y1, x2, y2) = gil()
	store = t
	val = 0
	for ci in range(c + 1):
		fi = f[ci][x2][y2] + f[ci][x1 - 1][y1 - 1] - f[ci][x2][y1 - 1] - f[ci][x1 - 1][y2]
		val += fi * ((t + ci) % (c + 1))
	print(val)


import sys
input = sys.stdin.readline
(n, q, c) = map(int, input().split())
dp = []
for i in range(101):
	k = []
	for j in range(101):
		k.append([0] * 11)
	dp.append(k)
for i in range(n):
	(x, y, s) = map(int, input().split())
	dp[x][y][s] += 1
for i in range(1, 101):
	for s in range(11):
		dp[i][0][s] += dp[i - 1][0][s]
for i in range(1, 101):
	for s in range(11):
		dp[0][i][s] += dp[0][i - 1][s]
for j in range(101):
	for i in range(101):
		if i > 0 and j > 0:
			for s in range(11):
				dp[i][j][s] += dp[i - 1][j][s] + dp[i][j - 1][s] - dp[i - 1][j - 1][s]
for j in range(q):
	(p, x1, y1, x2, y2) = map(int, input().split())
	k = [0] * 11
	ans = 0
	for i in range(11):
		if x1 > 0 and y1 > 0:
			k[i] = dp[x2][y2][i] - dp[x2][y1 - 1][i] - (dp[x1 - 1][y2][i] - dp[x1 - 1][y1 - 1][i])
		elif x1 > 0 and y1 == 0:
			k[i] = dp[x2][y2][i] - dp[x1 - 1][y2][i]
		elif y1 > 0 and x1 == 0:
			k[i] = dp[x2][y2][i] - dp[x2][y1 - 1][i]
		else:
			k[i] = dp[x2][y2][i]
		if i >= c:
			if p == 0:
				r = i
			else:
				r = (p - 1) % (c + 1)
		elif p > c - i:
			r = (p - 1 - (c - i)) % (c + 1)
		else:
			r = p + i
		ans += k[i] * r
	print(ans)


import math, sys, bisect, heapq
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
int1 = lambda x: int(x) - 1
ilele = lambda : map(int, input().split())
alele = lambda : list(map(int, input().split()))
ilelec = lambda : map(int1, input().split())
alelec = lambda : list(map(int1, input().split()))

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])
dp = {}

def fun(A):
	B = list2d(101, 101, 0)
	for j in range(101):
		B[0][j] = A[0][j]
	for i in range(1, 101):
		for j in range(101):
			B[i][j] = A[i][j] + B[i - 1][j]
	for i in range(101):
		for j in range(1, 101):
			B[i][j] = B[i][j] + B[i][j - 1]
	return B
(n, q, c) = ilele()
G = defaultdict(list)
for i in range(n):
	(a, b, s) = ilele()
	G[a, b].append(s)
for i in range(c + 1):
	A = list2d(101, 101, 0)
	for j in range(1, 101):
		for k in range(1, 101):
			x = G.get((j, k), [])
			for l in x:
				r = (l + i) % (c + 1)
				A[j][k] += r
	B = fun(A)
	dp[i] = B
for i in range(q):
	(t, x1, y1, x2, y2) = ilele()
	t %= c + 1
	ans = dp[t][x2][y2]
	ans -= dp[t][x2][y1 - 1]
	ans -= dp[t][x1 - 1][y2]
	ans += dp[t][x1 - 1][y1 - 1]
	print(ans)


import random, math
from copy import deepcopy as dc
MAXX = 101
MAXY = 101

def input_test():
	(n, q, c) = map(int, input().strip().split(' '))
	st = [[[0 for i in range(MAXX)] for j in range(MAXY)] for k in range(c + 1)]
	for _ in range(n):
		(x, y, s) = map(int, input().strip().split(' '))
		for t in range(c + 1):
			st[t][x][y] += (s + t) % (c + 1)
	for k in range(c + 1):
		for i in range(1, MAXX):
			for j in range(1, MAXY):
				st[k][i][j] = st[k][i][j] + st[k][i - 1][j] + st[k][i][j - 1] - st[k][i - 1][j - 1]
	comp = st
	for _ in range(q):
		(t, x1, y1, x2, y2) = map(int, input().strip().split(' '))
		t = t % (c + 1)
		to_be_add = comp[t][x1 - 1][y1 - 1]
		tot = comp[t][x2][y2] - comp[t][x2][y1 - 1] - comp[t][x1 - 1][y2] + to_be_add
		print(tot)

def test():
	pass
input_test()


(n, q, c) = list(map(int, input().split()))
sky = [[[0] * 11 for j in range(101)] for i in range(101)]
c += 1
for i in range(n):
	(x, y, s) = list(map(int, input().split()))
	sky[y][x][s % c] += 1
for k in range(11):
	i = 1
	while i < 101:
		j = 1
		while j < 101:
			sky[i][j][k] += sky[i - 1][j][k] + sky[i][j - 1][k] - sky[i - 1][j - 1][k]
			j += 1
		i += 1
req = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
	(t, x, y, x2, y2) = req[i]
	ans = 0
	j = 0
	while j < c:
		ans += (sky[y2][x2][j] - sky[y2][x - 1][j] - sky[y - 1][x2][j] + sky[y - 1][x - 1][j]) * ((j + t) % c)
		j += 1
	print(ans)


import sys
from collections import defaultdict
input = sys.stdin.readline
(n, q, c) = map(int, input().split())
d = defaultdict(lambda : [0] * 11)
for _ in range(n):
	(x, y, s) = map(int, input().split())
	if (x, y) not in d:
		d[x, y] = [0] * 11
	d[x, y][s] += 1
g = [[[0] * 11 for i in range(101)] for i in range(101)]
g[1][1] = d[1, 1]
for i in range(1, 101):
	for j in range(1, 101):
		if i == 1 and j == 1:
			continue
		for k in range(11):
			if i == 1:
				g[i][j][k] = g[i][j - 1][k] + d[i, j][k]
			elif j == 1:
				g[i][j][k] = g[i - 1][j][k] + d[i, j][k]
			else:
				g[i][j][k] = g[i - 1][j][k] + g[i][j - 1][k] - g[i - 1][j - 1][k] + d[i, j][k]
for _ in range(q):
	(t, x1, y1, x2, y2) = map(int, input().split())
	ans = 0
	for k in range(11):
		cnt = g[x2][y2][k] - g[x1 - 1][y2][k] - g[x2][y1 - 1][k] + g[x1 - 1][y1 - 1][k]
		ans += (t + k) % (c + 1) * cnt
	print(ans)


from sys import stdin, stdout
(n, q, c) = map(int, stdin.readline().split())
sky = [[[0 for i in range(101)] for j in range(101)] for k in range(c + 1)]
for i in range(n):
	(x, y, s) = map(int, stdin.readline().split())
	for t in range(c + 1):
		sky[t][x - 1][y - 1] += (s + t) % (c + 1)
for t in range(c + 1):
	for j in range(1, 101):
		for i in range(101):
			sky[t][i][j] += sky[t][i][j - 1]
for t in range(c + 1):
	for i in range(1, 101):
		for j in range(101):
			sky[t][i][j] += sky[t][i - 1][j]
for _ in range(q):
	(t, x1, y1, x2, y2) = map(int, stdin.readline().split())
	t = t % (c + 1)
	curr = sky[t]
	res = curr[x2 - 1][y2 - 1]
	if x1 - 1 > 0:
		res -= curr[x1 - 2][y2 - 1]
	if y1 - 1 > 0:
		res -= curr[x2 - 1][y1 - 2]
	if x1 - 1 > 0 and y1 - 1 > 0:
		res += curr[x1 - 2][y1 - 2]
	stdout.write(str(res) + '\n')


import sys

def main():
	(n, q, c) = list(map(int, sys.stdin.readline().split()))
	a = []
	c += 1
	for i in range(c):
		t = []
		for j in range(102):
			t.append([0] * 102)
		a.append(t)
	for i in range(n):
		(x, y, s) = list(map(int, sys.stdin.readline().split()))
		for j in range(c):
			a[j][x][y] += s
			s += 1
			if s >= c:
				s = 0
	for k in range(c):
		for i in range(102):
			for j in range(1, 102):
				a[k][i][j] += a[k][i][j - 1]
	alans = [0] * q
	for i in range(q):
		(t, x1, y1, x2, y2) = list(map(int, sys.stdin.readline().split()))
		ans = 0
		t = t % c
		for j in range(x1, x2 + 1):
			ans += a[t][j][y2] - a[t][j][y1 - 1]
		alans[i] = str(ans)
	print('\n'.join(alans))
main()


import sys
input = sys.stdin.buffer.readline

def print(val):
	sys.stdout.write(str(val) + '\n')

def prog():
	(n, q, c) = map(int, input().split())
	initial_sky = [[[] for j in range(101)] for i in range(101)]
	sky = [[[0] * 101 for j in range(101)] for i in range(c + 1)]
	for i in range(n):
		(x, y, s) = map(int, input().split())
		initial_sky[x][y].append(s)
	for t in range(c + 1):
		for i in range(101):
			for j in range(101):
				for star in initial_sky[i][j]:
					sky[t][i][j] += (star + t) % (c + 1)
	for t in range(c + 1):
		for i in range(1, 101):
			for j in range(1, 101):
				sky[t][i][j] += sky[t][i - 1][j] + sky[t][i][j - 1] - sky[t][i - 1][j - 1]
	for i in range(q):
		(t, x1, y1, x2, y2) = map(int, input().split())
		t %= c + 1
		print(sky[t][x2][y2] - (sky[t][x2][y1 - 1] + sky[t][x1 - 1][y2] - sky[t][x1 - 1][y1 - 1]))
prog()


import sys

def getInt():
	n = sys.stdin.readline()
	return int(n)

def getStr():
	s = sys.stdin.readline()
	return s

def getArr():
	arr = list(map(int, sys.stdin.readline().split()))
	return arr

def getPair():
	(a, b) = list(map(int, sys.stdin.readline().split()))
	return (a, b)

def put(n):
	sys.stdout.write(str(n) + '\n')
a = getArr()
cc = a[2]
st = []
s = []
ch = [[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] for i in range(101)] for j in range(101)]
for i in range(a[0]):
	c = getArr()
	st.append((c[0], c[1]))
	s.append(c[2])
	ch[c[0]][c[1]][c[2]] += 1
dp = [[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] for i in range(102)] for j in range(102)]
for i in range(1, 102):
	for j in range(1, 102):
		for k in range(11):
			dp[i][j][k] = dp[i - 1][j][k] + dp[i][j - 1][k] - dp[i - 1][j - 1][k]
		for k in range(11):
			dp[i][j][k] += ch[i - 1][j - 1][k]
for i in range(a[1]):
	ans = 0
	l = getArr()
	i1 = l[1]
	j1 = l[2]
	i2 = l[3]
	j2 = l[4]
	count = [dp[i2 + 1][j2 + 1][k] + dp[i1][j1][k] - dp[i2 + 1][j1][k] - dp[i1][j2 + 1][k] for k in range(11)]
	t = l[0]
	for m in range(11):
		lk = (m + t) % (cc + 1)
		ans += count[m] * lk
	print(ans)


import sys
input = sys.stdin.buffer.readline
(n, q, bright) = map(int, input().split())
dp = [[[0 for j in range(11)] for i in range(100 + 3)] for k in range(100 + 3)]
for i in range(n):
	(a, b, c) = map(int, input().split())
	dp[a][b][c] += 1
for i in range(1, 101):
	for j in range(1, 101):
		for k in range(11):
			dp[i][j + 1][k] += dp[i][j][k]
for i in range(1, 101):
	for j in range(1, 101):
		for k in range(11):
			dp[j + 1][i][k] += dp[j][i][k]
for i in range(q):
	(t, l_x, l_y, h_x, h_y) = map(int, input().split())
	l_x -= 1
	l_y -= 1
	arr = []
	a = dp[h_x][h_y]
	b = dp[h_x][l_y]
	c = dp[l_x][h_y]
	d = dp[l_x][l_y]
	for i in range(11):
		arr.append(a[i] - b[i] - c[i] + d[i])
	ans = 0
	for j in range(11):
		ans += (j + t) % (bright + 1) * arr[j]
	print(ans)


from sys import stdin

def main():
	(n, q, c) = map(int, input().split())
	c += 1
	l = stdin.read().splitlines()
	prec = [[[0] * 101 for _ in range(101)] for _ in range(c)]
	for line in l[:n]:
		(x, y, s) = map(int, line.split())
		for t in range(c):
			prec[t - s][x][y] += t
	del l[:n]
	for plane in prec:
		for x in range(100):
			for y in range(100):
				plane[x + 1][y + 1] += plane[x][y + 1] + plane[x + 1][y] - plane[x][y]
	for (i, line) in enumerate(l):
		(t, x1, y1, x2, y2) = map(int, line.split())
		plane = prec[t % c]
		l[i] = plane[x2][y2] - plane[x1 - 1][y2] - plane[x2][y1 - 1] + plane[x1 - 1][y1 - 1]
	print('\n'.join(map(str, l)))
main()


from sys import stdin, stdout
import math

def main():
	line = stdin.readline().split()
	n = int(line[0])
	q = int(line[1])
	c = int(line[2])
	dp = [[[0 for i in range(101)] for j in range(101)] for k in range(11)]
	for i in range(n):
		line = stdin.readline().split()
		x = int(line[0])
		y = int(line[1])
		p = int(line[2])
		dp[p][x][y] += 1
	for p in range(c + 1):
		for x in range(1, 101):
			for y in range(1, 101):
				dp[p][x][y] += dp[p][x - 1][y] + dp[p][x][y - 1] - dp[p][x - 1][y - 1]
	for i in range(q):
		line = stdin.readline().split()
		t = int(line[0])
		x1 = int(line[1])
		y1 = int(line[2])
		x2 = int(line[3])
		y2 = int(line[4])
		ans = 0
		for j in range(c + 1):
			bright = (j + t) % (c + 1)
			amount = dp[j][x2][y2] - dp[j][x2][y1 - 1] - dp[j][x1 - 1][y2] + dp[j][x1 - 1][y1 - 1]
			ans += bright * amount
		stdout.write(str(ans) + '\n')
main()


from sys import stdin, stdout
(n, q, c) = map(int, stdin.readline().split())
cs = [[[0] * 101 for _ in range(101)] for _ in range(11)]
for k in range(n):
	(x, y, s) = map(int, stdin.readline().split())
	cs[s][x][y] += 1
for i in range(1, 101):
	for j in range(1, 101):
		for k in range(11):
			cs[k][i][j] += cs[k][i - 1][j] + cs[k][i][j - 1] - cs[k][i - 1][j - 1]
for _ in range(q):
	(t, x1, y1, x2, y2) = map(int, stdin.readline().split())
	totalb = 0
	for k in range(11):
		totalb += (k + t) % (c + 1) * (cs[k][x2][y2] - cs[k][x2][y1 - 1] - cs[k][x1 - 1][y2] + cs[k][x1 - 1][y1 - 1])
	print(totalb)


from sys import stdin, stdout
stdin.readline

def mp():
	return list(map(int, stdin.readline().strip().split()))

def it():
	return int(stdin.readline().strip())
(n, q, c) = mp()
dp = [[[0] * 11 for _ in range(101)] for _ in range(101)]
for _ in range(n):
	(x, y, ib) = mp()
	dp[x][y][ib] += 1
for i in range(1, 101):
	for j in range(1, 101):
		for k in range(11):
			dp[i][j][k] += dp[i - 1][j][k] + dp[i][j - 1][k] - dp[i - 1][j - 1][k]
for _ in range(q):
	(t, x1, y1, x2, y2) = mp()
	ans = 0
	for k in range(11):
		cnt = dp[x2][y2][k] - dp[x1 - 1][y2][k] - dp[x2][y1 - 1][k] + dp[x1 - 1][y1 - 1][k]
		ans += (t + k) % (c + 1) * cnt
	print(ans)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def getInts():
	return map(int, input().split())
(n, q, c) = getInts()
sky = [[[0 for _ in range(101)] for _ in range(101)] for _ in range(11)]
sum = [[[0 for _ in range(101)] for _ in range(101)] for _ in range(11)]
for _ in range(n):
	(x, y, s) = getInts()
	sky[s][x][y] += 1

def calc(id: int):
	for i in range(1, 101):
		for j in range(1, 101):
			sum[id][i][j] = sum[id][i - 1][j] + sum[id][i][j - 1] + sky[id][i][j] - sum[id][i - 1][j - 1]
for i in range(c + 1):
	calc(i)
for _ in range(q):
	(t, x1, y1, x2, y2) = getInts()
	ans = 0
	for id in range(c + 1):
		val = (id + t) % (c + 1)
		cnt = sum[id][x2][y2] - sum[id][x1 - 1][y2] - sum[id][x2][y1 - 1] + sum[id][x1 - 1][y1 - 1]
		ans += val * cnt
	print(ans)


input = __import__('sys').stdin.readline
(n, q, c) = map(int, input().split())
dp = [[[0 for i in range(101)] for j in range(101)] for k in range(c + 1)]
for i in range(n):
	(x, y, s) = map(int, input().split())
	dp[s][x][y] += 1
for i in range(c + 1):
	for j in range(1, 101):
		for k in range(1, 101):
			dp[i][j][k] += dp[i][j - 1][k] + dp[i][j][k - 1] - dp[i][j - 1][k - 1]
for _ in range(q):
	(t, x1, y1, x2, y2) = map(int, input().split())
	ans = 0
	for i in range(c + 1):
		bright = (i + t) % (c + 1)
		amt = dp[i][x2][y2] - dp[i][x1 - 1][y2] - dp[i][x2][y1 - 1] + dp[i][x1 - 1][y1 - 1]
		ans += bright * amt
	print(ans)