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.InputStreamReader;
import java.util.HashMap;

public class Solution {
  private static class Point {
    private Point(int in_x,int in_y) {
      x = in_x;
      y = in_y;
    }
    private Point(Point cp) {
      x = cp.x;
      y = cp.y;
    }
    int x;
    int y;
  }
  private static int toCanon(Point p) {
    return p.x*128+p.y;
  }

  public static void main(String[] args) throws IOException {
    // testQuad();
    //Scanner scanner = new Scanner(System.in);
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String line;
    String[] vs;
    line = in.readLine();
    vs = line.split(" ");
    int n = Integer.parseInt(vs[0]);
    int q = Integer.parseInt(vs[1]);
    int c = Integer.parseInt(vs[2]);
    HashMap<Integer,HashMap<Integer,Integer>> points = new HashMap<>();
    for (int i=0;i<n;++i) {
      line = in.readLine();
      vs = line.split(" ");
      int x = Integer.parseInt(vs[0]);
      int y = Integer.parseInt(vs[1]);
      int s = Integer.parseInt(vs[2]);
      int k = toCanon(new Point(x,y));
      HashMap<Integer,Integer> hm = points.getOrDefault(k,new HashMap<>());
      int count = hm.getOrDefault(s,0);
      count++;
      hm.put(s,count);
      points.put(k,hm);
    }

    int[][][] dp = new int[c+1][101][101];
    HashMap<Integer,Integer> hm0 = new HashMap<>();
    for (int t=0;t<c+1;++t) {
      for (int x=0;x<101;++x) {
        for (int y = 0; y < 101; ++y) {
          HashMap<Integer, Integer> hm = points.getOrDefault(toCanon(new Point(x, y)), hm0);
          for (int b : hm.keySet()) {
            int count = hm.get(b);
            b += t;
            b %= c + 1;
            dp[t][x][y] += b * count;
          }
          if (x > 0) {
            dp[t][x][y] += dp[t][x - 1][y];
          }
            if (y > 0) {
              dp[t][x][y] += dp[t][x][y - 1];
            }
            if (x > 0 && y > 0) {
              dp[t][x][y] -= dp[t][x - 1][y - 1];
            }

        }
      }
    }

    for (int i=0;i<q;++i) {
      line = in.readLine();
      vs = line.split(" ");
      int t = Integer.parseInt(vs[0]);
      int x1 = Integer.parseInt(vs[1]);
      int y1 = Integer.parseInt(vs[2]);
      int x2 = Integer.parseInt(vs[3]);
      int y2 = Integer.parseInt(vs[4]);

      t %= c+1;
      int out = dp[t][x2][y2];
      if (x1>0) {
        out -= dp[t][x1 - 1][y2];
      }
      if (y1>0) {
        out -= dp[t][x2][y1-1];
      }
      if (x1>0 && y1>0) {
        out += dp[t][x1-1][y1-1];
      }
      System.out.println(out);
    }
  }
}
