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