U203393 小 M 的变换

## 此题数据已经完成重造。请大家重新提交。 小 M 喜欢奇怪的变换，所以他就把变换和序列操作结合起来出了一道题。

小 M 有一个正整数 $p$。对于一个整数 $n$，定义对 $n$ 进行一次 $\text{fib}$ 变换为 $n\leftarrow \text{fib}_n\bmod p$，其中 $\text{fib}_n$ 表示斐波那契数列的第 $n$ 项（本题约定 $\text{fib}_0=0,\text{fib}_1=1$）。 现在小 M 对 $\text{fib}$ 变换的性质很感兴趣。因此他会给你一个长度为 $n$ 的序列 $a$，有 $m$ 次操作，可能为以下两种： `1 l r k`：表示将区间 $[l,r]$ 之内的每一个数进行 $k$ 次 $\text{fib}$ 变换。形式化的说，定义函数 $f(n)=\text{fib}_n\bmod p$，则你需要 $\forall i\in[l,r],a_i\leftarrow f^{(k)}(a_i)=\begin{matrix}\underbrace{f(\cdots f(f(f(a_i))))}\\k次\end{matrix}$。 `2 l r`：表示将区间 $[l,r]$ 翻转。 你需要输出 $m$ 次操作后得到的序列。 **请注意，$k$ 的范围会达到 $\texttt{long long}$ 级别。**

第一行共三个正整数，依次表示 $n,m,p$。 接下来一行，共 $n$ 个整数，其中第 $i$ 个数表示 $a_i$。 接下来 $m$ 行，每行可能是 `1 l r k` 或 `2 l r` 中的一种，表示一次操作。

共一行，为 $n$ 个整数，表示 $m$ 次操作后得到的序列。

**【样例1解释】** 初始序列 $a$ 为 $\{1,2,3,4,5\}$。 第一次操作，将区间 $[2,4]$ 中的数进行一次 $\text{fib}$ 变换。因为 $\text{fib}_2=1,\text{fib}_3=2,\text{fib}_4=3$，操作后的序列为 $\{1,1,2,3,5\}$。 第二次操作，将区间 $[1,4]$ 翻转，操作后的序列为 $\{3,2,1,1,5\}$。 第三次操作，将区间 $[2,5]$ 翻转，操作后的序列为 $\{3,5,1,1,2\}$。 第四次操作，将区间 $[1,5]$ 的数进行两次 $\text{fib}$ 变换，第一次变换后得到 $\{2,5,1,1,1\}$，第二次变换后得到 $\{1,5,1,1,1\}$。 第五次操作，将区间 $[2,3]$ 翻转，操作后的序列为 $\{1,1,5,1,1\}$。 最终输出的结果为 $\text{1 1 5 1 1}$。 **【样例2解释】** 可以发现，$\text{fib}_{1509505}\bmod 3000000=1509505$，所以不论变换多少次其值都不变。 **【数据规模与约定】** **本题采用捆绑测试。** |子任务编号|$n,m$|$p$|特殊限制|时间限制|分值| | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | |$\text{Subtask 1}$|$1\leqslant n,m\leqslant 5\times10^5$|$p=1919810$|条件 $\text{A}$|$\text{2s}$|$15$| |$\text{Subtask 2}$|$1\leqslant n,m\leqslant 5\times10^3$|$p=114514$|无|$\text{3s}$|$15$| |$\text{Subtask 3}$|$1\leqslant n,m\leqslant5\times10^5$|$p=114514$|无|$\text{3s}$|$25$| |$\text{Subtask 4}$|$1\leqslant n,m\leqslant 2.5\times10^5$|$2\leqslant p\leqslant2\times10^6$|无|$\text{4s}$|$20$| |$\text{Subtask 5}$|$1\leqslant n,m\leqslant5\times10^5$|$2\leqslant p\leqslant5\times10^6$|无|$\text{4s}$|$25$| 条件 $\text{A}$：不存在操作 $1$。 对于 $100\%$ 的数据，满足 $1\leqslant n,m\leqslant 5\times10^5,2\leqslant p\leqslant 5\times10^6,0\leqslant a_i