Mike has grown extremely bored of playing snakes and ladders. So, with his mind cleared after a hike, Mike sat down and began devising his own board game!

The game involves a grid of cells, with each cell containing a non-negative integer. Initially, a token is placed on the top-left corner of the grid. Then, in one move, the token is moved to the cell directly to the right or down, with the token not allowed to move out of the grid. Moves are made until the token reaches the bottom-right corner. Then, the total score is the sum of the integers written in the cells visited by the token. The smaller the score, the better.

To make things more interesting, before the game starts, players are allowed to change the integer written on at most ~Z~ cells to ~0~. This allows them to potentially achieve lower scores.

Mike has constructed a grid with ~N~ rows and ~M~ columns, and wants you to help him answer ~Q~ queries. Denote ~(X, Y)~ as the cell in the ~X~-th row and ~Y~-th column, and let ~G_{X, Y}~ be the integer written in cell ~(X, Y)~. In the ~i~-th query, you have been asked to determine the smallest possible score if the game was to be played on the subgrid with the top-left corner of ~(A_i, B_i)~ and bottom-right corner of ~(C_i, D_i)~, and ~Z = K_i~. Each query is completely independent (updating the value of cells does not persist between queries), and the token must always lie within the relevant subgrid for each query.

Constraints

~1 \le N, M \le 200~

~1 \le Q \le 10^5~

~1 \le G_{X, Y} \le 10^9~

~1 \le A_i \le C_i \le N~

~1 \le B_i \le D_i \le M~

~(A_i, B_i) \ne (C_i, D_i)~

~1 \le K_i \le 5~

Subtask 1 [20%]

~1 \le Q \le 200~

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains three integers, ~N, M, Q~.

The ~i~-th of the following ~N~ lines contains ~M~ integers, ~G_{i, 1}, G_{i, 2}, \dots, G_{i, M}~.

The ~i~-th of the following ~Q~ lines contains five integers, ~A_i, B_i, C_i, D_i, K_i~.

Output Specification

Print ~Q~ lines of output. The ~i~-th line should contain a single integer, representing the answer for the ~i~-th query.

Sample Input

2 3 2
2 3 5
4 1 8
1 1 1 3 1
1 2 2 3 1

Sample Output

5
4

Explanation

In the first query, after updating the cell containing ~5~ to contain ~0~, the token can visit the cell containing the integers ~2, 3, 0~ in that order.

In the second query, after updating the cell containing ~8~ to contain ~0~, the token can visit the cell containing the integers ~3, 1, 0~ in that order.