## Yet Another Contest 7 P6 - Arithmetic Sequence Data Structure

View as PDF

Points: 25 (partial)
Time limit: 4.0s
Java 7.0s
Python 8.0s
Memory limit: 256M
Java 512M
Python 512M

Author:
Problem type

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 positions by . It is guaranteed that is a multiple of .
• 2 L R X V Set the elements at positions to . 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 .

There are no operations of type .

There are no operations of type .

#### 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 .