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.*;
import java.io.*;

public class c {

	public static void main(String [] args) {
		JoltyScanner in = new JoltyScanner(System.in);
		int n = in.nextInt(), q = in.nextInt(), c = in.nextInt();

		BIT2D[] bits = new BIT2D[c+1];
		for (int i = 0; i < bits.length; ++i)
			bits[i] = new BIT2D(101, 101);

		for (int i = 0, x, y, s; i < n; ++i) {
			x = in.nextInt(); y = in.nextInt();
			s = in.nextInt();

			bits[s].update(x, y, 1);
		}

		PrintWriter out = new PrintWriter(System.out);

		for (int t,x1,y1,x2,y2; q --> 0; ) {
			t = in.nextInt(); x1 = in.nextInt();
			y1 = in.nextInt(); x2 = in.nextInt();
			y2 = in.nextInt();

			long ret = 0;
			for (int bit = 0; bit < bits.length; ++bit)
				ret += ((bit + t)%bits.length) * bits[bit].query(x1,y1,x2,y2);
			out.println(ret);
		}

		out.flush(); out.close();
	}

	static class BIT2D {
		private long[][] tree;

		public BIT2D(int x, int y) { tree = new long[x + 1][y + 1]; }

		public long query(int x, int y) {
			long val = 0;
			while (x > 0) {
				int y1 = y;
				while (y1 > 0) {
					val += tree[x][y1];
					y1 -= y1 & -y1;
				}
				x -= x & -x;
			}
			return val;
		}

		public long query(int start_x, int start_y, int end_x, int end_y) {
			return query(end_x,end_y) - query(start_x-1,end_y) - query(end_x,start_y-1) + query(start_x-1,start_y-1);
		}

		public long queryAt(int x, int y) { return query(x,y,x,y); }

		public void update(int x, int y, long val) {
			int y1;
			while (x < tree.length) {
				y1 = y;
				while (y1 < tree[x].length) {
					tree[x][y1] += val;
					y1 += (y1 & -y1);
				}
				x += (x & -x);
			}
		}
	}

	static class JoltyScanner
	{
		public static final int BUFFER_SIZE = 1 << 16;
		public static final char NULL_CHAR = (char) -1;
		byte[] buffer = new byte[BUFFER_SIZE];
		boolean EOF_FLAG = false;
		int bufferIdx = 0, size = 0;
		char c = NULL_CHAR;
		BufferedInputStream in;
		public JoltyScanner(InputStream in)
		{
			this.in = new BufferedInputStream(in, BUFFER_SIZE);
		}
		public int nextInt()
		{
			long x = nextLong();
			if (x > Integer.MAX_VALUE || x < Integer.MIN_VALUE)
			{
				throw new ArithmeticException("Scanned value overflows integer");
			}
			return (int) x;
		}
		public long nextLong()
		{
			boolean negative = false;
			if (c == NULL_CHAR)
			{
				c = nextChar();
			}
			for (; !EOF_FLAG && (c < '0' || c > '9'); c = nextChar())
			{
				if (c == '-')
				{
					negative = true;
				}
			}
			checkEOF();
			long res = 0;
			for (; c >= '0' && c <= '9'; c = nextChar())
			{
				res = (res << 3) + (res << 1) + c - '0';
			}
			return negative ? -res : res;
		}
		public char nextChar()
		{
			if (EOF_FLAG)
			{
				return NULL_CHAR;
			}
			while (bufferIdx == size)
			{
				try
				{
					size = in.read(buffer);
					if (size == -1)
					{
						throw new Exception();
					}
				}
				catch (Exception e)
				{
					EOF_FLAG = true;
					return NULL_CHAR;
				}
				if (size == -1)
				{
					size = BUFFER_SIZE;
				}
				bufferIdx = 0;
			}
			return (char) buffer[bufferIdx++];
		}
		public void checkEOF()
		{
			if (EOF_FLAG)
			{
				throw new EndOfFileException();
			}
		}
		public class EndOfFileException extends RuntimeException
		{
		}
	}
}
