G. Shenchuan想考一道数学题

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

Shenchuan希望以维护一个长度为 的数组,这个数组的下标为从 的正整数。

一共有 个操作,可以分为两种:

  • 0 l r 表示将第 个到第 个数( )中的每一个数 替换为 ,即 次方,其中 是输入的一个常数,也就是执行赋值

  • 1 l r 求第 个到第 个数的和,也就是输出:

因为这个结果可能会很大,所以你只需要输出结果 的值即可。

输入格式

第一行有四个整数 ,所有整数含义见问题描述。
接下来一行 个整数,表示 数组的初始值。
接下来 行,每行三个整数,其中第一个整数表示了操作的类型。

  • 如果是 的话,表示这是一个修改操作,操作的参数为
  • 如果是 的话,表示这是一个询问操作,操作的参数为

输出格式

对于每个询问操作,输出一行,包括一个整数表示答案 的值。

样例

样例输入 #1

4 4 7 2
1 2 3 4
0 1 4
1 2 4
0 1 4
1 1 3

样例输出 #1

0
3

样例输入 #2

1 40 19910626 2
0
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1

样例输出 #2

1
2
4
16
65536
11418102
18325590
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558

数据范围与提示