A11394 | Willem, Chtholly and Seniorious

— Willem...

— What's the matter?

— It seems that there's something wrong with Seniorious...

— I'll have a look...






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. .

The only line contains four integers $n,m,seed,v_{max}$ ( $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 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.

For each operation of types $3$ or $4$ , output a line containing the answer.