Mike likes arithmetic sequences! So, he wants to create a data structure which maintains an array of integers, each initially equal to
, which supports three types of operations:
1 L R X V
Increase the elements at positionsby
. It is guaranteed that
is a multiple of
.
2 L R X V
Set the elements at positionsto
. It is guaranteed that
is a multiple of
.
3 Y
Output the value of the element at position.
Unfortunately, Mike does not know how to implement such a data structure. Can you help him implement this data structure and perform operations on it?
Constraints
is a multiple of
.
Subtask 1 [15%]
Subtask 2 [5%]
Subtask 3 [30%]
There are no operations of type .
Subtask 4 [25%]
There are no operations of type .
Subtask 5 [15%]
Subtask 6 [10%]
No additional constraints.
Input Specification
The first line contains two space-separated integers, and
.
The -th of the following
lines denotes the
-th operation, in one of the three formats described above.
Output Specification
For each operation of type , output the value of the queried element on a separate line.
Sample Input
5 4
1 1 5 2 4
2 2 4 1 6
3 1
3 2
Sample Output
4
6
Explanation
The initial array is .
The first operation increases the values of the elements at positions ,
and
by
. The array becomes
.
The second operation sets the values of the elements at positions ,
and
to
. The array becomes
.
The third operation queries the value of the element at position , which is
.
The fourth operation queries the value of the element at position , which is
.
Comments