There is a sequence of N numbers. Initially, the numbers in the sequence are 0 ... N-1. We'll then do different kinds of operations on it.
The operations could be:
add a b x, add all numbers in the interval [a,b) by x.
mul a b x, multiply all numbers in the interval [a,b) by x.
rot a b x, rotate the numbers in the interval [a,b) to the right by x positions.
rev a b, reverse the numbers in the interval [a,b).
We will query the sum of interval, sum a b means we need the sum of interval [a,b).
All subscripts are 0-based.
For example, when N is 6, after the operation 'rot 2 5 1', the sequence will become 0 1 4 2 3 5. And then take the operation 'mul 3 4 10', the sequence will become 0 1 4 20 3 5. If we query 'sum 0 4' now, the answer should be 25.
Input
About 10 test cases, seperated by blank line.
First line of each case is two integers N (1<=N<=40000000) and M (0<=M<2048). The following M lines are descriptions of operations and queries as the format in problem description.
All numbers are integers. For all operations, 0<=a<b<=N, 0<=x<16.
Output
For each query, output one line indicating the answer mod 9875321.
Output a blank line after each test case.
Sample Input
6 7
rot 2 5 1
mul 3 4 10
sum 0 4
add 0 6 1
sum 0 6
rev 0 6
sum 0 1
Sample Output
25
39
6