P3934 [Ynoi Easy Round 2016] Jabberwock I

It was supper time, and the slithy skunks Did bore through turf and gyre ’neath the gnomon’s mark; The Borogove parrot wheezed in fits, the lost green turtles Howled in their blind dark. “Beware the Jabberwock, my child! The jaws that bite, the claws that catch! Beware the Jubjub bird, and shun The frumious Bandersnatch!” He took his vorpal sword in hand: long time The manxome foe he sought— So rested he by the Tumtum tree, And stood awhile in thought. And, as in uffish thought he stood, The Jabberwock, with eyes of flame, Came whiffling through the tulgey wood, And burbled as it came! One, two! One, two! And through and through The vorpal blade went snicker-snack! He left it dead, and with its head He went galumphing back. “And hast thou slain the Jabberwock? Come to my arms, my beamish boy! O frabjous day! Callooh! Callay!” He chortled in his joy. It was supper time, and the slithy skunks Did bore through turf and gyre ’neath the gnomon’s mark; The Borogove parrot wheezed in fits, the lost green turtles Howled in their blind dark. — “The Poem of the Jabberwock.”  I shouted... but it was not human speech. Only, like a sugar cube that melts as it sinks in water... Losing the outline of myself... sinking all the way to the very bottom. The meridian that wants to climb up, Maintaining the continuum that I am myself... A dissolving, gradually scattered consciousness... I lost the hands used to struggle. I lost the arms used to struggle. Down, down, keep sinking, toward the bottom layer of consciousness. The self that sinks... A world that is gradually disappearing... I saw the world, a lost... world.  ```plain 回归天空的话我就可以成为 了 开什么玩笑，你才不是什么 ！ 吵死了！吵死了！我是 ！而且生来就是！ 就是因为这个家伙我才失去 的资格的！ 呜呜呜，由岐姐姐，由岐姐姐！ ...怎么会...由岐姐... 卓司！你这家伙！ 吵死了吵死了！像你这样的普通人懂些什么！ 由岐的血慢慢在冰凉的水泥地上扩散开来 抱在怀里的 在渐渐地流出来 本应成为 而出生 的我的被 妨碍了！ 不出生的话我就没法拯救是这个世界！ 所以预言者说能当世界回归天空的此处就是尽头 只要 回归天空的话！ 我有这么可怕吗？ 因为我是要对一切生物下达审判的存在！ 因为哥哥是凡人呢 凡人与天才 救世主 世界 救世主 回天之门 要死的是你！ 我不会死 不会死 诅咒你 要死的是羽咲 只要羽咲死了 间宫 皆 守 由 岐 间宫羽咲 可能性 和镜 终 终之空 空 ```  A baby was born. Whose? I don’t know. Although I don’t know... A baby was indeed born. Mm... that baby is crying... Waa, waa, crying... Hearing that crying, everyone smiled. Everyone was blessing the baby. The mother too... The father too... And the others too... For the baby’s birth... Blessing from the heart. The world was full of the blessing of life. But, it was not like that. There, I— I alone was afraid there. Very afraid... Why, you ask... Because that was placing a curse upon the world. That’s right... He was cursing that world, that newborn baby, Cursing his own birth. I— My whole body froze on the spot. Amid everyone’s smiles, Amid the blessings, All alone... I... I staggered... And approached that baby, Then tried to make that baby stop crying. I thought I had to do that. Why? I myself did not understand... That was— That was the one thing, For me, who has lived in misery since birth until today, That I could do. What I could do— The only, The only atonement.  Let me end you here... Mamiya Takuji. This is below the “End Sky”... isn’t that just right. It suits our ending, doesn’t it... Here is a sky of ending that exists only for you... This is the land of the end...  “No! Absolutely not!” ...Why... did you follow me...  Predestination... harmony, is it... I see... it looks like no matter what, to you... I’m already of no value at all, right... To think I was defeated by this guy... how helpless... This too is reality... Then I’ll accept it...  For some reason, I seemed to see a sunflower standing in the night sky... Only for a moment... That sunflower... As if somewhere... A sunflower... Together with Usaki... Yeah... I am the older brother... If only... I could be her brother a little longer...  Huh... Just now... That... that landscape... Is that so... that landscape... I know it too... The sunflower halfway up the slope... An azure sky and sunflowers. Big clouds floating... Usaki wearing a big hat... And walking together with me... Walking and walking... In order to... The two of us together... Climb that slope... Because... there is a very beautiful view beyond that slope...

You are playing a galgame, but you find this gal confusing and give up. So you start writing a data structure problem instead. Given a sequence of length $n$, there are $m$ operations. Each operation is one of the following: 1. Add $x$ to the range $[l, r]$. 2. For the range $[l, r]$, query $$a[l]^{a[l+1]^{a[l+2]^{\dots ^{a[r]}}}} \mod p.$$

The first line contains two integers $n, m$, the length of the sequence and the number of operations. The second line contains $n$ integers, the sequence. Each of the next $m$ lines is one of the following two operations. - $1\ l\ r\ x$: add $x$ to the range $[l, r]$. - $2\ l\ r\ p$: query the range $[l, r]$ with modulus $p$.

For each query, output one number as the answer.

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477. Constraints: - For 100% of the testdata, $n, m \le 500000$, each number in the sequence is in $[1, 2 \cdot 10^9]$, $p \le 2 \cdot 10^7$, and each added $x$ is in $[0, 2 \cdot 10^9]$. There are 10 sets of testdata. Translated by ChatGPT 5