进取号来到了MB858星云探索未知的宇宙。他们刚进入MB858星云就被委派了收集矿石的任务。 MB858星云矿石都在一片小行星带进行开采，小行星带是一个n行m列的矩阵，矩阵的每个位置有一个非负整数a[i][j]，有q次询问，每次询问求一个左上角为(a,b)，右下角为(c,d)的子矩阵的所有数之和。

输入描述

第一行两个整数n,m，表示矩阵的行和列的大小 接下来n行每行m个整数，为矩阵内容 接下来一行为一个整数q，表示询问次数 接下来q行每行4个整数a,b,c,d，含义见题面。

输出描述

共q行，第i行为第i个询问的答案。

输入样例1

3 5
1 2 3 4 5
3 2 1 4 7
2 4 2 1 2
3
1 1 3 5
2 2 3 3
1 1 3 3

输出样例1

43
9
20

提示

【数据规模与约定】 对于30%的数据：0 <= n，m， q <= 10，a[i][j] <= 1000。 对于60%的数据：0 <= n，m， q <= 5000，a[i][j] <= 1000。 对于100%的数据：n * m <= 1000000，a[i][j] <= 100000，q <= 100000，1 <= a <= c <= n，1 <= b <= d <= m。