write a go solution for H. Hard Demon Problemtime limit per test3.5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputSwing is opening a pancake factory! A good pancake factory must be good at flattening things, so Swing is going to test his new equipment on 2D matrices.Swing is given an nxn matrix M containing positive integers. He has q queries to ask you. For each query, he gives you four integers x_1, y_1, x_2, y_2 and asks you to flatten the submatrix bounded by (x_1,y_1) and (x_2,y_2) into an array A. Formally, A=[M_(x1,y1),M_(x1,y1+1),ldots,M_(x1,y2),M_(x1+1,y1),M_(x1+1,y1+1),ldots,M_(x2,y2)]. The following image depicts the flattening of a submatrix bounded by the red dotted lines. The orange arrows denote the direction that the elements of the submatrix are appended to the back of A, and A is shown at the bottom of the image.     Afterwards, he asks you for the value of sum_i=1^|A|A_i*i (sum of A_i*i over all i).InputThe first line contains an integer t (1<=t<=10^3) — the number of test cases.The first line of each test contains two integers n and q (1<=n<=2000,1<=q<=10^6) — the length of M and the number of queries.The following n lines contain n integers each, the i'th of which contains M_(i,1),M_(i,2),ldots,M_(i,n) (1<=M_(i,j)<=10^6).The following q lines contain four integers x_1, y_1, x_2, and y_2 (1<=x_1<=x_2<=n,1<=y_1<=y_2<=n) — the bounds of the query.It is guaranteed that the sum of n over all test cases does not exceed 2000 and the sum of q over all test cases does not exceed 10^6.OutputFor each test case, output the results of the q queries on a new line.ExampleInput24 31 5 2 44 9 5 34 5 2 31 5 5 21 1 4 42 2 3 31 2 4 33 31 2 34 5 67 8 91 1 1 31 3 3 32 2 2 2Output500 42 168 
14 42 5 
NoteIn the second query of the first test case, A=[9,5,5,2]. Therefore, the sum is 1*9+2*5+3*5+4*2=42.. Output only the code with no comments, explanation, or additional text.