逆元数列

【题目背景】

这是一道数据结构题。

【题目描述】

给定质数 $p$ ，你需要维护一个长为 $n$ 的数列 $\{a_n\}$ ，有如下两种操作形式：

$1\ l\ r\ $，表示将 $a_l…a_r$ 的所有数变为其模 $p$ 的乘法逆元；

$2\ l\ r\ $，表示查询 $a_l…a_r$ 的和。

若整数 $b,p$ 互质，并且 $b|a$ （b能整除a），则存在一个整数 $x$ ，使得 $a/b≡a*x\ (mod\ p)$，我们称 $x$ 为 $b$ 模 $p$ 的乘法逆元（取模运算的乘法逆元）。

【输入格式】

第一行三个整数 $n,m,p$。

第二行 $n$ 个数，表示初始的 $\{a_n\}$。

接下来 $m$ 行，每行三个整数 $opt,l,r$ ,表示一次操作，含义如上。 $opt∈\{1,2\}\ ,\ 1≤l≤r≤n$。

【输出格式】

若干行，对于每一个操作$2$，输出查询的值。

【样例输入1】

4 2 5
1 2 3 4
1 1 3
2 1 4

【样例输出1】

10

【样例输入输出2】

输入输出样例2

【样例说明】

初始：     $\{1,2,3,4\}$

第一次操作后：$\{1,3,2,4\}$

【数据规模与约定】

对于 $20\%$ 数据，$1≤n,m≤10^2$；

对于 $40\%$ 数据，$1≤n,m≤10^3$；

对于 $100\%$ 数据，$1≤n,m≤10^5，p≤10^9+7\ ,\ 1≤a_i<p$;

【来源】

$rsr$