{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eTHE END IS COMINGGGGGG!\u003cbr\u003e\u003cbr\u003eMike has got stuck on a mystery machine. If he cannot solve this problem, he will go to his doom.\u003cbr\u003e\u003cbr\u003eThis machine is consist of $n$ cells, and a screen. The $i$-th cell contains a number $a_i(1 \\leq i \\leq n)$. The screen also contains a number $s$, which is initially $0$.\u003cbr\u003e\u003cbr\u003eThere is a button on each cell. When the $i$-th is pushed, Mike observes that, the number on the screen will be changed to $s + a_i$, where $s$ is the original number. and the number on the $i$-th cell will be changed to $a_i^2$.\u003cbr\u003e\u003cbr\u003eMike observes that the number is stored in radix $p$, where $p \u003d 9223372034707292160$. In other words\u0026nbsp;\u0026nbsp;, the operation is under modulo $p$. \u003cbr\u003e\u003cbr\u003eAnd now, Mike has got a list of operations. One operation is to push buttons between from $l$-th to $r$-th (both included), and record the number on the screen. He is tired of this stupid work, so he asks for your help. Can you tell him, what are the numbers recorded.\u003cbr\u003e\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer $T$($T \\le 5$), denoting the number of test cases.\u003cbr\u003e\u003cbr\u003eFor each test case, the first line contains two integers $n, m$($1 \\leq n, m\\leq 10^5$).\u003cbr\u003e\u003cbr\u003eThe next line contains $n$ integers $a_i$($0 \\leq a_i \u0026lt; p$), which means the initial values of the $n$ cells.\u003cbr\u003e\u003cbr\u003eThe next $m$ lines describe operations. In each line, there are two integers $l, r (1 \\leq l \\leq r \\leq n)$, representing the operation.\u003cbr\u003e\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output \u0027\u0027Case #t:\u0027\u0027, to represent this is the $t$-th case. And then output the answer for each query operation, one answer in a line.\u003cbr\u003e\u003cbr\u003eFor more details you can take a look at the example.\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n4 4\r\n2 3 4 5\r\n1 2\r\n2 3\r\n3 4\r\n1 4\r\n1 3\r\n2\r\n1 1\r\n1 1\r\n1 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1:\r\n5\r\n18\r\n39\r\n405\r\nCase #2:\r\n2\r\n6\r\n22\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}