题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$，要求支持以下两种操作：

1. 0 l r：对于所有 $i\in[l,r]$，执行

   $$a_i\leftarrow a_i^2\bmod p.$$

2. 1 l r：询问

   $$\sum_{i=l}^{r}a_i.$$

输入格式

第一行包含三个整数 $n,m,p$，分别表示序列长度、操作总数以及平方操作所使用的模数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示初始序列。

接下来 $m$ 行，每行包含三个整数 $op,l,r$：

• 当 $op=0$ 时，表示对区间 $[l,r]$ 执行平方取模操作；
• 当 $op=1$ 时，表示询问区间 $[l,r]$ 的元素之和。

输出格式

对于每次询问操作，输出一行一个整数，表示对应区间内所有元素的总和。

注意：询问答案不对任何数取模。

样例 1

样例输入 1

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

样例输出 1

6
14

数据范围

对于全部数据：

各测试点的 $n,m,p$ 如下：