Ограничения: время – 8s/16s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
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.
Input
The first line contains two integers `N` and `Q` (`1\ ≤\ N\ ≤\ 1\ 000\ 000\ 000`, `1\ ≤\ Q\ ≤\ 50\ 000`),
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 their stones are in
boxes labeled `L` to `R` (inclusive).
Output
For 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.
Sample Input 1
6 3
2 1 6
1 1 5 1 2
2 1 6
Sample Input 2
4 5
1 1 4 3 4
2 1 1
2 2 2
2 3 3
2 4 4
Sample Input 3
4 4
1 1 4 7 9
2 1 4
1 1 4 1 1
2 1 4
First sample description:
The boxes start containing {0, 0, 0, 0, 0, 0}, 0 stones in total.
After that the device sets the
stones to {1 mod 2, 2 mod 2, 3 mod 2, 4 mod 2, 5 mod 2, 0} = {1,0,1,0,1,0}, or 3 stones in total.
Source: COCI 2009/2010 contest #1