Problem Description
You are given a strange problem. First you have got a sequence contains N integers A1,A2,A3,...AN.Then you should perform a sequence of M operations. An operation can be one of the following:
- Print operation l,r . Print the value of ∑i=lrAi.
- Modify operation x. Modify Ax to 2Ax
- Add operation l,r,x. Add xtoAi(l≤i≤r).
As the value of print operation can be rather large, print the remainder after dividing the number by 2333333.
Input
There are several test cases.
In each test case:
The first line contains two integers N,M(1≤N,M≤50000).
The second line contains N integers A1,A2,A3,...AN(1≤Ai≤109,1≤i≤N)
Each of the next M lines begin with a number type(1≤type≤3).
If type=1, there will be two integers more in the line: l,r(1≤l≤r≤N), which correspond the operation 1.
If type=2, there will be one integer more in the line: x(1≤x≤N), which correspond the operation 2.
If type=3, there will be three integers more in the line: l,r,x(1≤l≤r≤N,1≤x≤109), which correspond the operation 3.
Output
For each Print operation, output the remainder of division of the value by 2333333.
Sample Input
3 4
1 2 3
2 3
1 2 3
3 1 3 2
1 1 3
2 2
5 2
2 1
1 1 2
Sample Output
10
17
34