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.
//https://codeforces.com/problemset/problem/835/C
import java.util.Scanner;
public class Starsky
{
	public static int[][][] calculate_Modified_Prefix_Matrix_Sum(int[][][] matrix)
	{
		int m=matrix.length;
		int n=matrix[0].length;
		int[][][] modifiedPrefixMatrixSum;
		modifiedPrefixMatrixSum=new int[m][][];
		for(int i=0;i<m;i++)
		{
			modifiedPrefixMatrixSum[i]=new int[n][];
			for(int j=0;j<n;j++)
			{
				modifiedPrefixMatrixSum[i][j]=new int[11];	
			}
		}	
			
		for(int brightness=0;brightness<=10;brightness++)
			modifiedPrefixMatrixSum[0][0][brightness]=matrix[0][0][brightness];
		for(int indexrow=1;indexrow<m;indexrow++)
		{
			for(int brightness=0;brightness<=10;brightness++)
				modifiedPrefixMatrixSum[indexrow][0][brightness]=(modifiedPrefixMatrixSum[indexrow-1][0][brightness]+matrix[indexrow][0][brightness]);
		}
		for(int indexcol=1;indexcol<n;indexcol++)
		{
			for(int brightness=0;brightness<=10;brightness++)
				modifiedPrefixMatrixSum[0][indexcol][brightness]=(modifiedPrefixMatrixSum[0][indexcol-1][brightness]+matrix[0][indexcol][brightness]);
		}
		for(int indexrow=1;indexrow<m;indexrow++)
		{
			for(int indexcol=1;indexcol<n;indexcol++)
			{
				for(int brightness=0;brightness<=10;brightness++)
					modifiedPrefixMatrixSum[indexrow][indexcol][brightness]=((modifiedPrefixMatrixSum[indexrow-1][indexcol][brightness]
																				+modifiedPrefixMatrixSum[indexrow][indexcol-1][brightness]
																				-modifiedPrefixMatrixSum[indexrow-1][indexcol-1][brightness])
																				+matrix[indexrow][indexcol][brightness]);
			}
		}
		return modifiedPrefixMatrixSum;
	}
	public static int[] calculate_Modified_Submatrix_Sum(int[][][] modifiedPrefixMatrixSum,int startindexrow,int startindexcol,int endindexrow,int endindexcol)
	{
		//star_with_index_brightness is an array show number of star with brightness equal to index  
		int[] star_with_index_brightness=new int[11];
		if(startindexcol==0 && startindexrow==0)
		{
			for(int brightness=0;brightness<=10;brightness++)
				star_with_index_brightness[brightness]=modifiedPrefixMatrixSum[endindexrow][endindexcol][brightness];
		}
		else if(startindexcol==0)
		{
			for(int brightness=0;brightness<=10;brightness++)
				star_with_index_brightness[brightness]=(modifiedPrefixMatrixSum[endindexrow][endindexcol][brightness]
															-modifiedPrefixMatrixSum[startindexrow-1][endindexcol][brightness]);
		}
		else if(startindexrow==0)
		{
			for(int brightness=0;brightness<=10;brightness++)
				star_with_index_brightness[brightness]=(modifiedPrefixMatrixSum[endindexrow][endindexcol][brightness]
															-modifiedPrefixMatrixSum[endindexrow][startindexcol-1][brightness]);
		}
		else
		{
			for(int brightness=0;brightness<=10;brightness++)
				star_with_index_brightness[brightness]=(modifiedPrefixMatrixSum[endindexrow][endindexcol][brightness]
															-modifiedPrefixMatrixSum[endindexrow][startindexcol-1][brightness]
															-modifiedPrefixMatrixSum[startindexrow-1][endindexcol][brightness]
															+modifiedPrefixMatrixSum[startindexrow-1][startindexcol-1][brightness]);									
		}
		return star_with_index_brightness;
	}
	public static long calculate_Output(int[] star_with_index_brightness,int max_brightness,int time)
	{
		long total_brightness=0;
		int index;
		for(index=0;index<=10;index++)
		{
			long current_index_brightness=((index+time)%(max_brightness+1));
			current_index_brightness*=star_with_index_brightness[index];	
			total_brightness+=current_index_brightness;
		}
		return total_brightness;
	}
	public static void main(String[] args)
	{
		int number_of_stars,queries,max_brightness;
		int matrix[][][];
		Scanner sc=new Scanner(System.in);
		number_of_stars=sc.nextInt();
		queries=sc.nextInt();
		max_brightness=sc.nextInt();
		matrix=new int[101][][];
		for(int i=0;i<=100;i++)
		{
			matrix[i]=new int[101][];
			for(int j=0;j<=100;j++)
				matrix[i][j]=new int[11];
		}
		for(int i=0;i<=100;i++)
			for(int j=0;j<=100;j++)
				for(int k=0;k<=10;k++)
					matrix[i][j][k]=0;
		for(int i=0;i<number_of_stars;i++)
		{
			matrix[sc.nextInt()][sc.nextInt()][sc.nextInt()]++;			
		}
		int[][][] modifiedPrefixMatrixSum=calculate_Modified_Prefix_Matrix_Sum(matrix);
		for(int i=0;i<queries;i++)
		{
			int time=sc.nextInt();
			int startindexrow=sc.nextInt();
			int startindexcol=sc.nextInt();
			int endindexrow=sc.nextInt();
			int endindexcol=sc.nextInt();
			int[] star_with_index_brightness=calculate_Modified_Submatrix_Sum(modifiedPrefixMatrixSum,startindexrow,startindexcol,endindexrow,endindexcol);
			long total_brightness=calculate_Output(star_with_index_brightness,max_brightness,time);
			System.out.println(total_brightness);
		}
	}	
}