UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#1938. [CROATIAN2010] ALADIN

Statistics 下载数据

Description

有一个长度为 N 的序列P 和两种操作,共 Q个: 1. 给定 L, R, A, B,将第 L 到第 R 个之间的每个元素 Px 变成((X-L+1)×A)mod B 。 2. 给定 L, R,询问第 L 到第 R 个元素的和。 数据规模:N≤10^9 ,Q≤50000 , A, B≤106

Input

The first line contains two integers N i 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 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.

Sample Input

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

Sample Output

0
3

Hint

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

CONTEST #1 24.10.2009.