Gym

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

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

题意：给定矩阵，问有多少个非空子矩阵满足矩阵中最大值-最小值<=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=401;
const int inf=1<<30;
int a[maxn][maxn],Mx[maxn],Mn[maxn],q[maxn][2],N,M,Q;
void solve(int K)
{
    ll res=0;
    rep(i,1,N){
        rep(p,1,M) Mx[p]=-inf,Mn[p]=inf;
        rep(j,i,N){
            rep(p,1,M) Mx[p]=max(Mx[p],a[j][p]);
            rep(p,1,M) Mn[p]=min(Mn[p],a[j][p]);
             int l=1,h0=0,t0=1,h1=0,t1=1;
             rep(r,1,M){
                 while(t0<=h0&&Mx[r]>=Mx[q[h0][0]]) h0--;
                 while(t1<=h1&&Mn[r]<=Mn[q[h1][1]]) h1--;
                 q[++h0][0]=r; q[++h1][1]=r;
                 while(l<=r&&Mx[q[t0][0]]-Mn[q[t1][1]]>K){
                     l++; //移动得很巧妙。 
                     if(q[t0][0]<l) t0++;
                     if(q[t1][1]<l) t1++;
                }
                res+=r-l+1;
            }
        }
    }
    printf("%I64d
",res);
}
int main()
{
    scanf("%d%d%d",&N,&M,&Q);
    rep(i,1,N) rep(j,1,M) scanf("%d",&a[i][j]);
    while(Q--){
        int k; scanf("%d",&k);
        solve(k);
    }
    return 0;
}