{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。\u003c/p\u003e\u003cp\u003e有长为 $$$n$$$ 的数列,不妨设为 $$$a_1,a_2,\\cdots ,a_n$$$。有如下三种操作形式: \u003c/p\u003e\u003cul\u003e \u003cli\u003e 把数列中的一段数全部乘一个值; \u003c/li\u003e\u003cli\u003e 把数列中的一段数全部加一个值; \u003c/li\u003e\u003cli\u003e 询问数列中的一段数的和,由于答案可能很大,你只需输出这个数模 $$$P$$$ 的值。 \u003c/li\u003e\u003c/ul\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e第一行两个整数 $$$n$$$ 和 $$$P$$$;\u003c/p\u003e\u003cp\u003e第二行含有 $$$n$$$ 个非负整数,从左到右依次为 $$$a_1,a_2,\\cdots ,a_n$$$;\u003c/p\u003e\u003cp\u003e第三行有一个整数 $$$M$$$,表示操作总数;\u003c/p\u003e\u003cp\u003e从第四行开始每行描述一个操作,输入的操作有以下三种形式: \u003c/p\u003e\u003cul\u003e \u003cli\u003e 操作 $$$1$$$:\"1 t g c\",表示把所有满足 $$$t\\le i\\le g$$$ 的 $$$a_i$$$ 改为 $$$a_i\\times c$$$; \u003c/li\u003e\u003cli\u003e 操作 $$$2$$$:\"2 t g c\",表示把所有满足 $$$t\\le i\\le g$$$ 的 $$$a_i$$$ 改为 $$$a_i+c$$$; \u003c/li\u003e\u003cli\u003e 操作 $$$3$$$:\"3 t g\",询问所有满足 $$$t\\le i\\le g$$$ 的 $$$a_i$$$ 的和模 $$$P$$$ 的值。 \u003c/li\u003e\u003c/ul\u003e 同一行相邻两数之间用一个空格隔开,每行开头和末尾没有多余空格。"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e对每个操作 $$$3$$$,按照它在输入中出现的顺序,依次输出一行一个整数表示询问结果。\u003c/p\u003e"}},{"title":"Examples","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\u003e7 43\n1 2 3 4 5 6 7\n5\n1 2 5 5\n3 2 4\n2 3 7 9\n3 1 3\n3 4 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n35\n8\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003e对于全部测试数据,$$$1\\le t\\le g\\le n,0\\le c,a_i\\le 10^9,1\\le P\\le 10^9$$$。\u003c/p\u003e\u003cp\u003e样例说明:\u003c/p\u003e\u003cp\u003e初始时数列为 $$$\\{1,2,3,4,5,6,7\\}$$$;\u003c/p\u003e\u003cp\u003e经过第 $$$1$$$ 次操作后,数列为 $$$\\{1,10,15,20,25,6,7\\}$$$;\u003c/p\u003e\u003cp\u003e对第 $$$2$$$ 次操作,和为 $$$10+15+20\u003d45$$$,模 $$$43$$$ 的结果是 $$$2$$$;\u003c/p\u003e\u003cp\u003e经过第 $$$3$$$ 次操作后,数列为 $$$\\{1,10,24,29,34,15,16\\}$$$;\u003c/p\u003e\u003cp\u003e对第 $$$4$$$ 次操作,和为 $$$1+10+24\u003d35$$$,模 $$$43$$$ 的结果是 $$$35$$$;\u003c/p\u003e\u003cp\u003e对第 $$$5$$$ 次操作,和为 $$$29+34+15+16\u003d94$$$,模 $$$43$$$ 的结果是 $$$8$$$。\u003c/p\u003e"}}]}