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.*;

public class C {

  private static final String REGEX = " ";
  private static final Boolean DEBUG = false;
  private static final String FILE_NAME = "input.txt";


  public static void main(String[] args) throws IOException {
    if (DEBUG) {
      generate();
    }
    Solver solver = new Solver();
    solver.readData();
    solver.solve();
    solver.print();
  }

  private static void generate() throws IOException {
//    FileWriter writer = new FileWriter("input.txt");
//    writer.close();
  }

  private static class Solver {
    private StringBuilder myStringBuilder = new StringBuilder();
    int n, q, c;
    int[] xi, yi, si;
    int[] ti, x1i, y1i, x2i, y2i;

    void readData() throws IOException {
      Scanner scanner = new Scanner();
      n = scanner.nextInt();
      q = scanner.nextInt();
      c = scanner.nextInt();
      xi = new int[n];
      yi = new int[n];
      si = new int[n];
      for (int i = 0; i < n; i++) {
        xi[i] = scanner.nextInt();
        yi[i] = scanner.nextInt();
        si[i] = scanner.nextInt();
      }
      ti = new int[q];
      x1i = new int[q];
      y1i = new int[q];
      x2i = new int[q];
      y2i = new int[q];

      for (int i = 0; i < q; i++) {
        ti[i] = scanner.nextInt();
        x1i[i] = scanner.nextInt();
        y1i[i] = scanner.nextInt();
        x2i[i] = scanner.nextInt();
        y2i[i] = scanner.nextInt();
      }
      scanner.close();
    }

    void solve() {
      int[][][] shine = new int[101][101][c + 1];
      int xcur;
      int ycur;
      int scur;
      int[][] shineX;
      for (int i = 0; i < n; i++) {
        xcur = xi[i];
        ycur = yi[i];
        scur = si[i];
        shineX = shine[xcur];
        for (int j = ycur; j <= 100; j++) {
          shineX[j][scur]++;
        }
      }

      int t;
      int x1;
      int y1;
      int x2;
      int y2;
      int result;

      for (int i = 0; i < q; i++) {
        t = ti[i];
        x1 = x1i[i];
        y1 = y1i[i];
        x2 = x2i[i];
        y2 = y2i[i];

        result = 0;

        for (int x = x1; x <= x2; x++) {
          int highSum = 0;
          int lowSum = 0;
          for (int s = 0; s <= c; s++) {
            int shHigh = shine[x][y2][s];
            highSum += shHigh * ((s + t) % (c + 1));

            int shLow;
            if (y1 == 1) {
              shLow = 0;
            } else {
              shLow = shine[x][y1 - 1][s];
            }
            lowSum += shLow * ((s + t) % (c + 1));
          }
          result += highSum - lowSum;
        }
        out(result);
        newLine();
      }
    }

    void print() {
      System.out.println(myStringBuilder);
    }


    void out(Object object) {
      myStringBuilder.append(object);
    }

    void out(String string) {
      myStringBuilder.append(string);
    }

    public void out(boolean b) {
      myStringBuilder.append(b);
    }

    public void out(char c) {
      myStringBuilder.append(c);
    }

    public void out(int i) {
      myStringBuilder.append(i);
    }

    public void out(long lng) {
      myStringBuilder.append(lng);
    }

    public void out(float f) {
      myStringBuilder.append(f);
    }

    public void out(double d) {
      myStringBuilder.append(d);
    }

    public void newLine() {
      myStringBuilder.append("\n");
    }

    @SuppressWarnings("SameParameterValue")
    int[] splitInteger(String string, int n) {
      final String[] split = string.split(REGEX, n);
      int[] result = new int[split.length];
      for (int i = 0; i < n; ++i) {
        result[i] = Integer.parseInt(split[i]);
      }
      return result;
    }

    public int[] splitInteger(String string) {
      return splitInteger(string, 0);
    }


    @SuppressWarnings("SameParameterValue")
    long[] splitLong(String string, int n) {
      final String[] split = string.split(REGEX, n);
      long[] result = new long[split.length];
      for (int i = 0; i < n; ++i) {
        result[i] = Long.parseLong(split[i]);
      }
      return result;
    }

    public long[] splitLong(String string) {
      return splitLong(string, 0);
    }

    @SuppressWarnings("SameParameterValue")
    double[] splitDouble(String string, int n) {
      final String[] split = string.split(REGEX, n);
      double[] result = new double[split.length];
      for (int i = 0; i < n; ++i) {
        result[i] = Double.parseDouble(split[i]);
      }
      return result;
    }

    public double[] splitDouble(String string) {
      return splitDouble(string, 0);
    }

    @SuppressWarnings("SameParameterValue")
    String[] splitString(String string, int n) {
      return string.split(REGEX, n);
    }

    public String[] splitString(String string) {
      return splitString(string, 0);
    }

    public int max(int a, int b) {
      return Math.max(a, b);
    }

    public int max(int[] arr) {
      int max = Integer.MIN_VALUE;
      for (int x : arr) {
        max = max(max, x);
      }
      return max;
    }

    public long max(long a, long b) {
      return Math.max(a, b);
    }

    public int min(int a, int b) {
      return Math.min(a, b);
    }

    public long min(long a, long b) {
      return Math.min(a, b);
    }

    public double max(double a, double b) {
      return Math.max(a, b);
    }

    public double min(double a, double b) {
      return Math.min(a, b);
    }

    private final static int MOD = 1000000009;

    int multMod(int a, int b) {
      return ((a % MOD) * (b % MOD)) % MOD;
    }

    int sumMod(int a, int b) {
      return ((a % MOD) + (b % MOD)) % MOD;
    }

    long multMod(long a, long b) {
      return ((a % MOD) * (b % MOD)) % MOD;
    }

    long sumMod(long a, long b) {
      return ((a % MOD) + (b % MOD)) % MOD;
    }

  }

  private static class Scanner {
    private int currentIndex = 0;
    private String[] objects;
    private final BufferedReader myReader;
    private Computable<Character> charComputer;
    private Computable<Double> doubleComputer;
    private Computable<Integer> intComputer;
    private Computable<Long> longComputer;

    Scanner() throws FileNotFoundException {
      InputStream in = DEBUG ? new FileInputStream(FILE_NAME) : System.in;
      myReader = new BufferedReader(new InputStreamReader(in));
      charComputer = () -> objects[currentIndex].charAt(0);
      doubleComputer = () -> Double.parseDouble(objects[currentIndex]);
      intComputer = () -> Integer.parseInt(objects[currentIndex]);
      longComputer = () -> Long.parseLong(objects[currentIndex]);
    }

    String nextLine() throws IOException {
      objects = null;
      currentIndex = 0;
      return myReader.readLine();
    }

    int nextInt() throws IOException {
      return next(intComputer);

    }

    long nextLong() throws IOException {
      return next(longComputer);

    }

    double nextDouble() throws IOException {
      return next(doubleComputer);

    }

    char nextChar() throws IOException {
      return next(charComputer);
    }

    <T> T next(Computable<T> computer) throws IOException {
      T result;
      if (objects == null || currentIndex >= objects.length) {
        String s = myReader.readLine();
        objects = s.split(" ");
        currentIndex = 0;
      }
      result = computer.compute();
      currentIndex++;
      return result;
    }

    interface Computable<T> {
      T compute();
    }

    public void close() throws IOException {
      myReader.close();
    }
  }

}
