Mysterious Object

A person finds a mysterious object while walking. To the left of the object, there are N boxes in a row, and every box is initially empty.

The object accepts four integers L, R, A, and B. When its button is pressed, it changes the number of stones in boxes L through R by the following rule.

Box L receives A mod B stones. Box L+1 receives (2*A) mod B stones. In general, for every X such that L <= X <= R, box X is set to ((X-L+1)*A) mod B stones.

Given several commands, answer every command that asks for the total number of stones in a range.

The first line contains the number of boxes N and the number of queries Q.

• 1 <= N <= 1,000,000,000
• 1 <= Q <= 50,000

Each of the next Q lines contains one command.

• 1 L R A B: set the number of stones in boxes L through R by the rule above. (1 <= L <= R <= N, 1 <= A, B <= 1,000,000)
• 2 L R: ask for the total number of stones in boxes L through R. (1 <= L <= R <= N)

All ranges include both endpoints.

For each command that starts with 2, print the total number of stones in the requested range on its own line.