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 \bmod B\).
• It proceeds to fly to the box labeled \(L+1\), and sets the number of stones there to \((2 \cdot A) \bmod B\).
• It proceeds to fly to the box labeled \(L+2\), and sets the number of stones there to \((3 \cdot A) \bmod B\).
• Generally, it visits each box labeled between \(L\) and \(R\), and sets the number of stones there to \(\big((X - L + 1) \cdot A\big) \bmod 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.

Test cases worth 30% total points have N and \(Q \le 1000\).
Test cases worth 70% total points have \(Q \le 1000\).

The first line contains two integers \(N\) and \(Q\) (\(1 \le N \le 1\,000\,000\,000\), \(1 \le Q \le 50\,000\)), the number of boxes and the number of queries.

The next \(Q\) lines contain information about the simulation.

• If a line starts with \(1\), it has the format 1 L R A B (\(1 \le L \le R \le N\), \(1 \le A, B \le 1\,000\,000\)), meaning that Aladin keyed the numbers \(L\), \(R\), \(A\) and \(B\) into the device and allowed the device to do its job.
• If a line starts with \(2\), it has the format 2 L R (\(1 \le L \le R \le N\)), meaning that Aladin wonders how many stones in total are in the boxes labeled \(L\) to \(R\), inclusive.

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, Q \le 1000\). Test cases worth \(70\%\) of total points have \(Q \le 1000\).

First sample description: the boxes start as \(\{0, 0, 0, 0, 0, 0\}\) — \(0\) stones in total. The device sets them to \(\{1 \bmod 2, 2 \bmod 2, 3 \bmod 2, 4 \bmod 2, 5 \bmod 2, 0\} = \{1, 0, 1, 0, 1, 0\}\), or \(3\) stones in total.

riseoj 작성

출처 COCI 2009/2010 Contest 1