问题描述

公园可以看作由 $n\times m$ 个矩形区域构成。每个区域都有一盏灯，初始亮度为 $a[i][j]$。

小蓝可以选择一个矩形区域并按下开关一次：该区域内每盏灯的亮度减少 $1$，但每盏灯最多只能减少到 $a[i][j]-c$。如果某盏灯此时亮度已为 $a[i][j]-c$，再次按该区域的开关会使该灯的亮度恢复为 $a[i][j]$（即对每盏灯而言，按开关相当于在两个状态间切换：原亮度与降低 $c$ 后的亮度，按一次切换一次）。

现在小蓝将进行 $t$ 次操作。每次操作他会选择一个矩形区域，左上角为 $(x_1,y_1)$，右下角为 $(x_2,y_2)$，然后将该区域内所有灯按下 $k$ 次开关。每次操作结束后，他想知道该矩形区域内所有灯的总亮度是多少。在下一次操作前，他会将公园内所有灯恢复为初始亮度。

数据保证每盏灯的亮度不会减少至负数。

输入格式

第一行包含三个正整数 $n,\ m,\ c$。

接下来 $n$ 行，每行 $m$ 个正整数，表示矩阵 $a$ 的初始亮度（第 $i$ 行为 $a[i][1]\ a[i][2]\ \dots\ a[i][m]$）。

第 $n+2$ 行包含一个正整数 $t$，表示操作次数。

接下来 $t$ 行，每行包含 $5$ 个正整数 $x_1\ y_1\ x_2\ y_2\ k$，表示一次操作的矩形左上角 $(x_1,y_1)$、右下角 $(x_2,y_2)$ 以及按下开关的次数 $k$。

输出格式

输出 $t$ 行，每行一个正整数，第 $i$ 行为第 $i$ 次操作结束后对应矩形区域内所有灯的总亮度。

样例输入

3 3 3
14 14 17
13 15 18
13 16 19
3
1 1 2 2 3
2 2 3 3 5
2 3 3 3 4

样例输出

44
64
37

说明

样例解释

第一次操作，矩形为 $(1,1)$ 到 $(2,2)$，按 $k=3$ 次开关。对于矩形中每盏灯，按 $3$ 次等价于按 $3\bmod 2=1$ 次（因为按两次回到初始状态）。因此矩形内亮度从初始值降低 $1$（但不超过 $c$ 的限制），矩阵变为：

11 11 17
10 12 18
13 16 19

答案为矩形内四盏灯亮度之和： $11+11+10+12=44$。

第二次操作，矩形为 $(2,2)$ 到 $(3,3)$，按 $k=5$ 次，$5\bmod 2=1$ 次实际生效，因此矩形中每盏灯降低 $1$（不超过 $c$），矩阵变为：

14 14 17
13 14 17
13 15 18

答案为矩形内四盏灯亮度之和： $14+17+15+18=64$。

第三次操作，矩形为 $(2,3)$ 到 $(3,3)$，按 $k=4$ 次，$4\bmod 2=0$，因此灯恢复为初始亮度，矩阵仍为初始矩阵：

14 14 17
13 15 18
13 16 19

答案为矩形内两盏灯亮度之和： $18+19=37$。

数据范围

• $1\le n,m\le 300$，$1\le c\le 10$。
• $1\le t\le 10^5$，$10\le a[i][j]\le 10^9$。
• $1\le x_1\le x_2\le n$，$1\le y_1\le y_2\le m$，
• $1\le k\le 10^9$。