별이 빛나는 하늘

하늘에 The Cartesian 좌표계가 설정되어 있다. 그곳에서는 n개의 별을 볼 수 있으며, i-th 별의 좌표는 (xi, yi)이다. 모든 별에 대해 동일한 최대 밝기 c와 초기 밝기 si (0 ≤ si ≤ c)가 주어진다.

시간이 지나면서 별들은 반짝인다. 시각 0에 i-th 별의 밝기는 si이다. 시각 t에 어떤 별의 밝기가 x라고 하자. 그러면 시각 (t + 1)에 이 별의 밝기는 x + 1 ≤ c이면 x + 1이고, 그렇지 않으면 0이다.

당신은 하늘을 q번 보려고 한다. i-th 번째에는 시각 ti에 하늘을 보며, 변이 좌표축과 평행하고 왼쪽 아래 꼭짓점의 좌표가 (x1i, y1i), 오른쪽 위 꼭짓점의 좌표가 (x2i, y2i)인 직사각형을 보게 된다. 각 관측에 대해, 보이는 직사각형 안에 있는 별들의 밝기 합을 알고 싶다.

별이 직사각형의 경계 위에 있거나 그 내부에 엄밀히 들어 있으면 그 별은 직사각형 안에 있다.

첫째 줄에는 세 정수 n, q, c (1 ≤ n, q ≤ 105, 1 ≤ c ≤ 10)가 주어진다. 각각 별의 개수, 관측 횟수, 별의 최대 밝기를 나타낸다.

다음 n개의 줄에는 별에 대한 설명이 주어진다. 이 줄들 중 i-th 줄에는 세 정수 xi, yi, si (1 ≤ xi, yi ≤ 100, 0 ≤ si ≤ c ≤ 10)가 주어진다. 이는 i-th 별의 좌표와 초기 밝기를 나타낸다.

다음 q개의 줄에는 관측에 대한 설명이 주어진다. 이 줄들 중 i-th 줄에는 다섯 정수 ti, x1i, y1i, x2i, y2i (0 ≤ ti ≤ 109, 1 ≤ x1i < x2i ≤ 100, 1 ≤ y1i < y2i ≤ 100)가 주어진다. 이는 i-th 관측의 시각과 보이는 직사각형의 좌표를 나타낸다.

각 관측에 대해 보이는 별들의 밝기 합을 출력한다.

첫 번째 예제를 살펴보자.

첫 번째 관측에서는 첫 번째 별만 볼 수 있다. 시각 2에 그 밝기는 3이므로 답은 3이다.

두 번째 관측에서는 두 번째 별만 볼 수 있다. 시각 0에 그 밝기는 0이므로 답은 0이다.

세 번째 관측에서는 두 별을 모두 볼 수 있다. 시각 5에 첫 번째 별의 밝기는 2이고 두 번째 별의 밝기는 1이므로 답은 3이다.