『STA - R1』好吃的智慧果子

在上古时代，$-(2077^{-1}\ \ (mod=2035))$ 年，$\mathfrak{Morlin}$ 种下了一棵非常珍贵的$\colorbox{black}{\textcolor{red}{\textbf{智♂慧♂树♂}}}$，被 $\mathfrak{char\_phi}$ 看见了。 过了 $114810$ 年，树上结出了 $\colorbox{black}{\textcolor{blue}{\textbf{智♂慧♂果♂子♂}}}$。 又过了 $1919514$ 年，果子成熟了，$\mathfrak{char\_phi}$ 非常馋。 $\mathfrak{char\_phi}$ 十分想吃果子，但是~~神机妙算的~~ $\mathfrak{Morlin}$ 早就知道 $\mathfrak{char\_phi}$ 想要吃他的果子，所以把每个果子都装进了密码箱。 现在，$\mathfrak{char\_phi}$ 把偷果子这项重任托付给了你。

**形式化题面** 维护一个序列 $\{a_n\}$，每次操作给五个非负整数 $l, r, k, p, c$，对于所有 $i\in[l,r]$，将 $a_i\gets (f_{a_i}^k+c)\bmod p$。 其中 $f$ 是 Fibonacci 数列，定义为： $$f_n=\begin{cases}n&n\leqslant 1\\f_{n-1}+f_{n-2}&n>1\end{cases}$$ *** **原题面** ~~神机妙算的~~ $\mathfrak{Morlin}$ 早就知道 $\mathfrak{char\_phi}$ 很聪明，所以他会不定时改密码。 每个密码箱上有一个数字，组成了数列 $\{a_n\}$。 关于密码有 $m$ 次操作，每次操作给定五个整数 $l, r, k, p, c$，表示将满足 $l \leqslant i \leqslant r$ 将 $a_i$ 变成 $(f_{a_i}^k+c) \bmod p$（$f_i$ 代表斐波那契数列的第 $i$ 项；保证 $l \leqslant r$）。 $\mathfrak{char\_phi}$ 搞了一个记录器记录下了 $\mathfrak{Morlin}$ 的操作。现在，他把记录器给了你，希望你能在 $\mathfrak{Morlin}$ 操作完后搞出所有密码箱的密码。

第一行，两个整数 $n, m$，表示果子的数量和操作次数。 第二行，$n$ 个整数为数列 $a$，表示每个密码箱上的数字。 接下来 $m$ 行，表示 $\mathfrak{Morlin}$ 的操作 $l, r, k, p, c$。

一行，表示所有密码箱的密码，每个密码间使用空格隔开。

6 2
1 1 4 5 1 4
2 4 2 100 3
3 5 1 97 5

1 4 52 44 6 4

**【数据范围】** **本题采用捆绑测试。** | Subtask | $\bm{n,m\leqslant}$ | 分值 | 特殊性质 | | :--: | :--: | :--: | :--: | | $1$ | $10^3$ | $10$ | 无 | | $2$ | $10^5$ | $10$ | $p \leqslant 2$ | | $3$ | $10^5$ | $20$ | $p \leqslant 3$ | | $4$ | $10^5$ | $60$ | 无 | 对于 $100\%$ 的数据，$1 \leqslant n, m \leqslant 10^5$，$1 \leqslant a_i, p, k \leqslant 100$，$0 \leqslant c \leqslant 10^9$。