### COCI 2009/2010, Contest #1

## Task 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**. - Generally, 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 Aladin's questions

### Input

The first line contains two integers **N** (1 ≤ **N** ≤ 1 000 000 000) and **Q** (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 ther 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.

### Scoring

Test cases worth 30% of total points have **N** and **Q** ≤ 1000.

Test cases worth 70% of total points have **Q** ≤ 1000.

### Sample Tests

## Input6 3 2 1 6 1 1 5 1 2 2 1 6 ## Output0 3 |
## Input4 5 1 1 4 3 4 2 1 1 2 2 2 2 3 3 2 4 4 ## Output3 2 1 0 |
## Input4 4 1 1 4 7 9 2 1 4 1 1 4 1 1 2 1 4 ## Output16 0 |

### 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.

All Submissions

Best Solutions

**Point Value:** 25 (partial)

**Time Limit:** 8.00s

**Memory Limit:** 64M

**Added:** Aug 13, 2013

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

Ronny_Chenon Aug 12, 2016 - 11:58:25 pm UTC Anyone helps?ImaxBlueon Aug 16, 2016 - 8:35:49 pm UTC Re: Anyone helps?there are going to be a maximum of 2Q points that actually matter