题目描述

Seniorious 由 $n$ 片特殊的护符按照特定顺序连接而成。经过 500 多年的岁月，这架钟琴已经状况不佳，Willem 决定彻底检查它。

Willem 将 $n$ 片护符排成一行，第 $i$ 片上的数字为 $a_i$。为了维护它，Willem 需要执行 $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$ 小的数字。保证 $1 \le x \le r - l + 1$。
• 4 l r x y：输出 $\displaystyle \left( \sum_{i=l}^{r} a_i^x \right) \bmod y$。

初始数组和操作由以下伪代码生成：

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

输入格式

一行四个整数 $n, m, seed, vmax$（$1 \le n, m \le 10^5$，$0 \le \mathit{seed} < 10^9 + 7$，$1 \le \mathit{vmax} \le 10^9$）。

输出格式

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

样例 1

10 10 7 9

2
1
0
3

样例 2

10 10 9 9

1
1
3
3