Gym – 100570C： Subrect Query （巧妙的单调队列）

De Prezer loves rectangles.He has a n × m rectangle which there is a number in each of its cells. We show the number in the j - th column of the i - th row by a_i, j.

De Prezer also loves query. So he gives you q queries. In each query, he gives you number k and asks you to print the number of subrectangles of this rectangle that the difference between the maximum element and the minimum element in them is at most k .

Input

The first line of input contains 3 integers, n, m and q .

In the next n lines, there are informations of the rectangle. i - th line among them, contains m space separated integers, a_i, 1, a_i, 2, …, a_i, m .

The next q lines, each line contains a single integer k (for that query).

1 ≤ n, m ≤ 400

1 ≤ q ≤ 10

1 ≤ a_i, j ≤ 10⁹ (for each 1 ≤ i ≤ n and 1 ≤ j ≤ m)

0 ≤ k ≤ 10⁹ (for each query)

Output

For each query, print the answer in a single line.

Examples

Input

5 4 6
451 451 452 452
452 452 452 452
451 452 450 450
451 451 451 451
452 452 450 450
0
2
773726
724963313
1
1

Output

42
150
150
150
88
88

Input

4 5 8
1314 1287 1286 1290 1295
1278 1271 1324 1317 1289
1305 1305 1284 1300 1309
1318 1296 1301 1274 1315
976296835
12
13
38
16
40
665711658
35

Output

150
34
35
82
37
92
150
77

题意：给定矩阵，问有多少个非空子矩阵满足矩阵中最大值-最小值<=K。

思路：不难想到要压缩矩阵，即枚举枚举矩阵的上边界和下边界，然后压缩，看成一维的，如果可以线性解决一维的，则单次询问的复杂度为O（N^2*M）。

那么现在给定数组a[]，我们用一个单增队列保存最小值的位置，用一个单减队列保存最大值的位置。对于R，如果二队首对应的值之差>K，则L++，并且维护队首>=L；

（主要是两个单调队列，我们移动的不是队首，而且L，在L>队首时，弹出队首。妙啊。VJ一血？

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
using namespace std;
const int maxn=;
const int inf=<<;
int a[maxn][maxn],Mx[maxn],Mn[maxn],q[maxn][],N,M,Q;
void solve(int K)
{
    ll res=;
    rep(i,,N){
        rep(p,,M) Mx[p]=-inf,Mn[p]=inf;
        rep(j,i,N){
            rep(p,,M) Mx[p]=max(Mx[p],a[j][p]);
            rep(p,,M) Mn[p]=min(Mn[p],a[j][p]);
             int l=,h0=,t0=,h1=,t1=;
             rep(r,,M){
                 while(t0<=h0&&Mx[r]>=Mx[q[h0][]]) h0--;
                 while(t1<=h1&&Mn[r]<=Mn[q[h1][]]) h1--;
                 q[++h0][]=r; q[++h1][]=r;
                 while(l<=r&&Mx[q[t0][]]-Mn[q[t1][]]>K){
                     l++; //移动得很巧妙。
                     if(q[t0][]<l) t0++;
                     if(q[t1][]<l) t1++;
                }
                res+=r-l+;
            }
        }
    }
    printf("%I64d\n",res);
}
int main()
{
    scanf("%d%d%d",&N,&M,&Q);
    rep(i,,N) rep(j,,M) scanf("%d",&a[i][j]);
    while(Q--){
        int k; scanf("%d",&k);
        solve(k);
    }
    return ;
}