Background

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.

Problem Description

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.

Input Format

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 Format

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

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

1 4 52 44 6 4

Hint

Constraints

This problem uses bundled testdata.

Subtask	$\bm{n,m\leqslant}$	Score	Special property
$1$	$10^3$	$10$	None
$2$	$10^5$		$p \leqslant 2$
$3$		$20$	$p \leqslant 3$
$4$		$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