Mike likes arithmetic sequences! So, he wants to create a data structure which maintains an array of ~N~ integers, each initially equal to ~0~, which supports three types of operations:

• 1 L R X V Increase the elements at positions ~L, L+X, L+2X, L+3X, \dots, R~ by ~V~. It is guaranteed that ~R - L~ is a multiple of ~X~.
• 2 L R X V Set the elements at positions ~L, L+X, L+2X, L+3X, \dots, R~ to ~V~. It is guaranteed that ~R - L~ is a multiple of ~X~.
• 3 Y Output the value of the element at position ~Y~.

Unfortunately, Mike does not know how to implement such a data structure. Can you help him implement this data structure and perform ~Q~ operations on it?

Constraints

~1 \le N, Q \le 5 \times 10^5~

~1 \le L \le R \le N~

~1 \le X < N~

~1 \le Y \le N~

~R - L~ is a multiple of ~X~.

~-10^9 \le V \le 10^9~

Subtask 1 [15%]

~X = 2~

Subtask 2 [5%]

~1 \le X \le 2~

Subtask 3 [30%]

~1 \le N, Q \le 2 \times 10^5~

There are no operations of type ~2~.

Subtask 4 [25%]

There are no operations of type ~2~.

Subtask 5 [15%]

~1\le N, Q \le 2 \times 10^5~

Subtask 6 [10%]

No additional constraints.

Input Specification

The first line contains two space-separated integers, ~N~ and ~Q~.

The ~i~-th of the following ~Q~ lines denotes the ~i~-th operation, in one of the three formats described above.

Output Specification

For each operation of type ~3~, 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 ~[0, 0, 0, 0, 0]~.

The first operation increases the values of the elements at positions ~1~, ~3~ and ~5~ by ~4~. The array becomes ~[4, 0, 4, 0, 4]~.

The second operation sets the values of the elements at positions ~2~, ~3~ and ~4~ to ~6~. The array becomes ~[4, 6, 6, 6, 4]~.

The third operation queries the value of the element at position ~1~, which is ~4~.

The fourth operation queries the value of the element at position ~2~, which is ~6~.