题目背景

在上古时代，$-(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$		$p \leqslant 2$
$3$		$20$	$p \leqslant 3$
$4$		$60$	无

对于 $100\%$ 的数据，$1 \leqslant n, m \leqslant 10^5$，$1 \leqslant a_i, p, k \leqslant 100$，$0 \leqslant c \leqslant 10^9$。