Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 3260
Boring Sequence Operations

Time Limit: 10 Seconds      Memory Limit: 32768 KB

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:

1. add a b x, add all numbers in the interval [a,b) by x.
2. mul a b x, multiply all numbers in the interval [a,b) by x.
3. rot a b x, rotate the numbers in the interval [a,b) to the right by x positions.
4. 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
```25