ALADIN
Aladin was walking down the path one day when he found the strangest thing. N empty boxes right next to a weird alien machine. After a bit of fumbling around he got the machine to do something. The machine now accepts 4 integers L, R, A and B. After that hitting the big red glowing button labeled "NE DIRAJ" causes the machine to go crazy and follow the next routine:
· Set the number of stones in the box labeled L to A modulo B.
· It procedes to fly to the box labeled L+1, and set the number of stones there to (2∙A) mod B.
· It procedes to fly to the box labeled L+2, and set the number of stones there to (3∙A) mod B.
· Generaly, it visits each box labeled between L and R, and set the number of stones there to
( (X - L + 1)∙A) mod B. where X is the box label.
· After it visits the box labeled R. It settles down for further instructions.
During the game Aladin wonders what is the total number of stones in some range of boxes.
Write a program that simulates the device and answers Aladins questions.
SCORING
Test cases worth 30% total points have N and Q ≤ 1000.
Test cases worth 70% total points have Q ≤ 1000.
Input:
Output:
Input:
Output:
Input:
Output:
· Set the number of stones in the box labeled L to A modulo B.
· It procedes to fly to the box labeled L+1, and set the number of stones there to (2∙A) mod B.
· It procedes to fly to the box labeled L+2, and set the number of stones there to (3∙A) mod B.
· Generaly, it visits each box labeled between L and R, and set the number of stones there to
( (X - L + 1)∙A) mod B. where X is the box label.
· After it visits the box labeled R. It settles down for further instructions.
During the game Aladin wonders what is the total number of stones in some range of boxes.
Write a program that simulates the device and answers Aladins questions.
InputThe first line contains two integers N i Q (1 ≤ N ≤ 1 000 000 000) (1 ≤ Q ≤ 50000), number of boxes and number of queries. The next Q lines contain information about the simulation. If the line starts with 1, than it follows the format "1 L R A B" (1 ≤ L ≤ R ≤ N) (1 ≤ A, B ≤ 1 000 000), meaning that Aladin keyed in numbers L, R, A and B in the device and allowed the device to do its job. If the line starts with 2, than it follows the format "2 L R" (1 ≤ L ≤ R ≤ N).
Meaning that Aladin wonders how many stones in total are ther stones are in boxes labeled L to R (inclusive).
Meaning that Aladin wonders how many stones in total are ther stones are in boxes labeled L to R (inclusive).
OutputFor each query beginning with 2 output the answer to that particular query.
Queries should be processed in the order they are given in the input.
Queries should be processed in the order they are given in the input.
SCORING
Test cases worth 30% total points have N and Q ≤ 1000.
Test cases worth 70% total points have Q ≤ 1000.
Input:
6 3
2 1 6
1 1 5 1 2
2 1 6
Output:
0
3Input:
4 5
1 1 4 3 4
2 1 1
2 2 2
2 3 3
2 4 4
Output:
3
2
1
0Input:
4 4
1 1 4 7 9
2 1 4
1 1 4 1 1
2 1 4
Output:
16
0Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.