{"problem":{"name":"C. 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":"CF896C"},"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":"— Willem...\n\n— 怎么了？\n\n— Seniorious 似乎出了点问题...\n\n— 我去看看...\n\nSeniorious 是由按特定顺序连接的特殊符文组成的。\n\n经过500多年，风铃现在状况不佳，因此 Willem 决定彻底检查它。\n\nSeniorious 有 #cf_span[n] 个符文。Willem 将它们排成一行，第 #cf_span[i] 个符文是一个整数 #cf_span[ai]。\n\n为了维护它，Willem 需要执行 #cf_span[m] 次操作。\n\n共有四种操作类型：\n\n唯一的一行包含四个整数 #cf_span[n, m, seed, vmax] (#cf_span[1 ≤ n, m ≤ 105, 0 ≤ seed < 109 + 7, 1 ≤ vmax ≤ 109])。\n\n初始值和操作使用以下伪代码生成：\n\n这里 #cf_span[op] 是传说中提到的操作类型。\n\n对于类型为 #cf_span[3] 或 #cf_span[4] 的每次操作，请输出一行包含答案。\n\n## Input\n\n唯一的一行包含四个整数 #cf_span[n, m, seed, vmax] (#cf_span[1 ≤ n, m ≤ 105, 0 ≤ seed < 109 + 7, 1 ≤ vmax ≤ 109])。初始值和操作使用以下伪代码生成：\n\ndef rnd():\n    ret = seed\n    seed = (seed * 7 + 13) mod 1000000007\n    return ret\n\nfor i = 1 to n:\n    a[i] = (rnd() mod vmax) + 1\n\nfor i = 1 to m:\n    op = (rnd() mod 4) + 1\n    l = (rnd() mod n) + 1\n    r = (rnd() mod n) + 1\n    if (l > r):\n          swap(l, r)\n    if (op == 3):\n        x = (rnd() mod (r - l + 1)) + 1\n    else:\n        x = (rnd() mod vmax) + 1\n    if (op == 4):\n        y = (rnd() mod vmax) + 1\n\n这里 #cf_span[op] 是传说中提到的操作类型。\n\n## Output\n\n对于类型为 #cf_span[3] 或 #cf_span[4] 的每次操作，请输出一行包含答案。\n\n[samples]\n\n## Note\n\n在第一个例子中，初始数组是 #cf_span[{8, 9, 7, 2, 3, 1, 5, 6, 4, 8}]。操作如下：\n\n#cf_span[2 6 7 9]\n#cf_span[1 3 10 8]\n#cf_span[4 4 6 2 4]\n#cf_span[1 4 5 8]\n#cf_span[2 1 7 1]\n#cf_span[4 7 9 4 4]\n#cf_span[1 2 7 9]\n#cf_span[4 5 8 1 1]\n#cf_span[2 5 7 5]\n#cf_span[4 3 10 8 5]","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 a deterministic pseudo-random process using `seed` and `vmax`.  \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 the same pseudo-random process.\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} $  \n5. For each operation $ o_i $:  \n   - If $ o_i = 1 $: $ l, r, x $ satisfy $ 1 \\le l \\le r \\le n $, $ 1 \\le x \\le v_{\\max} $; update $ a_j \\leftarrow \\min(a_j, x) $ for $ j \\in [l, r] $  \n   - If $ o_i = 2 $: $ l, r, x $ satisfy $ 1 \\le l \\le r \\le n $, $ 1 \\le x \\le v_{\\max} $; update $ a_j \\leftarrow a_j + x $ for $ j \\in [l, r] $  \n   - If $ o_i = 3 $: $ l, r, x $ satisfy $ 1 \\le l \\le r \\le n $, $ 1 \\le x \\le v_{\\max} $; compute $ \\sum_{j=l}^{r} [a_j = x] $  \n   - If $ o_i = 4 $: $ l, r, k $ satisfy $ 1 \\le l \\le r \\le n $, $ 1 \\le k \\le r - l + 1 $; compute the $ k $-th smallest value in $ \\{a_l, a_{l+1}, \\dots, a_r\\} $\n\n**Objective**  \nFor each operation $ o_i \\in \\{3, 4\\} $, output the result of the query.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF896C","tags":["data structures","probabilities"],"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"}}