408523: GYM103181 D Markat

Marko, the bartender, has a long night ahead of him. He has $$$N$$$ glasses (of infinite capacity) arranged in a sequence, numbered from $$$1$$$ to $$$N$$$. Initially all glasses are empty, but he will perform some operations on it:

• given 4 integers $$$L, R, X, Y$$$, he will add $$$X^Y$$$ milliliters of lemon juice to each glass in the interval $$$[L, R]$$$
• given 3 integers $$$L, R, M$$$, he wonders if $$$M$$$ of his friends will come to the bar and he needs to serve them with lemon juice from the glasses in interval $$$[L, R]$$$, how much lemon juice will remain in total in these glasses. Marko always serves his friends with the maximum amount of lemon juice such that each friend receives the same amount of lemon juice. (No quantity of lemon juice is removed from the glasses, Marko just asks about this imaginary scenario)

Knowing the queries that Marko needs to perform through the night, help him answer his questions.

The first line of the input contains two integers $$$1 \leq N \leq 10^5$$$ and $$$1 \leq Q \leq 10^5$$$, the number of glasses and the number of queries.

The following $$$Q$$$ lines each describe a query, being one of the following types:

• $$$0\ L\ R\ X\ Y$$$, with $$$1 \le L \le R \le N$$$ and $$$0 \le X, Y \le 10^9$$$, describing the first type of query, meaning that Marko adds $$$X^Y$$$ milliliters of lemon juice in each of glasses in interval $$$[L, R]$$$.
• $$$1\ L\ R\ M$$$, with $$$1 \le L \le R \le N$$$ and $$$2 \le M \le 100$$$, describing the second type of query, meaning that Marko asks for the quantity of lemon juice in the glasses in interval $$$[L, R]$$$ modulo $$$M$$$.

The output should contain a line for each query of the second type with a single integer representing the answer to that query.

3 2
0 1 2 1 1
1 1 2 100

2