{"trustable":false,"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e♔♕♖♗♘♙♚♛♜♝♞♟\u003c/p\u003e\n\n\u003cdiv class\u003d\"epigraph\"\u003e\u003cdiv class\u003d\"epigraph-text\"\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003e\u003cp\u003e— Willem...\u003c/p\u003e\u003cp\u003e— 怎么了?\u003c/p\u003e\u003cp\u003e— 看起来Seniorious出了点问题...\u003c/p\u003e\u003cp\u003e— 我去看看...\u003c/p\u003e\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003ccenter\u003e\u003cp\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/1bdd77a0463fe7a36efc5d95fc20c359?v\u003d1714228108\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/p\u003e\u003c/center\u003e\u003cp\u003eSeniorious是通过特殊符咒按特定顺序连接而成。\u003c/p\u003e\u003cp\u003e500多年后,钟琴现在状况不佳,所以Willem决定彻底检查它。\u003c/p\u003e\u003cp\u003eSeniorious有\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e个符咒。Willem将它们排成一行,其中第\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e个是整数\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e。\u003c/p\u003e\u003cp\u003e为了维护它,Willem需要执行\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e次操作。\u003c/p\u003e\u003cp\u003e有四种类型的操作:\u003c/p\u003e\u003cul\u003e\u003cli\u003e\u003cspan class\u003d\"tex-span\"\u003e1 \u003ci\u003el\u003c/i\u003e \u003ci\u003er\u003c/i\u003e \u003ci\u003ex\u003c/i\u003e\u003c/span\u003e: 对于每个\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e,使得\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\u003c/i\u003e ≤ \u003ci\u003ei\u003c/i\u003e ≤ \u003ci\u003er\u003c/i\u003e\u003c/span\u003e,将\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e + \u003ci\u003ex\u003c/i\u003e\u003c/span\u003e赋给\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e。\u003c/li\u003e\u003cli\u003e\u003cspan class\u003d\"tex-span\"\u003e2 \u003ci\u003el\u003c/i\u003e \u003ci\u003er\u003c/i\u003e \u003ci\u003ex\u003c/i\u003e\u003c/span\u003e: 对于每个\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e,使得\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\u003c/i\u003e ≤ \u003ci\u003ei\u003c/i\u003e ≤ \u003ci\u003er\u003c/i\u003e\u003c/span\u003e,将\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e赋给\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e。\u003c/li\u003e\u003cli\u003e\u003cspan class\u003d\"tex-span\"\u003e3 \u003ci\u003el\u003c/i\u003e \u003ci\u003er\u003c/i\u003e \u003ci\u003ex\u003c/i\u003e\u003c/span\u003e: 输出索引范围\u003cspan class\u003d\"tex-span\"\u003e[\u003ci\u003el\u003c/i\u003e, \u003ci\u003er\u003c/i\u003e]\u003c/span\u003e内第\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e小的数,即如果取出所有满足\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\u003c/i\u003e ≤ \u003ci\u003ei\u003c/i\u003e ≤ \u003ci\u003er\u003c/i\u003e\u003c/span\u003e的元素并排序为非递减整数数组,则在第\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e个位置的元素。保证\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ex\u003c/i\u003e ≤ \u003ci\u003er\u003c/i\u003e - \u003ci\u003el\u003c/i\u003e + 1\u003c/span\u003e。\u003c/li\u003e\u003cli\u003e\u003cspan class\u003d\"tex-span\"\u003e4 \u003ci\u003el\u003c/i\u003e \u003ci\u003er\u003c/i\u003e \u003ci\u003ex\u003c/i\u003e \u003ci\u003ey\u003c/i\u003e\u003c/span\u003e: 输出\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\u003c/i\u003e ≤ \u003ci\u003ei\u003c/i\u003e ≤ \u003ci\u003er\u003c/i\u003e\u003c/span\u003e的\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e次幂的和,使得\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e,取模\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/span\u003e,即\u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/2afc28ae0642f3a072a9f37dfb25ee36?v\u003d1714228108\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e。\u003c/li\u003e\u003c/ul\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e仅一行包含四个整数\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e, \u003ci\u003eseed\u003c/i\u003e, \u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003emax\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e(\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e, 0 ≤ \u003ci\u003eseed\u003c/i\u003e \u0026lt; 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7, 1 ≤ \u003ci\u003evmax\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e)。\u003c/p\u003e\u003cp\u003e初始值和操作是使用以下伪代码生成的:\u003c/p\u003e\u003cpre class\u003d\"verbatim\"\u003e\u003cbr\u003edef rnd():\u003cbr\u003e\u003cbr\u003e ret \u003d seed\u003cbr\u003e seed \u003d (seed * 7 + 13) mod 1000000007\u003cbr\u003e return ret\u003cbr\u003e\u003cbr\u003efor i \u003d 1 to n:\u003cbr\u003e\u003cbr\u003e a[i] \u003d (rnd() mod vmax) + 1\u003cbr\u003e\u003cbr\u003efor i \u003d 1 to m:\u003cbr\u003e\u003cbr\u003e op \u003d (rnd() mod 4) + 1\u003cbr\u003e l \u003d (rnd() mod n) + 1\u003cbr\u003e r \u003d (rnd() mod n) + 1\u003cbr\u003e\u003cbr\u003e if (l \u0026gt; r): \u003cbr\u003e swap(l, r)\u003cbr\u003e\u003cbr\u003e if (op \u003d\u003d 3):\u003cbr\u003e x \u003d (rnd() mod (r - l + 1)) + 1\u003cbr\u003e else:\u003cbr\u003e x \u003d (rnd() mod vmax) + 1\u003cbr\u003e\u003cbr\u003e if (op \u003d\u003d 4):\u003cbr\u003e y \u003d (rnd() mod vmax) + 1\u003cbr\u003e\u003cbr\u003e\u003c/pre\u003e\u003cp\u003e这里\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eop\u003c/i\u003e\u003c/span\u003e是传说中提到的操作类型。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e对于类型为\u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e或\u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e的每个操作,输出包含答案的一行。\u003c/p\u003e"}},{"title":"示例","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\u003e10 10 7 9\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n1\n0\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","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\u003e10 10 9 9\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n1\n3\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个示例中,初始数组为\u003cspan class\u003d\"tex-span\"\u003e{8, 9, 7, 2, 3, 1, 5, 6, 4, 8}\u003c/span\u003e。\u003c/p\u003e\u003cp\u003e操作为:\u003c/p\u003e\u003cul\u003e\u003cli\u003e\u003cspan class\u003d\"tex-span\"\u003e2 6 7 9\u003c/span\u003e\u003c/li\u003e\u003cli\u003e\u003cspan class\u003d\"tex-span\"\u003e1 3 10 8\u003c/span\u003e\u003c/li\u003e\u003cli\u003e\u003cspan class\u003d\"tex-span\"\u003e4 4 6 2 4\u003c/span\u003e\u003c/li\u003e\u003cli\u003e\u003cspan class\u003d\"tex-span\"\u003e1 4 5 8\u003c/span\u003e\u003c/li\u003e\u003cli\u003e\u003cspan class\u003d\"tex-span\"\u003e2 1 7 1\u003c/span\u003e\u003c/li\u003e\u003cli\u003e\u003cspan class\u003d\"tex-span\"\u003e4 7 9 4 4\u003c/span\u003e\u003c/li\u003e\u003cli\u003e\u003cspan class\u003d\"tex-span\"\u003e1 2 7 9\u003c/span\u003e\u003c/li\u003e\u003cli\u003e\u003cspan class\u003d\"tex-span\"\u003e4 5 8 1 1\u003c/span\u003e\u003c/li\u003e\u003cli\u003e\u003cspan class\u003d\"tex-span\"\u003e2 5 7 5\u003c/span\u003e\u003c/li\u003e\u003cli\u003e\u003cspan class\u003d\"tex-span\"\u003e4 3 10 8 5\u003c/span\u003e\u003c/li\u003e\u003c/ul\u003e"}}]}