#917. 2D prefix sums
You get a matrix, then q queries `r1 c1 r2 c2`. For each query print the sum of the elements inside the rectangle (counting from 1).
### Input
n m, n lines of the matrix, q, then q lines of queries.
### Output
q lines.
Examples
Input
2 1 -9 -1 3 1 1 2 1 2 1 2 1 2 1 2 1
Output
-10 -1 -1
Input
5 1 2 -4 5 5 3 3 5 1 5 1 3 1 3 1 3 1 5 1
Output
3 5 13
💡 You can solve it with Python, JavaScript or blocks. Read the input line by line with input(). Don't print a question (like input("Number: ")). Print exactly what the output asks for, nothing more.