P8878 『STA - R1』Delicious Wisdom Fruit.

In ancient times, $-(2077^{-1}\ \ (mod=2035))$ years ago, $\mathfrak{Morlin}$ planted a very precious $\colorbox{black}{\textcolor{red}{\textbf{Wis♂dom♂Tree♂}}}$, which was seen by $\mathfrak{char\_phi}$. After $114810$ years, the tree bore $\colorbox{black}{\textcolor{blue}{\textbf{Wis♂dom♂Fruit♂}}}$. After another $1919514$ years, the fruit ripened, and $\mathfrak{char\_phi}$ really wanted to eat it. $\mathfrak{char\_phi}$ wanted to eat the fruit very much, but ~~all-knowing~~ $\mathfrak{Morlin}$ had already known that $\mathfrak{char\_phi}$ wanted his fruit, so he put each fruit into a password box. Now, $\mathfrak{char\_phi}$ has entrusted you with the important task of stealing the fruit.

**Formal statement** Maintain a sequence $\{a_n\}$. In each operation, you are given five non-negative integers $l, r, k, p, c$. For all $i\in[l,r]$, update $a_i\gets (f_{a_i}^k+c)\bmod p$. Here $f$ is the Fibonacci sequence, defined as: $$f_n=\begin{cases}n&n\leqslant 1\\f_{n-1}+f_{n-2}&n>1\end{cases}$$ *** **Original statement** ~~All-knowing~~ $\mathfrak{Morlin}$ had long known that $\mathfrak{char\_phi}$ was very smart, so he would change the password from time to time. Each password box has a number on it, forming the sequence $\{a_n\}$. There are $m$ operations on the password. In each operation, five integers $l, r, k, p, c$ are given, meaning that for all $i$ satisfying $l \leqslant i \leqslant r$, change $a_i$ into $(f_{a_i}^k+c) \bmod p$ ($f_i$ denotes the $i$-th term of the Fibonacci sequence; it is guaranteed that $l \leqslant r$). $\mathfrak{char\_phi}$ made a recorder to record $\mathfrak{Morlin}$'s operations. Now, he gives you the recorder, hoping that after $\mathfrak{Morlin}$ finishes all operations, you can figure out the passwords of all the boxes.

The first line contains two integers $n, m$, representing the number of fruits and the number of operations. The second line contains $n$ integers as the sequence $a$, representing the number on each password box. The next $m$ lines describe $\mathfrak{Morlin}$'s operations $l, r, k, p, c$.

Output one line containing the passwords of all boxes, separated by spaces.

**Constraints** **This problem uses bundled testdata.** | Subtask | $\bm{n,m\leqslant}$ | Score | Special property | | :--: | :--: | :--: | :--: | | $1$ | $10^3$ | $10$ | None | | $2$ | $10^5$ | $10$ | $p \leqslant 2$ | | $3$ | $10^5$ | $20$ | $p \leqslant 3$ | | $4$ | $10^5$ | $60$ | None | For $100\%$ of the testdata, $1 \leqslant n, m \leqslant 10^5$, $1 \leqslant a_i, p, k \leqslant 100$, $0 \leqslant c \leqslant 10^9$. Translated by ChatGPT 5