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

Over time the stars twinkle. At moment 0 the i-th star has brightness si. 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 ti and you will see a rectangle with sides parallel to the coordinate axes, the lower left corner has coordinates (x1i, y1i) and the upper right — (x2i, y2i). 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 ≤ 105, 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 xi, yi, si (1 ≤ xi, yi ≤ 100, 0 ≤ si ≤ 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 ti, x1i, y1i, x2i, y2i (0 ≤ ti ≤ 109, 1 ≤ x1i < x2i ≤ 100, 1 ≤ y1i < y2i ≤ 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.
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class main {
	private static InputStream stream;
	private static byte[] buf = new byte[1024];
	private static int curChar;
	private static int numChars;
	private static SpaceCharFilter filter;
	private static PrintWriter pw;
	private static long mod = 1000000000 + 7;
	private static long mod1 = 1000000000 + 9;
	private static int MAX=1000001;
	private static int block;
	private static void soln(){
		/*long k=nextInt();
		String s=nextLine();
		long sum=0;
		long[] digit=new long[10];
		for(int i=0;i<s.length();i++){
			sum+=(s.charAt(i)-'0');
			digit[(s.charAt(i)-'0')]++;
		}
		long ans=0;
		if(sum>=k){
			pw.println(0);
		}else{
			sum=k-sum;
			//System.out.println(sum);
			for(int i=0;i<10;i++){
				//System.out.println(sum+" "+digit[i]+" "+ans);
				long diff=(9-i)*digit[i];
				if(diff<=sum){
					sum-=diff;
					ans+=digit[i];
				}else{
					long diff1=9-i;
					ans+=sum/diff1;
					if(sum%diff1!=0)
						ans++;
					sum=0;
					break;
				}
			}
			pw.println(ans);
		}*/
		int n=nextInt();
		int q=nextInt();
		int c=nextInt();
		//int[][] arr=new int[101][101];
		int[][][] cnt=new int[101][101][11];
		for(int i=0;i<n;i++){
			int xi=nextInt();
			int yi=nextInt();
			int ci=nextInt();
			cnt[xi][yi][ci]++;
		}
		for(int i=1;i<=100;i++)
			for(int j=1;j<=100;j++){
				for(int k=0;k<=10;k++)
					cnt[i][j][k]+=(cnt[i-1][j][k]+cnt[i][j-1][k]-cnt[i-1][j-1][k]);
			}
		for(int i=0;i<q;i++){
			int ti=nextInt()%(c+1);
			int x1=nextInt();
			int y1=nextInt();
			int x2=nextInt();
			int y2=nextInt();
			long ans=0;
			for(int j=0;j<=10;j++){
				long cnt1=cnt[x2][y2][j]-cnt[x1-1][y2][j]-cnt[x2][y1-1][j]+cnt[x1-1][y1-1][j];
				ans+=cnt1*(long)((j+ti)%(c+1));
			}
			//System.out.println(arr[x2][y2]+" "+arr[x1-1][y2]+" "+arr[x2][y1-1]+" "+arr[x1-1][y1-1]);
			//int ans1=arr[x2][y2]-arr[x1-1][y2]-arr[x2][y1-1]+arr[x1-1][y1-1];
			//int ans2=cnt[x2][y2]-cnt[x1-1][y2]-cnt[x2][y1-1]+cnt[x1-1][y1-1];
			pw.println(ans);
		}
	}
	public static class Segment {
		private int[] tree;
		private int[] base;
		private int size;
		private int n;
		private class node{
			private int a;
			private int b;
			private int c;
			public node(int x,int y,int z){
				a=x;
				b=y;
				c=z;
			}
		}
		public Segment(int n,int[] arr){
			this.base=arr;
			int x = (int) (Math.ceil(Math.log(n) / Math.log(2)));
	        size = 2 * (int) Math.pow(2, x) - 1;
			tree=new int[size];
			this.n=n;
			build(0,0,n-1);
		}
		private void build(int id,int l,int r){
			//pw.println(1);
			if(r==l){
				tree[id]=base[l];
				return;
			}
			int mid=l+(r-l)/2;
			//System.out.println(2*id+1+" "+l+" "+mid);
			build(2*id+1,l,mid);
			//System.out.println(2*id+2+" "+(mid+1)+" "+r);
			build(2*id+2,mid+1,r);
			tree[id]=tree[2*id+1]^tree[2*id+2];
		}
		public int query(int l,int r){
			return queryUtil(l,r,0,0,n-1);
		}
		private int queryUtil(int x,int y,int id,int l,int r){
			if(l>y || x>r) 
				return 0;
			if(x <= l && r<=y)
				return tree[id];
			int mid=l+(r-l)/2;
			return queryUtil(x,y,2*id+1,l,mid)^queryUtil(x,y,2*id+2,mid+1,r);
		}
		/*private void cnt(int id,int l,int r,HashSet<Integer> set){
			if(tree[id]!=0){
				set.add(tree[id]);
				return;
			}
			if(r==l)
				return;
			int mid=l+(r-l)/2;
			cnt(2*id+1,l,mid,set);
			cnt(2*id+2,mid+1,r,set);
		}*/
		public void update(int x,int colour,int id,int l,int r){
			if(x>r || x<l)
				return;
			if(l==r){
				tree[id]^=colour;
				return;
			}
			int mid=l+(r-l)/2;
			//shift(id);
			update(x,colour,2*id+1,l,mid);
			update(x,colour,2*id+2,mid+1,r);
			tree[id]=tree[2*id+1]^tree[2*id+2];
		}
		private void shift(int id){
			if(tree[id]!=0){
				tree[2*id+1]=tree[2*id+2]=tree[id];
			}
			tree[id]=0;
		}
	}

	static void multiply(long[][] a, long[][] b,long m){
		int n=a.length;
	    long[][] mul=new long[n][n];
	    for (int i = 0; i < n; i++){
	        for (int j = 0; j < n; j++){
	            mul[i][j] = 0;
	            for (int k = 0; k < n; k++)
	                mul[i][j] = (mul[i][j]+(a[i][k]*b[k][j])%m)%m;
	        }
	    }
	    for (int i=0; i<n; i++)
	        for (int j=0; j<n; j++)
	            a[i][j] =mul[i][j];
	}
	static class Pair implements Comparable<Pair>{
		int p;
		int c;
		int b;
		public Pair(int t,int x,int y){
			p=t;
			c=x;
			b=y;
		}
		@Override
		public int compareTo(Pair arg0) {
			return this.p-arg0.p;
		}
		
	}
	private static class DSU{
		int[] parent;
		public DSU(int n){
			parent=new int[n];
			for(int i=0;i<n;i++)
				parent[i]=i;
		}
		int find(int i){
	        while(parent[i] !=i){
	        	parent[i]=parent[parent[i]];
	        	i=parent[i];
	        }
	        return i;
	    }
		void Union(int x, int y){
	        int xset = find(x);
	        int yset = find(y);
	        parent[yset]=yset;
	        parent[xset] = yset;
	    }
	}
	private static class Edge{
		int x;
		int y;
		int i;
		public Edge(int a,int b,int c){
			x=a; y=b;i=c;
		}
	}
	private static long pow(long a, long b, long c) {
		if (b == 0)
			return 1;
		long p = pow(a, b / 2, c);
		p = (p * p) % c;
		return (b % 2 == 0) ? p : (a * p) % c;
	}
	
	private static class Mo implements Comparable<Mo>{
		int l;
		int r;
		int i;
		public Mo(int a,int b,int ind) {
			l=a;r=b;i=ind;
		}
		@Override
		public int compareTo(Mo arg0) {
			int b1=this.l/block;
			int b2=arg0.l/block;
			return (b1!=b2)?(b1-b2):(this.r-arg0.r);
		}
	}

	private static long gcd(long n, long l) {
		if (l == 0)
			return n;
		return gcd(l, n % l);
	}

	private static long max(long a, long b) {
		if (a > b)
			return a;
		return b;
	}

	private static long min(long a, long b) {
		if (a < b)
			return a;
		return b;
	}

	public static void main(String[] args) throws Exception {
		new Thread(null,new Runnable(){
			@Override
			public void run() {
				/*try {
					InputReader(new FileInputStream("C:\\Users\\hardik\\Desktop\\C-small-1-attempt1.in"));
				} catch (FileNotFoundException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}*/
				InputReader(System.in);
				pw = new PrintWriter(System.out);
				/*try {
					pw=new PrintWriter(new FileOutputStream("C:\\Users\\hardik\\Desktop\\out.txt"));
				} catch (FileNotFoundException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}*/
				soln();
				pw.close();
			}
		},"1",1<<26).start();
	}

	public static void InputReader(InputStream stream1) {
		stream = stream1;
	}

	private static boolean isWhitespace(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private static boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}

	private static int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	private static int nextInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	private static long nextLong() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	private static String nextToken() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	private static String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	private static int[] nextIntArray(int n) {
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = nextInt();
		}
		return arr;
	}

	private static long[] nextLongArray(int n) {
		long[] arr = new long[n];
		for (int i = 0; i < n; i++) {
			arr[i] = nextLong();
		}
		return arr;
	}

	private static void pArray(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		return;
	}

	private static void pArray(long[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		return;
	}

	private static boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhitespace(c);
	}
	private static char nextChar() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		char c1=(char)c;
		while(!isSpaceChar(c))
			c=read();
		return c1;
	}
	private interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}