15380번 - The Grand Noi and ICPC Battle 다국어

The Nois are an ancient and cultured race who have a strange fascination in 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’s for another story). But 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 Noi 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 Noi 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, ..., 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 for all indices i, j, k such that L ≤ i < j < k ≤ 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 Noi 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 A_L, A_L+1, ..., A_R−1, AR to V.
• ASK L R - Output the sum of all A_i · A_j · A_k for all indices i, j, k such that L ≤ i < j < k ≤ R. Output the answer modulo 10⁸.

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

Constraints

• 1 ≤ N ≤ 10⁹
• 1 ≤ Q ≤ 10⁵
• 1 ≤ L ≤ R ≤ N
• 1 ≤ V ≤ 10⁶

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 for all indices i, j, k such that L ≤ i < j < k ≤ R, modulo 10⁸.