一维前缀和 ：

　　这个优化 ， 可以在 O （1） 的时间内计算出一个序列的和 ，

 

二维前缀和 ：

　　对于一个矩阵 ， 也可以在 O （1） 的时间内计算出矩阵 （x1~x2）( y1 ~ y2 ) 的和 。

　　sum[ i ] [ j ] 表示矩阵 1 ~ i ， 1 ~ j 的和 ， 那么由容斥原理知 sum[ 0 ] [ j ] 和 sum [ i ] [ 0 ] 均为 0 。

　　则  s[ x1 ~ x2 ] [ y1 ~ y2 ] = sum[ x2 , y2 ] + sum [ x1 - 1 ] [ y1 - 1 ] - sum [ x1 - 1 ][ y2 ] - sum [ x2 ] [ y1-1 ] 。

 

The Cartesian coordinate system is set in the sky. There you can see n stars, the i-th has coordinates (x_i, y_i), a maximum brightness c, equal for all stars, and an initial brightness s_i (0 ≤ s_i ≤ c).

Over time the stars twinkle. At moment 0 the i-th star has brightness s_i. 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 t_i and you will see a rectangle with sides parallel to the coordinate axes, the lower left corner has coordinates (x_1i, y_1i) and the upper right — (x_2i, y_2i). 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 ≤ 10⁵, 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 x_i, y_i, s_i (1 ≤ x_i, y_i ≤ 100, 0 ≤ s_i ≤ 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 t_i, x_1i, y_1i, x_2i, y_2i (0 ≤ t_i ≤ 10⁹, 1 ≤ x_1i < x_2i ≤ 100, 1 ≤ y_1i < y_2i ≤ 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.

Example

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.

 

如果这题是遍历 所有的点 ， 那么一定会超时 ， 由于灯亮度变化范围较小 ， 可以借助二维前缀和 ， 将一定范围内不同亮度的灯全部合并到一起 ， 最后对于 每次询问 ，只需要遍历所有的亮度即可 。

 

代码示例 ：

 

/* * Author:  renyi  * Created Time:  2017/8/29 9:23:49 * File Name:  */#include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    using namespace std;const int maxint = -1u>>1;#define Max(a,b) a>b?a:b#define Min(a,b) a>b?b:a#define ll long longint dp[105][105][15] ;int main() { int n , q , c ; int x , y , c1 ; while ( ~scanf ( "%d%d%d" , &n , &q , &c) ) { memset ( dp , 0 , sizeof(dp) ) ; for ( int i = 0 ; i < n ; i++ ) { scanf ( "%d%d%d" , &x , &y , &c1 ) ; dp[x][y][c1]++ ; } for ( int i = 1 ; i <= 100 ; i++ ) { for ( int j = 1 ; j <= 100 ; j++ ) { for ( int k = 0 ; k <= 10 ; k++ ) { dp[i][j][k] += dp[i-1][j][k]+dp[i][j-1][k]-dp[i-1][j-1][k] ; } } } int t , x1 , y1 , x2 , y2 ; while ( q-- ) { scanf ( "%d%d%d%d%d" , &t , &x1 , &y1 , &x2 , &y2 ) ; int sum = 0 ; for ( int i = 0 ; i <= c ; i++ ) { int s = dp[x2][y2][i] + dp[x1-1][y1-1][i] - dp[x1-1][y2][i] - dp[x2][y1-1][i] ; int l = ( t + i ) % ( c + 1 ) ; sum += s * l ; } printf ( "%d\n" , sum ) ; } } return 0;}