TopCoder

Thumb tumblr m6532itd121rnos1s
$(pr)^3pony$
https://prprprpony.github.io/blog/ $\\\huge PinkiePie:"OkieDokieLokie"$

User's AC Ratio

87.5% (7/8)

Submission's AC Ratio

31.2% (35/112)

Description

身為一個擁有N個箱子(編號1~N)的怪人,

有時候你會想對編號在某個區間[L,R]內的箱子做一些奇怪的事情:

將編號L的箱子弄成裡面恰有A mod B顆球
將編號L+1的箱子弄成裡面恰有2*A mod B顆球
...
將編號X的箱子內弄成裡面恰有(X-L+1)*A mod B顆球
...
將編號R的箱子內弄成裡面恰有(R-L+1)*A mod B顆球

而為了避免放錯,你三不五時會檢查一下編號在[L,R]的箱子內所有球的數量。

(一開始箱子都是空的)

Input Format

第一行有兩個整數N(1<=N<=1000000000),Q(1<=Q<=50000)

接下來Q行依序代表每一個動作

如果該行格式為"1 L R A B"(1<=L<=R<=N)(1<=A,B<=1000000)代表對編號在[L,R]內的箱子做奇怪的事情

如果該行格式為"2 L R"則代表檢查編號在[L,R]的箱子內所有球的數量

Output Format

對於每次檢查,依序輸出答案,每個答案一行。

Sample Input

6 3
2 1 6
1 1 5 1 2
2 1 6

Sample Output

0
3

Hints

範例測資:{0,0,0,0,0,0} => {1,0,1,0,1,0}

Problem Source

原TIOJ1606 / Problem Translater: shik
Original Source: COCI 2009/2010 Contest #1 ALADIN

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1900 65536 262144 1
1 1900 65536 262144 2
2 1900 65536 262144 3
3 1900 65536 262144 4
4 1900 65536 262144 5
5 1900 65536 262144 6
6 1900 65536 262144 7
7 1900 65536 262144 8
8 1900 65536 262144 9
9 1900 65536 262144 10