题目描述

给定一个有 N 行 M 列的表格，记第 x 行第 y 列中的数为 a(x,y)。现在需要回答 Q 个询问，询问形式如下：

对于两格 (x_s, y_s) 和 (x_t, y_t)，其中 x_s <= x_t 且 y_s <= y_t，求一条从 (x_s, y_s) 出发、到 (x_t, y_t) 结束的路径上所有格子数字之和的最小值。要求路径只能向下或向右移动。

更形式化地说，对每个询问，要求最小化：

a(x_1,y_1) + a(x_2,y_2) + ... + a(x_k,y_k)

其中格子序列 ⟨(x_1, y_1), …, (x_k, y_k)⟩ 满足：

1. x_1 = x_s 且 y_1 = y_s；
2. x_k = x_t 且 y_k = y_t；
3. 对任意 1 <= i < k，都有
   • (x_{i+1}, y_{i+1}) = (x_i + 1, y_i)，或
   • (x_{i+1}, y_{i+1}) = (x_i, y_i + 1)。

请编写程序 tq，在给定表格后回答上述询问。

输入格式

第一行包含三个正整数 N、M、Q，分别表示表格的行数、列数以及询问个数。

接下来 N 行，每行包含 M 个整数，表示表格中的数。第 i 行输入 a(i,1), a(i,2), ..., a(i,M)。

接下来 Q 行，每行包含四个整数 x_s, y_s, x_t, y_t，表示一个询问。

输出格式

输出 Q 行，每行输出对应询问的答案，即从 (x_s, y_s) 到 (x_t, y_t) 的最小路径和。

数据范围

• 1 <= N * M <= 200000
• 1 <= Q <= 200000
• 对每个单元格 (x, y)，都有 |a(x,y)| <= 10^4

子任务

样例

输入

5 5 6
1 2 1 1 1
1 1 3 2 2
1 1 1 1 1
1 3 3 1 1
2 3 3 1 1
1 1 4 4
2 2 5 5
1 1 1 4
1 1 2 4
2 2 4 3
1 1 5 5

输出

7
7
5
7
6
9