{"problem":{"name":"E. Willem, Chtholly and Seniorious","description":{"content":"%epigraph%%epigraphtext%_— Willem... — What's the matter? — It seems that there's something wrong with Seniorious... — I'll have a look... _%endepigraphtext%%endepigraph%<center>![image](https://e","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF897E"},"statements":[{"statement_type":"Markdown","content":"%epigraph%%epigraphtext%_— Willem...\n\n— What's the matter?\n\n— It seems that there's something wrong with Seniorious...\n\n— I'll have a look...\n\n_%endepigraphtext%%endepigraph%<center>![image](https://espresso.codeforces.com/f0c1a165961ac7b1495e448614d25cba032c5952.png)\n\n</center>Seniorious is made by linking special talismans in particular order.\n\nAfter over 500 years, the carillon is now in bad condition, so Willem decides to examine it thoroughly.\n\nSeniorious has _n_ pieces of talisman. Willem puts them in a line, the _i_\\-th of which is an integer _a__i_.\n\nIn order to maintain it, Willem needs to perform _m_ operations.\n\nThere are four types of operations:\n\n*   1 _l_ _r_ _x_: For each _i_ such that _l_ ≤ _i_ ≤ _r_, assign _a__i_ + _x_ to _a__i_.\n*   2 _l_ _r_ _x_: For each _i_ such that _l_ ≤ _i_ ≤ _r_, assign _x_ to _a__i_.\n*   3 _l_ _r_ _x_: Print the _x_\\-th smallest number in the index range \\[_l_, _r_\\], i.e. the element at the _x_\\-th position if all the elements _a__i_ such that _l_ ≤ _i_ ≤ _r_ are taken and sorted into an array of non-decreasing integers. It's guaranteed that 1 ≤ _x_ ≤ _r_ - _l_ + 1.\n*   4 _l_ _r_ _x_ _y_: Print the sum of the _x_\\-th power of _a__i_ such that _l_ ≤ _i_ ≤ _r_, modulo _y_, i.e. .\n\n## Input\n\nThe only line contains four integers _n_, _m_, _seed_, _v__max_ (1 ≤ _n_, _m_ ≤ 105, 0 ≤ _seed_ < 109 + 7, 1 ≤ _vmax_ ≤ 109).\n\nThe initial values and operations are generated using following pseudo code:\n\ndef rnd():\n\n    ret = seed\n    seed = (seed * 7 + 13) mod 1000000007\n    return ret\n\nfor i = 1 to n:\n\n    a\\[i\\] = (rnd() mod vmax) + 1\n\nfor i = 1 to m:\n\n    op = (rnd() mod 4) + 1\n    l = (rnd() mod n) + 1\n    r = (rnd() mod n) + 1\n\n    if (l > r): \n         swap(l, r)\n\n    if (op == 3):\n        x = (rnd() mod (r - l + 1)) + 1\n    else:\n        x = (rnd() mod vmax) + 1\n\n    if (op == 4):\n        y = (rnd() mod vmax) + 1\n\nHere _op_ is the type of the operation mentioned in the legend.\n\n## Output\n\nFor each operation of types 3 or 4, output a line containing the answer.\n\n[samples]\n\n## Note\n\nIn the first example, the initial array is {8, 9, 7, 2, 3, 1, 5, 6, 4, 8}.\n\nThe operations are:\n\n*   2 6 7 9\n*   1 3 10 8\n*   4 4 6 2 4\n*   1 4 5 8\n*   2 1 7 1\n*   4 7 9 4 4\n*   1 2 7 9\n*   4 5 8 1 1\n*   2 5 7 5\n*   4 3 10 8 5","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"iden\":\"statement\",\"content\":\"— Willem...\\n\\n— What's the matter?\\n\\n— It seems that there's something wrong with Seniorious...\\n\\n— I'll have a look...\\n\\n\\n\\nSeniorious is made by linking special talismans in particular order.\\n\\nAfter over 500 years, the carillon is now in bad condition, so Willem decides to examine it thoroughly.\\n\\nSeniorious has $n$ pieces of talisman. Willem puts them in a line, the $i$-th of which is an integer $a_i$.\\n\\nIn order to maintain it, Willem needs to perform $m$ operations.\\n\\nThere are four types of operations:\\n\\nThe only line contains four integers $n, m, seed, vmax$ ($1 ≤ n, m ≤ 10^5, 0 ≤ seed < 10^9 + 7, 1 ≤ vmax ≤ 10^9$).\\n\\nThe initial values and operations are generated using following pseudo code:\\n\\nHere $op$ is the type of the operation mentioned in the legend.\\n\\nFor each operation of types $3$ or $4$, output a line containing the answer.\\n\\nIn the first example, the initial array is $\\{8, 9, 7, 2, 3, 1, 5, 6, 4, 8\\}$.\\n\\nThe operations are:\\n\\n\"},{\"iden\":\"input\",\"content\":\"The only line contains four integers $n, m, seed, vmax$ ($1 ≤ n, m ≤ 10^5, 0 ≤ seed < 10^9 + 7, 1 ≤ vmax ≤ 10^9$).The initial values and operations are generated using following pseudo code:def rnd():    ret = seed    seed = (seed * 7 + 13) mod 1000000007    return retfor i = 1 to n:    a[i] = (rnd() mod vmax) + 1for i = 1 to m:    op = (rnd() mod 4) + 1    l = (rnd() mod n) + 1    r = (rnd() mod n) + 1    if (l > r):          swap(l, r)    if (op == 3):        x = (rnd() mod (r - l + 1)) + 1    else:        x = (rnd() mod vmax) + 1    if (op == 4):        y = (rnd() mod vmax) + 1Here $op$ is the type of the operation mentioned in the legend.\"},{\"iden\":\"output\",\"content\":\"For each operation of types $3$ or $4$, output a line containing the answer.\"},{\"iden\":\"examples\",\"content\":\"Input10 10 7 9Output2103Input10 10 9 9Output1133\"},{\"iden\":\"note\",\"content\":\"In the first example, the initial array is $\\{8, 9, 7, 2, 3, 1, 5, 6, 4, 8\\}$.\\nThe operations are:  $2\\ 6\\ 7\\ 9$  $1\\ 3\\ 10\\ 8$  $4\\ 4\\ 6\\ 2\\ 4$  $1\\ 4\\ 5\\ 8$  $2\\ 1\\ 7\\ 1$  $4\\ 7\\ 9\\ 4\\ 4$  $1\\ 2\\ 7\\ 9$  $4\\ 5\\ 8\\ 1\\ 1$  $2\\ 5\\ 7\\ 5$  $4\\ 3\\ 10\\ 8\\ 5$ \"}]\n\n{\"problem_iden\":\"CF897E\",\"statement_source\":\"Codeforces\",\"problem_source\":\"CF\",\"problem_statements\":[{\"iden\":\"statement\",\"content\":\"— Willem...\\n\\n— What's the matter?\\n\\n— It seems that there's something wrong with Seniorious...\\n\\n— I'll have a look...\\n\\n\\n\\nSeniorious is made by linking special talismans in particular order.\\n\\nAfter over 500 years, the carillon is now in bad condition, so Willem decides to examine it thoroughly.\\n\\nSeniorious has $n$ pieces of talisman. Willem puts them in a line, the $i$-th of which is an integer $a_i$.\\n\\nIn order to maintain it, Willem needs to perform $m$ operations.\\n\\nThere are four types of operations:\\n\\nThe only line contains four integers $n, m, seed, vmax$ ($1 ≤ n, m ≤ 10^5, 0 ≤ seed < 10^9 + 7, 1 ≤ vmax ≤ 10^9$).\\n\\nThe initial values and operations are generated using following pseudo code:\\n\\nHere $op$ is the type of the operation mentioned in the legend.\\n\\nFor each operation of types $3$ or $4$, output a line containing the answer.\\n\\nIn the first example, the initial array is $\\{8, 9, 7, 2, 3, 1, 5, 6, 4, 8\\}$.\\n\\nThe operations are:\\n\\n\"},{\"iden\":\"input\",\"content\":\"The only line contains four integers $n, m, seed, vmax$ ($1 ≤ n, m ≤ 10^5, 0 ≤ seed < 10^9 + 7, 1 ≤ vmax ≤ 10^9$).The initial values and operations are generated using following pseudo code:def rnd():    ret = seed    seed = (seed * 7 + 13) mod 1000000007    return retfor i = 1 to n:    a[i] = (rnd() mod vmax) + 1for i = 1 to m:    op = (rnd() mod 4) + 1    l = (rnd() mod n) + 1    r = (rnd() mod n) + 1    if (l > r):          swap(l, r)    if (op == 3):        x = (rnd() mod (r - l + 1)) + 1    else:        x = (rnd() mod vmax) + 1    if (op == 4):        y = (rnd() mod vmax) + 1Here $op$ is the type of the operation mentioned in the legend.\"},{\"iden\":\"output\",\"content\":\"For each operation of types $3$ or $4$, output a line containing the answer.\"},{\"iden\":\"examples\",\"content\":\"Input10 10 7 9Output2103Input10 10 9 9Output1133\"},{\"iden\":\"note\",\"content\":\"In the first example, the initial array is $\\{8, 9, 7, 2, 3, 1, 5, 6, 4, 8\\}$.\\nThe operations are:  $2\\ 6\\ 7\\ 9$  $1\\ 3\\ 10\\ 8$  $4\\ 4\\ 6\\ 2\\ 4$  $1\\ 4\\ 5\\ 8$  $2\\ 1\\ 7\\ 1$  $4\\ 7\\ 9\\ 4\\ 4$  $1\\ 2\\ 7\\ 9$  $4\\ 5\\ 8\\ 1\\ 1$  $2\\ 5\\ 7\\ 5$  $4\\ 3\\ 10\\ 8\\ 5$ \"}],\"time_limit\":2000,\"memory_limit\":262144}","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m, \\text{seed}, v_{\\max} \\in \\mathbb{Z} $ be given parameters.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the initial sequence of integers, generated via provided pseudo-code using $ \\text{seed} $ and $ v_{\\max} $.  \nLet $ \\mathcal{O} = (o_1, o_2, \\dots, o_m) $ be a sequence of $ m $ operations, each of type $ o_i \\in \\{1, 2, 3, 4\\} $, generated via pseudo-code.\n\n**Constraints**  \n1. $ 1 \\le n, m \\le 10^5 $  \n2. $ 0 \\le \\text{seed} < 10^9 + 7 $  \n3. $ 1 \\le v_{\\max} \\le 10^9 $  \n4. For all $ i \\in \\{1, \\dots, n\\} $: $ 1 \\le a_i \\le v_{\\max} $  \n\n**Operations**  \nFor each operation $ o_i $:  \n- **Type 1**: $ \\text{add}(l, r, v) $: $ a_j \\leftarrow a_j + v $ for all $ j \\in [l, r] $  \n- **Type 2**: $ \\text{assign}(l, r, v) $: $ a_j \\leftarrow v $ for all $ j \\in [l, r] $  \n- **Type 3**: $ \\text{query\\_sum}(l, r, x) $: output $ \\sum_{j=l}^{r} a_j^x \\mod (10^9 + 7) $  \n- **Type 4**: $ \\text{query\\_kth}(l, r, k) $: output the $ k $-th smallest value in $ \\{a_l, a_{l+1}, \\dots, a_r\\} $\n\n**Objective**  \nFor each operation of type 3 or 4, output the corresponding result.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF897E","tags":["data structures"],"sample_group":[["10 10 7 9","2\n1\n0\n3"],["10 10 9 9","1\n1\n3\n3"]],"created_at":"2026-03-03 11:00:39"}}