Description

Format

Input

第一行有三个整数N，M，p，分别代表序列的长度、平方操作与询问操作的总次数以及在平方操作中所要模的数。

接下来一行N个数代表一开始的序列{X1,X2,...,XN}。

接下来M行，每行三个整数op,l,r。其中op代表本次操作的类型。若op=0，代表这是一次平方操作，平方的区间为[l,r]；如果op=1，代表这是一次询问操作，询问的区间为[l,r]。

Output

对于每次的询问操作，输出一行代表这段区间内数的总和。注意：答案没有对任何数取模。

Samples

3 3 11
1 2 3
1 1 3
0 1 3
1 1 3

6
14

Limitation

对于100%的数据，∀i,Xi∈[0,p),l,r∈[1,n]

N，M，p的范围如下：

编号** ** N** ** M** ** p

1** ** 1000** ** 1000** ** 233

2** ** 1000** ** 1000** ** 2332

3** ** 100000** ** 100000** ** 5

4** ** 100000** ** 100000** ** 8192

5** ** 100000** ** 100000** ** 23

6** ** 100000** ** 100000** ** 45

7** ** 100000** ** 100000** ** 37

8** ** 55000** ** 55000** ** 4185

9** ** 55000** ** 55000** ** 5850

10** ** 55000** ** 55000** ** 2975

11** ** 55000** ** 55000** ** 2542

12** ** 55000** ** 55000** ** 2015

13** ** 60000** ** 60000** ** 2003

14** ** 65000** ** 65000** ** 2010

15** ** 70000** ** 70000** ** 4593

16** ** 75000** ** 75000** ** 4562

17** ** 80000** ** 80000** ** 1034

18** ** 85000** ** 85000** ** 5831

19** ** 90000** ** 90000** ** 9905

20** ** 100000** ** 100000** ** 9977