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.*;
import java.util.*;
 
	 
	 
	public   class Main {
		private InputStream is;
		private PrintWriter out;
		int time = 0, val[][], DP[], start[], end[], dist[],  black[], MOD = (int)(1e9+7), arr[], weight[][], x[], y[], parent[];
		int MAX = 800000, N, K;
		long red[];
		ArrayList<Integer>[] amp;
		ArrayList<Pair>[][] pmp;
		boolean b[], boo[][];
		Pair prr[];
		HashMap<Integer,Long> hm[] = new HashMap[305];
		long Dp[][][][] = new long[110][110][12][12];
		void soln() {
			is = System.in;
			out = new PrintWriter(System.out);
			long s = System.currentTimeMillis();
			solve();
			//out.close();
			out.flush();
			//tr(System.currentTimeMillis() - s + "ms");
		}
		public static void main(String[] args) throws Exception {
			new Thread(null, new Runnable() {
			public void run() {
				try {
			//new CODEFORCES().soln();
			} catch (Exception e) {
					System.out.println(e);
				}
			}
		}, "1", 1 << 26).start();
			new Main().soln();
		}
		int ans = 0, cost = 0;
		char ch[], ch1[];
		int dp[][] = new int[5010][5010], n;
		void solve(){
			int n = ni(), q = ni(), c = ni();
			int arr[][] = new int[n][3];
			for(int i = 0; i < n ;i++){
				for(int j = 0; j<3;j++){
					arr[i][j] = ni();
				}
			}
			int amp[][][] = new int[110][110][11];
			int d = c+1;
			for(int i = 0;i<n;i++){
				amp[arr[i][0]][arr[i][1]][arr[i][2]]++;
			}
			long sum[][][] = new long[110][110][11];
			for(int i = 1;i<110;i++){
				for(int j = 1;j<110;j++){
					for(int k = 0;k<=c;k++){
						sum[i][j][k] = (amp[i][j][k]+sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k]);
					}
				}
			}
			while(q-->0){
				int t = ni(), x1 = ni() , y1 = ni(), x2 = ni(), y2 = ni();
				long ans = 0;
				for(int i = 0; i<=c;i++){
					long h1 = sum[x2][y2][i] - sum[x2][y1-1][i] - sum[x1-1][y2][i] + sum[x1-1][y1-1][i];
					ans += h1*((i+t)%d);
				}
				out.println(ans);
			}
		}
		void sieve(int n){
			b = new boolean[n+1];
			b[0] = b[1] = true;
			for(int i = 2;i*i<n;i++){
				if(!b[i]){
					for(int j = 2*i;j<100001;j+=i) b[j] = true;
				}
			}
		}
		class Pair implements Comparable<Pair>{
			int u, v, i;
			
			Pair(int u, int v){
				this.u = u;
				this.v = v;
			}
			Pair(){
				
			}
			Pair(int u, int v, int i){
				this.u = u;
				this.v = v;
				this.i = i;
			}
			public int hashCode() {
				return Objects.hash();
			}
			public boolean equals(Object o) {
				Pair other = (Pair) o;
				return ((u == other.u && v == other.v)); 
			}
			public int compareTo(Pair other) {
				//return Integer.compare(val, other.val);
				return Long.compare(u, other.u) != 0 ? (Long.compare(u, other.u)) : (Long.compare(v,other.v));
			}
			public String toString(){
				return this.u +" " + this.v;
			}
		}
		int max(int a, int b){
			if(a>b) return a;
			return b;
		}
		public static class FenwickTree {
			
		    int[] array; // 1-indexed array, In this array We save cumulative information to perform efficient range queries and updates
	 
		    public FenwickTree(int size) {
		        array = new int[size + 1];
		    }
		    public int rsq(int ind) {
		        assert ind > 0;
		        int sum = 0;
		        while (ind > 0) {
		            sum += array[ind];
		            //Extracting the portion up to the first significant one of the binary representation of 'ind' and decrementing ind by that number
		            ind -= ind & (-ind);
		        }
		        return sum;
		    }
		    public int rsq(int a, int b) {
		        assert b >= a && a > 0 && b > 0;
		        return rsq(b) - rsq(a - 1);
		    }
		    public void update(int ind, int value) {
		        assert ind > 0;
		        while (ind < array.length) {
		            array[ind] += value;
		            //Extracting the portion up to the first significant one of the binary representation of 'ind' and incrementing ind by that number
		            ind += ind & (-ind);
		        }
		    }
		    public int size() {
		        return array.length - 1;
		    }
		}
		void buildGraph(int n){
			for(int i = 0; i<n ;i++){
				int x1 = ni() -1, y1 = ni()-1;
				amp[x1].add(y1);
				amp[y1].add(x1);
				x[i] = x1; y[i] = y1;
			}
		}
		long modInverse(long a, long mOD2){
	        return  power(a, mOD2-2, mOD2);
		}
		long power(long x, long y, long m)
		{
			if (y == 0)
	    return 1;
		long p = power(x, y/2, m) % m;
		p = (p * p) % m;
	 
		return (y%2 == 0)? p : (x * p) % m;
		}
		public long gcd(long a, long b){
			if(b==0) return a;
			return gcd(b,a%b);
		}
		static class ST1{
			int arr[], st[], size;
			ST1(int a[]){
				arr = a.clone();
				size = 10*arr.length;
				st = new int[size];
				build(0,arr.length-1,1);
			}
			void build(int ss, int se, int si){
				if(ss==se){
					st[si] = arr[ss];
					return;
				}
				int mid = (ss+se)/2;
				int val = 2*si;
				build(ss,mid,val); build(mid+1,se,val+1);
				st[si] = Math.min(st[val], st[val+1]);
			}
			int get(int ss, int se, int l, int r, int si){
				if(l>se || r<ss || l>r) return Integer.MAX_VALUE;
				if(l<=ss && r>=se) return st[si];
				int mid = (ss+se)/2;
				int val = 2*si;
				return Math.min(get(ss,mid,l,r,val), get(mid+1,se,l,r,val+1));
			}
		}
		static class ST{
			int arr[],lazy[],n;
			ST(int a){
				n = a;
				arr = new int[10*n];
				lazy = new int[10*n];
			}
			void up(int l,int r,int val){
				update(0,n-1,0,l,r,val);
			}
			void update(int l,int r,int c,int x,int y,int val){
				if(lazy[c]!=0){
					lazy[2*c+1]+=lazy[c];
					lazy[2*c+2]+=lazy[c];
					if(l==r)
						arr[c]+=lazy[c];
					lazy[c] = 0;
				}
				if(l>r||x>y||l>y||x>r)
					return;
				if(x<=l&&y>=r){
					lazy[c]+=val;
					return ;
				}
				int mid = l+r>>1;
				update(l,mid,2*c+1,x,y,val);
				update(mid+1,r,2*c+2,x,y,val);
				arr[c] = Math.max(arr[2*c+1], arr[2*c+2]);
			}
			int an(int ind){
				return ans(0,n-1,0,ind);
			}
			int ans(int l,int r,int c,int ind){
				if(lazy[c]!=0){
					lazy[2*c+1]+=lazy[c];
					lazy[2*c+2]+=lazy[c];
					if(l==r)
						arr[c]+=lazy[c];
					lazy[c] = 0;
				}
				if(l==r)
					return arr[c];
				int mid = l+r>>1;
				if(mid>=ind)
					return ans(l,mid,2*c+1,ind);
				return ans(mid+1,r,2*c+2,ind);
			}
		}
		public static int[] shuffle(int[] a, Random gen){
			for(int i = 0, n = a.length;i < n;i++)
			{ 
				int ind = gen.nextInt(n-i)+i; 
				int d = a[i]; 
				a[i] = a[ind];
				a[ind] = d; 
			} 
		return a; 
		}
		long power(long x, long y, int mod){
			long ans = 1;
			while(y>0){
				if(y%2==0){
					x = (x*x)%mod;
					y/=2;
				}
				else{
					ans = (x*ans)%mod;
					y--;
				}
			}
			return ans;
		}
	 
	 
		// To Get Input
		// Some Buffer Methods
		private byte[] inbuf = new byte[1024];
		public int lenbuf = 0, ptrbuf = 0;
	 
		private int readByte() {
			if (lenbuf == -1)
				throw new InputMismatchException();
			if (ptrbuf >= lenbuf) {
				ptrbuf = 0;
				try {
					lenbuf = is.read(inbuf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (lenbuf <= 0)
					return -1;
			}
			return inbuf[ptrbuf++];
		}
	 
		private boolean isSpaceChar(int c) {
			return !(c >= 33 && c <= 126);
		}
	 
		private int skip() {
			int b;
			while ((b = readByte()) != -1 && isSpaceChar(b))
				;
			return b;
		}
	 
		private double nd() {
			return Double.parseDouble(ns());
		}
	 
		private char nc() {
			return (char) skip();
		}
		private String ns() {
			int b = skip();
			StringBuilder sb = new StringBuilder();
			while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
										// ')
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}
	 
		private char[] ns(int n) {
			char[] buf = new char[n];
			int b = skip(), p = 0;
			while (p < n && !(isSpaceChar(b))) {
				buf[p++] = (char) b;
				b = readByte();
			}
			return n == p ? buf : Arrays.copyOf(buf, p);
		}
	 
		private char[][] nm(int n, int m) {
			char[][] map = new char[n][];
			for (int i = 0; i < n; i++)
				map[i] = ns(m);
			return map;
		}
	 
		private int[] na(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = ni();
			return a;
		}
	 
		private int ni() {
			int num = 0, b;
			boolean minus = false;
			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
				;
			if (b == '-') {
				minus = true;
				b = readByte();
			}
	 
			while (true) {
				if (b >= '0' && b <= '9') {
					num = num * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
				b = readByte();
			}
		}
	 
		private long nl() {
			long num = 0;
			int b;
			boolean minus = false;
			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
				;
			if (b == '-') {
				minus = true;
				b = readByte();
			}
	 
			while (true) {
				if (b >= '0' && b <= '9') {
					num = num * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
				b = readByte();
			}
		}
	 
		private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
	 
		private void tr(Object... o) {
			if (!oj)
				System.out.println(Arrays.deepToString(o));
		}
	} 