给定一个N和Q，表示有N个篮子（编号从1到N）和Q个操作，$1 \le N \le 1 000 000 000$) ($1 \le Q \le 50000$，接下来Q行，每行表示一个操作，操作共有两类，第一类以1开头后面跟4个数，如："1 L R A B" ($1 \le L \le R \le N$) ($1\le A, B \le 1 000 000$), 表示要按规则把蓝子中的石头设成一定的数（规则后面说明）；第二类以数字2开头后面跟两个数如："2 L R",($1 \le L \le R \le N$).表示询问L和R间（包括端点）的所有篮子中的石头个数。
规则：
"1 L R A B"，表示重新设置编号从L到R的篮子内的石头（编号为X的篮子设成$(x-L+1）\times A \ mod \ B$.
SCORING
Test cases worth 30% total points have $N \ and\ Q \le 1000$.
Test cases worth 70% total points have $Q \le 1000$.

SAMPLE TESTS

input
6 3
2 1 6
1 1 5 1 2
2 1 6
output
0
3

input
4 5
1 1 4 3 4
2 1 1
2 2 2
2 3 3
2 4 4
output
3
21
0

input
4 4
1 1 4 7 9
2 1 4
1 1 4 1 1
2 1 4
output
16
0