The Grand Noi and ICPC Battle

The Nois are an ancient and cultured race with a strange fascination for mathematics and computers. They are a peaceful race, but they are now engaged in an epic war against their feared foes, the Inter-continental Prairie Corgis (known as the ICPCs in short). The war has been in progress for years, and neither side has managed to make footholds in their opponent's territory.

But now the Nois have a grand plan to finally end the war and return to their normal activities of discovering new theorems and inventing math problems. The Nois, with their devastating intellects, have managed to create a superweapon that will blast the ICPCs into an alternate dimension where math and computers do not exist. (The very thought that such a dimension exists chills their bones, and the poor Noi who discovered the dimension is now locked in a psychiatric ward. But that is for another story.) Alas, ICPC spies discovered their plan, and a saboteur managed to sneak in and ruin the configuration of the Noi superweapon.

The superweapon is configured using a sequence of $N$ integers, and the Nois have devised a way to rapidly test for the right configuration. However, the only Noi who can write code to perform the tests is in a psychiatric ward, and they now desperately need help. The Nois have heard of your programming prowess, and have enlisted your help in reconfiguring their superweapon.

They sent you this message. Help us, oh great one! We need a program to help defeat the dastardly ICPCs. When looking for the right configuration of our superweapon, we perform either of two operations on our configuration sequence (which we will refer to as $A$): we either set $A_L, A_{L+1}, \dots, A_{R-1}, A_R$ to $V$ (for some integers $L$ and $R$), or we try to find the sum of all $A_i A_j A_k$ over the indices $i$, $j$, $k$ such that $L \le i < j < k \le R$ (for some integers $L$ and $R$).

The first line of input contains two integers $N$ and $Q$, separated by a single space, where $N$ is the length of the configuration sequence and $Q$ is the number of operations that the Nois have to perform.

The next $Q$ lines contain the operations to be performed on the configuration sequence in order, and are in either of the two following formats:

• SET L R V: set all of $A_L, A_{L+1}, \dots, A_{R-1}, A_R$ to $V$.
• ASK L R: output the sum of all $A_i A_j A_k$ over the indices $i$, $j$, $k$ such that $L \le i < j < k \le R$, modulo $10^8$.

Every element of the configuration sequence is initially set to 1.

Constraints:

• $1 \le N \le 10^9$
• $1 \le Q \le 10^5$
• $1 \le L \le R \le N$
• $1 \le V \le 10^6$

Output $M$ lines, where $M$ is the number of operations of the second kind. For each such line, output a single integer $S$, which is the sum of all $A_i A_j A_k$ over the indices $i$, $j$, $k$ such that $L \le i < j < k \le R$, modulo $10^8$. If fewer than three indices lie in the range, the sum is empty and the answer is 0.