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

— 威廉……

— 怎么了？

— 看起来“塞尼奥里乌斯”出了些问题……

— 我去看看……

“塞尼奥里乌斯”是通过按特定顺序连接若干特殊符咒所构成的。

历经五百余年，这座编钟如今已严重老化，因此威廉决定对其进行全面检修。

“塞尼奥里乌斯”共有 $n$ 枚符咒。威廉将它们排成一行，其中第 $i$ 枚符咒对应一个整数 $a_i$。

为维护其正常运转，威廉需执行 $m$ 次操作。

操作共分为四类：

• 1 l r x：对每个满足 $l \le i \le r$ 的下标 $i$，执行赋值操作 $a_i \gets a_i + x$；
• 2 l r x：对每个满足 $l \le i \le r$ 的下标 $i$，执行赋值操作 $a_i \gets x$；
• 3 l r x：输出区间 $[l,\,r]$ 中第 $x$ 小的数，即：将所有满足 $l \le i \le r$ 的元素 $a_i$ 取出，按非递减顺序排序后，取其第 $x$ 个位置上的元素（下标从 1 开始计数）。数据保证 $1 \le x \le r - l + 1$；
• 4 l r x y：输出所有满足 $l \le i \le r$ 的 $a_i$ 的 $x$ 次幂之和对 $y$ 取模的结果，即：
  

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.

唯一一行包含四个整数 $n$、$m$、$\textit{seed}$、$v_{\max}$（满足 $1 \le n, m \le 10^5$，$0 \le \textit{seed} < 10^9 + 7$，$1 \le v_{\max} \le 10^9$）。

初始值及操作均通过以下伪代码生成：

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

其中 $\textit{op}$ 表示题面说明中所提及的操作类型。

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

对于每个类型为 3 或 4 的操作，输出一行包含答案的内容。

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

在第一个例子中，初始数组为 $\{8,\ 9,\ 7,\ 2,\ 3,\ 1,\ 5,\ 6,\ 4,\ 8\}$。

操作序列为：

• 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