%epigraph%%epigraphtext%_— Willem...
— What's the matter?
— It seems that there's something wrong with Seniorious...
— I'll have a look...
_%endepigraphtext%%endepigraph%<center>
</center>Seniorious is made by linking special talismans in particular order.
After over 500 years, the carillon is now in bad condition, so Willem decides to examine it thoroughly.
Seniorious has _n_ pieces of talisman. Willem puts them in a line, the _i_\-th of which is an integer _a__i_.
In order to maintain it, Willem needs to perform _m_ operations.
There are four types of operations:
* 1 _l_ _r_ _x_: For each _i_ such that _l_ ≤ _i_ ≤ _r_, assign _a__i_ + _x_ to _a__i_.
* 2 _l_ _r_ _x_: For each _i_ such that _l_ ≤ _i_ ≤ _r_, assign _x_ to _a__i_.
* 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.
* 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. .
## Input
The only line contains four integers _n_, _m_, _seed_, _v__max_ (1 ≤ _n_, _m_ ≤ 105, 0 ≤ _seed_ < 109 + 7, 1 ≤ _vmax_ ≤ 109).
The initial values and operations are generated using following pseudo code:
def rnd():
ret = seed
seed = (seed * 7 + 13) mod 1000000007
return ret
for i = 1 to n:
a\[i\] = (rnd() mod vmax) + 1
for 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) + 1
Here _op_ is the type of the operation mentioned in the legend.
## Output
For each operation of types 3 or 4, output a line containing the answer.
[samples]
## Note
In the first example, the initial array is {8, 9, 7, 2, 3, 1, 5, 6, 4, 8}.
The 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
[{"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$ "}]
{"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}
**Definitions**
Let $ n, m, \text{seed}, v_{\max} \in \mathbb{Z} $ be given parameters.
Let $ 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} $.
Let $ \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.
**Constraints**
1. $ 1 \le n, m \le 10^5 $
2. $ 0 \le \text{seed} < 10^9 + 7 $
3. $ 1 \le v_{\max} \le 10^9 $
4. For all $ i \in \{1, \dots, n\} $: $ 1 \le a_i \le v_{\max} $
**Operations**
For each operation $ o_i $:
- **Type 1**: $ \text{add}(l, r, v) $: $ a_j \leftarrow a_j + v $ for all $ j \in [l, r] $
- **Type 2**: $ \text{assign}(l, r, v) $: $ a_j \leftarrow v $ for all $ j \in [l, r] $
- **Type 3**: $ \text{query\_sum}(l, r, x) $: output $ \sum_{j=l}^{r} a_j^x \mod (10^9 + 7) $
- **Type 4**: $ \text{query\_kth}(l, r, k) $: output the $ k $-th smallest value in $ \{a_l, a_{l+1}, \dots, a_r\} $
**Objective**
For each operation of type 3 or 4, output the corresponding result.