题目描述

给出两个n*n的矩阵，m次询问它们的积中给定子矩阵的数值和。(n<=2000, m<=100000, 矩阵元素 < 10^9)

输入

第一行两个正整数n，m。

接下来n行，每行n个非负整数，表示第一个矩阵。

接下来n行，每行n个非负整数，表示第二个矩阵。

接下来m行，每行四个正整数a，b，c，d，表示询问第一个矩阵与第二个矩阵的积中，以第a行第b列与第c行第d列为顶点的子矩阵中的元素和。

输出

对每次询问，输出一行一个整数，表示该次询问的答案。

样例输入

3 2
1 9 8
3 2 0
1 8 3
9 8 4
0 5 15
1 9 6
1 1 3 3
2 3 1 2

样例输出

661
388