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.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.OutputStream;
public class B{
	
	
	public static void main(String[] args) {
		
		Kattio kat = new Kattio(System.in);
		int n_stars = kat.getInt();
		int n_views = kat.getInt();
		int max_b = kat.getInt();
		int[][][] stars = new int[101][101][max_b+1];
		int[][][] dp = new int[101][101][max_b+1];
		for(int i = 0;i<n_stars;i++) {
			int x = kat.getInt();
			int y = kat.getInt();
			int s = kat.getInt();
			stars[x][y][s] +=1;
		}
		
		for(int x = 1;x<101;x++) {
			for(int y = 1;y<101;y++) {
				for(int p=0;p<max_b+1;p++) {
					dp[x][y][p] = dp[x-1][y][p] + dp[x][y-1][p] - dp[x-1][y-1][p] + stars[x][y][p];
				}
			}
		}
		
		for(int i = 0;i<n_views;i++) {
			int t=kat.getInt();
			int x1 = kat.getInt();
			int y1 = kat.getInt();
			int x2 = kat.getInt();
			int y2 = kat.getInt();
			int total = 0;
			for(int p = 0;p<max_b+1;p++) {
				total += ((t+p)%(max_b+1) )* (dp[x2][y2][p] - dp[x1-1][y2][p]-dp[x2][y1-1][p] + dp[x1-1][y1-1][p]);
			}
			System.out.println(total);
		}
	}
}
/** Simple yet moderately fast I/O routines.
*
* Example usage:
*
* Kattio io = new Kattio(System.in, System.out);
*
* while (io.hasMoreTokens()) {
*    int n = io.getInt();
*    double d = io.getDouble();
*    double ans = d*n;
*
*    io.println("Answer: " + ans);
* }
*
* io.close();
*
*
* Some notes:
*
* - When done, you should always do io.close() or io.flush() on the
*   Kattio-instance, otherwise, you may lose output.
*
* - The getInt(), getDouble(), and getLong() methods will throw an
*   exception if there is no more data in the input, so it is generally
*   a good idea to use hasMoreTokens() to check for end-of-file.
*
* @author: Kattis
*/



class Kattio extends PrintWriter {
   public Kattio(InputStream i) {
       super(new BufferedOutputStream(System.out));
       r = new BufferedReader(new InputStreamReader(i));
   }
   public Kattio(InputStream i, OutputStream o) {
       super(new BufferedOutputStream(o));
       r = new BufferedReader(new InputStreamReader(i));
   }

   public boolean hasMoreTokens() {
       return peekToken() != null;
   }

   public int getInt() {
       return Integer.parseInt(nextToken());
   }

   public double getDouble() {
       return Double.parseDouble(nextToken());
   }

   public long getLong() {
       return Long.parseLong(nextToken());
   }

   public String getWord() {
       return nextToken();
   }



   private BufferedReader r;
   private String line;
   private StringTokenizer st;
   private String token;

   private String peekToken() {
       if (token == null)
           try {
               while (st == null || !st.hasMoreTokens()) {
                   line = r.readLine();
                   if (line == null) return null;
                   st = new StringTokenizer(line);
               }
               token = st.nextToken();
           } catch (IOException e) { }
       return token;
   }

   private String nextToken() {
       String ans = peekToken();
       token = null;
       return ans;
   }
}
