← 返回题目列表

Codeforces · 896/C

C. 威廉、Chtholly 和 Seniorious

中文机器翻译题面 查看原题

Seniorious是通过按特定顺序连接特殊护身符而制成的。

500 多年过去了,钟琴现在状况不佳,因此威廉决定彻底检查它。

Seniorious有n张护身符。 Willem 将它们排成一行,其中第 i 个是整数 ai。

为了维持它,Willem 需要执行 m 次操作。

有四种类型的操作:

- 1 l r x:对于每个 i,使得 l ≤ i ≤ r,将 ai + x 分配给 ai。
- 2 l r x:对于每个 i,使得 l ≤ i ≤ r,将 x 分配给 ai。
- 3 l r x:打印索引范围 [l, r] 中第 x 个最小的数字,即如果将满足 l ≤ i ≤ r 的所有元素 ai 都取出并排序到非递减整数数组中,则打印第 x 个位置的元素。保证1 ≤ x ≤ r - l + 1。
- 4 l r x y:打印 ai 的 x 次方之和,使得 l ≤ i ≤ r,以 y 为模,即 $$(\sum_{i=1}^{r}a_i^x) \bmod y$$。

输入

唯一一行包含四个整数 n、m、seed、vmax (1 ≤ n、m ≤ 105、0 ≤ Seed < 109 + 7、1 ≤ vmax ≤ 109)。

初始值和操作是使用以下伪代码生成的:

这里的op是图例中提到的操作的类型。

输出

对于类型 3 或 4 的每个操作,输出包含答案的行。

示例

输入 #1

10 10 7 9

输出 #1

2
1
0
3

输入 #2

10 10 9 9

输出 #2

1
1
3
3

注意

在第一个示例中,初始数组为 {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