{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n\u003cdiv class\u003d\"panel_content\"\u003e\n Kazari has an array $A$ length of $L$, she plans to generate an infinite matrix $M$ using $A$.\n \u003cbr\u003eThe procedure is given below in C/C++:\n \u003cbr\u003e\n \u003cbr\u003eint cursor \u003d 0;\n \u003cbr\u003e\n \u003cpre\u003efor (int i \u003d 0; ; ++i) {\u003cbr\u003e for (int j \u003d 0; j \u0026lt;\u003d i; ++j) { \u003cbr\u003e M[j][i - j] \u003d A[cursor];\u003cbr\u003e cursor \u003d (cursor + 1) % L;\u003cbr\u003e }\u003cbr\u003e}\u003c/pre\u003e\n \u003cbr\u003e\n \u003cbr\u003eHer friends don\u0027t believe that she has the ability to generate such a huge matrix, so they come up with a lot of queries about $M$, each of which focus the sum over some sub matrix. Kazari hates to spend time on these boring queries. She asks you, an excellent coder, to help her solve these queries.\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input contains an integer $T$ $(1 \\le T \\le 100)$ denoting the number of test cases.\n\u003cbr\u003eEach test case starts with an integer $L$ $(1 \\le L \\le 10)$ denoting the length of $A$.\n\u003cbr\u003eThe second line contains $L$ integers $A_0, A_1, ..., A_{L - 1}$ $(1 \\le A_i \\le 100)$.\n\u003cbr\u003eThe third line contains an integer $Q$ $(1 \\le Q \\le 100)$ denoting the number of queries.\n\u003cbr\u003eEach of next $Q$ lines consists of four integers $x_0, y_0, x_1, y_1$ $(0 \\le x_0 \\le x_1 \\le 10 ^ 8, 0 \\le y_0 \\le y_1 \\le 10 ^ 8)$ querying the sum over the sub matrix whose upper-leftmost cell is $(x_0, y_0)$ and lower-rightest cell is $(x_1, y_1)$."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, print an integer representing the sum over the specific sub matrix for each query."}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e1\t\t\r\n3\t\t\r\n1 10 100\r\n5\t\t\r\n3 3 3 3\r\n2 3 3 3\r\n2 3 5 8\r\n5 1 10 10\r\n9 99 999 1000\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e1\r\n101\r\n1068\r\n2238\r\n33076541\u003c/pre\u003e"}}]}