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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import java.util.StringTokenizer;


public class Main {

	static boolean visited[] ; 
	static boolean ends[] ;
	static long mod = 1000000007 ;
	static int lens[] ; 
	static int seeds[] ; 
	static int a[] ;
	static double total ; 
	public static ArrayList adj[] ; 
	public static void main(String[] args) throws IOException, InterruptedException {
		Scanner sc =  new Scanner(System.in) ;
		int n=sc.nextInt() ; 
		int q = sc.nextInt() ; 
		int c = sc.nextInt() ; 



		//	int matrix1[][][] = new int[10][100][100]; 
		int matrix[][][] = new int[c+1][101][101];

		int s[] = new int[n];
		int x[] = new int[n] ; 
		int y[] = new int[n] ; 


		for (int i = 0; i < n; i++)
		{
			x[i]=sc.nextInt() ; 
			y[i] = sc.nextInt() ; 
			s[i]=sc.nextInt() ;
			matrix[s[i]][x[i]][y[i]] ++ ; 
			//			matrix1[x[i]][y[i]] ++ ; 
		}


		int memo[][][] = new int[c+1][101][101];  //x,y
		//	int memo1[][] = new int[100][100];

		//		for (int i = 0; i <=c; i++)
		//		{
		//			memo[i][0][0] = matrix[i][0][0] ;
		//		}
		//		memo[0][0] = matrix[0][0] ; 
		//		//	memo1[0][0] = matrix1[0][0] ;
		//
		//
		//		for (int i = 1; i < 100; i++)
		//		{
		//			for (int j = 0; j <=c; j++)
		//			{
		//				memo[j][i][0]=matrix[j][i][0]+memo[j][i-1][0];
		//			}
		//
		//			//	memo1[i][0]=matrix1[i][0]+memo1[i-1][0];
		//		}
		//
		//		for (int i = 1; i <100; i++)
		//		{
		//			for (int j = 0; j <=c; j++)
		//			{
		//				memo[j][0][i]=matrix[j][0][i]+memo[j][0][i-1];
		//
		//			}
		//			//memo1[0][i]=matrix1[0][i]+memo1[0][i-1];
		//		}

		for (int i = 1; i <=100; i++)
			for (int j = 1; j <=100; j++)
				for(int k=0 ; k<=c ; k++)
				{
					memo[k][i][j]=matrix[k][i][j]+memo[k][i-1][j]+memo[k][i][j-1]-memo[k][i-1][j-1];
					//	memo1[i][j]=matrix1[i][j]+memo1[i-1][j]+memo1[i][j-1]-memo1[i-1][j-1];
				}

		//		for (int i = 0; i < 4; i++)
		//			for (int j = 0; j <4; j++)
		//			{
		//				System.err.println(i+" "+j+"  "+memo1[i][j]);
		//			}

		while (q-->0)
		{
			int t = sc.nextInt() ; 
			int x1 = sc.nextInt() ; 
			int y1 = sc.nextInt() ; 
			int x2 = sc.nextInt() ; 
			int y2 = sc.nextInt() ; 

			int A,B,C,D ;



			long ans = 0; 
			//			ans = A-B-D+C; 
			//			int num = AA-BB-DD+CC ; 
			//			ans += num*(t%(c+1)) ;
			//			System.out.println(ans);
			//			System.err.println(A+" "+B+" "+C+" "+D);
			//			System.err.println(AA+" "+BB+" "+CC+" "+DD);





			for (int i = 0; i <=c; i++)
			{
				A = memo[i][x2][y2];			

				D = memo[i][x1-1][y2] ; 
				B = memo[i][x2][y1-1];
				C = memo[i][x1-1][y1-1];

				long sum=(t+i)%(c+1); ;
				long val  = (A-B-D+C) ; 
				sum*= val ;
				//	System.err.println(val+" "+i);
				ans+= sum ;

			}

			System.out.println(ans);












		}








	}




	static int even(String x , int b )
	{
		for (int j = b; j>=0; j--)
		{
			int current = x.charAt(j)-48 ; 
			if(current%2==0)
				return current ; 
		}
		return -1;
	}
	static int odd(String x , int b )
	{
		for (int j = b; j>=0; j--)
		{
			int current = x.charAt(j)-48 ; 
			if(current%2!=0)
				return current ; 
		}
		return -1;
	}
	static long pow(long base, int exp) {
		long res = 1;
		while(exp > 0) {
			if(exp % 2 == 1) {
				res = (res * base) % mod;
			}

			base = (base * base) % mod;
			exp /= 2;
		}

		return res;
	}
	public static long solve(int k1, long k2)
	{
		long x   = 1l*k2*(pow(2, k1)-1) ;
		return x%(1000000007) ; 
	}


	public static long getN(long x)
	{
		long n = (long) Math.sqrt(x*2) ; 
		long y = n*(n+1)/2; 
		if(y==x)
			return n ; 
		else if(y>x)
			return n ; 
		else
			for (long i = n; ; i++)
			{
				y = i*(i+1)/2 ; 
				if(y>=x)
					return i ; 


			}	}








	public static void dfss(int root , int len)
	{
		visited[root]=true ; 
		if(ends[root] && root!=0) lens[root] = len ; 

		for (int i = 0; i < adj[root].size(); i++)
		{
			int c= (int) adj[root].get(i) ; 
			if(visited[c]==false)
				dfss(c, len+1);
		}
	}

	public static void pr(int root ,  int seed){
		visited[root] = true ;
		int dv = adj[root].size()-1 ; 
		if(root==0) dv++ ;

		for (int i = 0; i < adj[root].size(); i++)
		{
			int c = (int)adj[root].get(i) ; 
			seeds[c]=dv*seed ;
		}

		for (int i = 0; i < adj[root].size() ; i++)
		{
			int c = (int)adj[root].get(i) ; 
			if(visited[c]==false)
				pr(c , seeds[c]);

		}

	}


	public static String concatinate(String s ,int n)
	{
		if(s.length()==n)
			return s ; 
		else return concatinate("0"+s, n) ;
	}
	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public boolean ready() throws IOException {
			return br.ready();
		}
	}


	public static long getGCD(long n1, long n2) {
		if (n2 == 0) {
			return n1;
		}
		return getGCD(n2, n1 % n2);
	}

	public static int cnt1(int mat[][])  //how many swaps to be a 1 matrix
	{
		int m = mat.length ; 
		int c=0 ; 
		for (int i = 0; i < mat.length; i++)
		{
			for (int j = 0; j < mat.length; j++)
			{
				int x =  (i*m) +j ;
				if(x%2==0 && mat[i][j]==0)
					c++; 
				if(x%2!=0 && mat[i][j]==1)
					c++; 

			}
		}
		return c;
	}
	public static int cnt0(int mat[][])
	{
		int m = mat.length ; 
		int c=0 ; 
		for (int i = 0; i < mat.length; i++)
		{
			for (int j = 0; j < mat.length; j++)
			{
				int x =  (i*m) +j ; 
				if(x%2!=0 && mat[i][j]==0)
					c++; 
				if(x%2==0 && mat[i][j]==1)
					c++; 

			}
		}
		return c;
	}

	public static boolean canFit2(int x1, int y1 , int x2 , int y2 , int x3 , int y3){
		if(x1==x2)
			if(x1==x3)
				return true ; 
			else
				return false ;
		else
			if(x1==x3)
				return false ; 
			else
			{
				long a = 1l*(y2-y1)*(x3-x2) ; 
				long b = 1l*(y3-y2)*(x2-x1) ; 

				if(a==b)
					return true;
				else 
					return false ;

			}

	}
	public static void shuffle(long[] a2){
		if(a2.length==1)
			return ; 
		for (int i = 0; i < a2.length; i++)
		{
			Random rand = new Random();

			int  n = rand.nextInt(a2.length-1) + 0;

			long temp = a2[i] ; 
			a2[i] = a2[n] ; 
			a2[n] = temp ;
		}
	}
	public static int binary(long[]arr, int l, int r, long x)   /// begin by 0 and n-1
	{
		if (r>=l)
		{
			int mid = l + (r - l)/2;
			if (arr[mid]== x)
				return mid;
			if (arr[mid]> x)
				return binary(arr, l, mid-1, x);
			return binary(arr, mid+1, r, x);
		}
		return -1;
	}

	/// searching for the index of first elment greater than x
	public static int binary1(long[]arr , long x) {
		int low = 0, high = arr.length; // numElems is the size of the array i.e arr.size() 
		while (low != high) {
			int mid = (low + high) / 2; // Or a fancy way to avoid int overflow
			if (arr[mid] <= x) {
				/* This index, and everything below it, must not be the first element
				 * greater than what we're looking for because this element is no greater
				 * than the element.
				 */
				low = mid + 1;
			}
			else {
				/* This element is at least as large as the element, so anything after it can't
				 * be the first element that's at least as large.
				 */
				high = mid;
			}
		}
		return low ; // return high ; 
	}


	private static boolean triangle(int a, int b , int c){
		if(a+b>c && a+c>b && b+c>a)
			return true ; 
		else 
			return false ;
	}
	private static boolean segment(int a, int b , int c){
		if(a+b==c || a+c==b && b+c==a)
			return true ; 
		else 
			return false ;
	}
	private static int gcdThing(long a, long b) {
		BigInteger b1 = BigInteger.valueOf(a);
		BigInteger b2 = BigInteger.valueOf(b);
		BigInteger gcd = b1.gcd(b2);
		return gcd.intValue();
	}

	public static boolean is(int i){
		if(Math.log(i)/ Math.log(2) ==(int) (Math.log(i)/ Math.log(2)))
			return true ; 
		if(Math.log(i)/ Math.log(3) ==(int) (Math.log(i)/ Math.log(3)) )
			return true ; 
		if(Math.log(i)/ Math.log(6) ==(int) (Math.log(i)/ Math.log(6)) )
			return true ; 

		return false;

	}
	public static boolean contains(int b[] , int x)
	{
		for (int i = 0; i < b.length; i++)
		{
			if(b[i]==x)
				return true ;
		}
		return false ;
	}
	public static int binary(long []arr , long target , int low , long shift) {
		int high = arr.length; 
		while (low != high) {
			int mid = (low + high) / 2; 
			if (arr[mid]-shift <= target) {
				low = mid + 1;
			}
			else {
				high = mid;
			}
		}
		return low ; // return high ; 
	}
	public static boolean isLetter(char x){
		if(x+0 <=122 && x+0 >=97 )
			return true ;
		else if (x+0 <=90 && x+0 >=65 )
			return true ; 
		else return false; 
	}
	public static long getPrimes(long x ){
		if(x==2 || x==3 || x==1)
			return 2 ;
		if(isPrime(x))
			return 5 ;
		for (int i = 2; i*i<=x; i++)
		{
			if(x%i==0 && isPrime(i))
				return getPrimes(x/i) ;
		}
		return -1;
	}
	public static String solve11(String x){

		int n = x.length() ; 
		String y = "" ;
		for (int i = 0; i < n-2; i+=2)
		{
			if(ifPalindrome(x.substring(i, i+2)))
				y+= x.substring(i, i+2) ;
			else 
				break ;
		}
		return y+ solve11(x.substring(y.length(),x.length())) ;

	}
	public static String solve1(String x){
		String y = x.substring(0 , x.length()/2) ; 
		return "" ;

	}
	public static String reverse(String x){
		String y ="" ;
		for (int i = 0; i < x.length(); i++)
		{
			y  = x.charAt(i) + y ;
		}
		return y ;
	}

	public static boolean ifPalindrome(String x){
		int numbers[] = new int[10] ; 
		for (int i = 0; i < x.length(); i++)
		{
			int z = Integer.parseInt(x.charAt(i)+"") ; 
			numbers[z] ++ ;
		}
		for (int i = 0; i < numbers.length; i++)
		{
			if(numbers[i]%2!=0)
				return false; 
		}
		return true ;	
	}

	public static int get(int n){
		return n*(n+1)/2 ; 
	}
	//		public static long getSmallestDivisor( long y){
	//			if(isPrime(y))
	//				return -1;
	//
	//			for (long i = 2; i*i <= y; i++)
	//			{
	//				if(y%i ==0)
	//				{
	//					return i;
	//				}
	//			}
	//			return -1;
	//		}
	public static int lis( int[]a , int n){
		int lis[] = new int[n] ; 
		Arrays.fill(lis,1) ; 

		for(int i=1;i<n;i++)
			for(int j=0 ; j<i; j++)
				if (a[i]>a[j] &&  lis[i] < lis[j]+1)   
					lis[i] = lis[j] + 1;           

		int max = lis[0];

		for(int i=1; i<n ; i++)
			if (max < lis[i])
				max = lis[i] ;
		return (max);

		//			ArrayList<Integer> s = new ArrayList<Integer>() ;
		//			for (int i = n-1; i >=0; i--)
		//			{
		//				if(lis[i]==max)
		//				{
		//					s.add(a[i].z);
		//					max --; 
		//				}
		//			}
		//
		//			for (int i = s.size()-1 ; i>=0 ;  i--)
		//			{
		//				System.out.print(s.get(i)+" ");
		//			}
		//
	}
	public static int calcDepth(Vertix node){
		if(node.depth>0) return node.depth; 
		// meaning it has been updated before;
		if(node.parent != null)
			return 1+ calcDepth(node.parent);
		else
			return -1;
	}

	public static boolean isPrime (long num){
		if (num < 2) return false;
		if (num == 2) return true;
		if (num % 2 == 0) return false;
		for (int i = 3; i * i <= num; i += 2)
			if (num % i == 0) return false;
		return true;
	}


	public static ArrayList<Long> getDiv(Long n)
	{
		ArrayList<Long>  f = new ArrayList<Long>() ; 

		while (n%2==0)
		{
			if(!f.contains(2))f.add((long) 2) ;
			n /= 2;
		}

		// n must be odd at this point.  So we can
		// skip one element (Note i = i +2)
		for (long i = 3; i <= Math.sqrt(n); i+= 2)
		{
			// While i divides n, print i and divide n
			while (n%i == 0)
			{
				if(!f.contains(i))f.add(i);
				n /= i;
			}
		}

		// This condition is to handle the case whien
		// n is a prime number greater than 2
		if (n > 2)
			if(!f.contains(n))f.add(n);


		return f ;



	}

	//		public static boolean dfs(Vertix v , int target){
	//			try{
	//				visited[v.i]= true ;
	//			} catch (NullPointerException e)
	//			{
	//				System.out.println(v.i);
	//			}
	//			if(v.i == target)
	//
	//				return true ;
	//			for (int i =0 ; i< v.neighbours.size() ; i++)
	//			{ 
	//
	//				Vertix child = v.neighbours.get(i) ;
	//				if(child.i == target){
	//					found = true  ; 
	//				}
	//				if(visited[child.i]==false){
	//					found |= dfs(child, target) ;
	//				}
	//			}
	//			return found; 
	//		}









	public static class Vertix{
		long i ; 
		int depth ;
		ArrayList<Vertix> neighbours ; 
		Vertix parent ; 
		Vertix child ; 


		public Vertix(long i){
			this.i = i ;
			this.neighbours = new ArrayList<Vertix> () ;
			this.parent = null ;
			depth =-1;
			this.child = null ;
		}
	}

	public static class pair {
		int x ;
		int y ;





		public pair(int x, int y ){

			this.x=x ; 
			this.y =y ;


		}

		//
		//		@Override
		//		public int compareTo(pair p) {
		//			if(this.value > p.value)
		//				return 1 ; 
		//			else if (this.value == p.value) 
		//				return 0 ;
		//			else 
		//				return -1 ;
		//		}




	}

	public static class pair2 implements Comparable<pair2>{
		int i ; 
		int j ;
		int plus ;

		public pair2(int i , int j , int plus){
			this.i =i ;
			this.j = j ; 
			this.plus = plus ;
		}

		@Override
		public int compareTo(pair2 p) {
			if(this.j > p.j)
				return 1 ; 
			else if (this.j == p.j) return 0 ;
			else 
				return -1 ;
		}


	}


}