• # For Solution

Colorful Operations solution codeforces:- You have an array a1,a2,,ana1,a2,…,an. Each element initially has value 00 and color 11. You are also given qq queries to perform:

• Color ll rr cc: Change the color of elements al,al+1,,aral,al+1,⋯,ar to cc (1lrn1≤l≤r≤n1cn1≤c≤n).
• Add cc xx: Add xx to values of all elements aiai (1in1≤i≤n) of color cc (1cn1≤c≤n109x109−109≤x≤109).
• Query ii: Print aiai (1in1≤i≤n).

## Colorful Operations solution codeforces

The first line of input contains two integers nn and qq (1n,q1061≤n,q≤106) — the length of array aa and the number of queries you have to perform.

Each of the next qq lines contains the query given in the form described in the problem statement.

Output

Print the answers to the queries of the third type on separate lines.

Examples

## Colorful Operations solution codeforces

Copy
5 8
Color 2 4 2
Query 3
Color 4 5 3
Color 2 2 3
Query 2
Query 5


output

Copy
2
5
3


## Colorful Operations solution codeforces

Copy
2 7
Query 1
Query 2
Color 1 1 1
Query 2


## Colorful Operations solution codeforces

Copy
7
7
8

Note

The first sample test is explained below. Blue, red and green represent colors 1122 and 33 respectively.