P4691 Nephren Ruq Insania

This problem is exactly the same as [P3934 [Ynoi2016]炸脖龙I](https://www.luogu.com.cn/problem/P3934), but for the consistency of the contest problems, the statement is shown and submissions are not allowed. A backup of the statement for [Ynoi2016]炸脖龙I: https://www.luogu.org/discuss/show/45962. Large sample download link: https://pan.baidu.com/s/1nuVpRS1 Password: sfxg. **Note: The output file of large sample 4 has been changed to https://pan.baidu.com/s/1bUWuZW.** Nephren-Ruq-Insania.  As an adult fairy soldier from the same Fairy Warehouse, she is not as talented as Chtholly, just an ordinary fairy. When sleeping, she wraps around William like a blanket to keep him warm. She is used to sticking to William. When talking with Elmeria in dreams, she calls herself like William’s pet.  This statement contains a lot of spoilers. It is recommended to finish watching this anime before doing the problem（

She is just a very ordinary golden fairy. During the rescue operation for the salvage team, they unfortunately encountered (almost all of) the Sixth Beasts. At this time, Chtholly is in a coma because she has come into contact with the main body of the Star God Elq. William also cannot leave Chtholly.  Silently guarding outside the room, she picked up the holy sword and walked toward the battlefield.  As a fairy girl whose talent is only average, it is hard for her to fight against the No. 6 Beasts that outnumber her by countless times. Before long, she started to run out of strength. Finally, facing the endless No. 6 Beasts, she could no longer hold them back…  At last, due to excessive stimulation of magical power, she was already on the verge of losing control… “William, saving others is the mission of us golden fairies.” “Besides, William has saved us before.” “So, there is no problem anymore.”  William wants to save Nephren, but he himself is also on the verge of collapse. Somehow he recalled a kind of magic he had learned before. At this last moment, it might be the only way. This magic operates on a sequence made up of spells. Each individual spell has its own mana value. William needs to repeatedly, according to his memory, add a number to the mana values on some interval, or compute the spell resonance on an interval. Spell resonance is computed as follows: For an interval $[l,r]$, query $ a[l]^{a[l+1]^{a[l+2]^{.....}}} \bmod \ p$, continuing until $ a[r] $. Please note that the modulus is different each time. Time is running out, and William is unable to compute such complex magic by himself. But this is the last hope. Whether Nephren can be saved depends on you. 

The first line contains two integers $n,m$, representing the sequence length and the number of operations. The next line contains $n$ integers $a_i$, representing the sequence. The next $m$ lines are one of the following two operations: - `1 l,r,x`, meaning add $x$ to the interval $[l,r]$. - `2 l,r,p`, meaning perform one spell resonance, with modulus $p$.

For each operation of type 2, output one line containing the answer.

Test point | Range of $n$ | Range of $m$ | Special constraints. -|-|-|- 1| $n = 5$ | $m = 5$ | $a_i \le 3$. 2| $n = 1000$ | $m = 1000$ | Query interval length is 1. 3| $n = 100000$ | $m = 100000$ | Query interval length is 1. 4| $n = 1000$ | $m = 1000$ | Query interval length is at most 2. 5| $n = 100000$ | $m = 100000$ | Query interval length is at most 2. 6| $n = 1000$ | $m = 1000$ | $a_i \le 2$. 7| $n = 1000$ | $m = 1000$ | $p = 2$. 8| $n = 100000$ | $m = 100000$ | $p = 2$, no modifications. 9| $n = 1000$ | $m = 1000$ | $p \le 100000$, no modifications. 10| $n = 500000$ | $m = 500000$ | None. For 100% of the data, $n , m \le 500000$, each number in the sequence is within $[1,2\cdot 10^9]$, $p \le 2 \cdot 10^7$, and each added number is within $[0,2\cdot 10^9]$.   Translated by ChatGPT 5