CF896C Willem, Chtholly and Seniorious

> ——威廉…… > > ——怎么了？ > > ——好像瑟尼欧里斯出问题了…… > > ——我去看看……  瑟尼欧里斯是通过特定顺序连接特殊护符制成的。 经过了 500 多年，这个圣剑现在状况不太好，所以威廉决定彻底检查它。 瑟尼欧里斯有 $n$ 片护符。威廉将它们排成一行，第 $i$ 片护符是一个整数 $a _ i$。 为了维护它，威廉需要执行 $m$ 次操作。 有四种操作类型： - $1\ l\ r\ x$ ：对于 $i$ 满足 $l \le i \le r$，将 $a _ i + x$ 赋值给 $a _ i$。 - $2\ l\ r\ x$ ：对于 $i$ 满足 $l \le i \le r$，将 $x$ 赋值给 $a _ i$。 - $3\ l\ r\ x$ ：输出范围 $[l, r]$ 中第 $x$ 小的数字，即在所有满足 $l \le i \le r$ 的 $a _ i$ 排序后第 $x$ 小的数字。保证 $1 \le x \le r - l + 1$。 - $4\ l\ r\ x\ y$ ：输出范围 $[l, r]$ 中所有 $a _ i$ 的 $x$ 次幂之和模 $y$，即 $\left( \sum _ {i = 1} ^ r {a _ i} ^ x \right) \bmod y$。

第一行包含四个整数 $n, m, seed, v _ {max}$（$1 \le n, m \le 10 ^ 5$，$0 \le 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 ``` 这里的 $op$ 是题目中提到的操作类型。

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

对于样例 1，初始数组为 $\{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 $