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.

Difficulty: interview

Starter code:

Solutions:
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

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)
        #print(m,lk,ans)
    anss.append(str(ans))
print("\n".join(anss))
    #break


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)] #0, c
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)




"""
    Author      : Arif Ahmad
    Date        : 
    Algo        : 
    Difficulty  : 
"""
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 stores cummulative brightness at time t
    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')


def __starting_point():
    main()

__starting_point()

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)] #0, c
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)


# Fast I/O template
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")

# Your code goes here
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(m,lk,ans)
    print(ans)

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 random, math
from copy import deepcopy as dc

MAXX = 101
MAXY = 101


# Function to take input
def input_test():
	n, q, c = list(map(int, input().strip().split(" ")))
	st = [[[0 for i in range(MAXX)] for j in range(MAXY)] for k in range(c+1)]
	
	# Taking Input and marking the values in the 
	# Frequency array and the grid that the star is present
	for _ in range(n):
		x, y, s = list(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 i in comp:
	# 	for j in i:
	# 		print(j)
	# 	print("Done")

	# Taking the Queries
	for _ in range(q):
		t, x1, y1, x2, y2 = list(map(int, input().strip().split(" ")))
		# t = t % (c+1)
		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)




# Function to check test my code
def test():
	pass


input_test()
# test()


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 = list(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 sys
input=sys.stdin.readline
n,q,c=list(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=list(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=list(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)
        else:
            if p>(c-i):
                r=(p-1-(c-i))%(c+1)
            else:
                r=(p+i)
        ans+=(k[i])*(r)
    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)                     

import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
int1 = lambda x: int(x) - 1
#input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
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)]
#MOD = 1000000000 + 7
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)
#print(G)
for i in range(c+1):
    #print(i,c)
    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)
                #print(j,k,r,l,i)
                A[j][k] += r
    B = fun(A)
    dp[i] = B

for i in range(q):
    t,x1,y1,x2,y2 = ilele()
    t %= (c+1)
    #print(dp[t][x2][y2],dp[t][x2][y1])
    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 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)

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):
		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]+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)

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)

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)