E. Colorful Operationstime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou have an array a_1,a_2, \dots, a_n. Each element initially has value 0 and color 1. You are also given q queries to perform:   Color l r c: Change the color of elements a_l,a_{l+1},\cdots,a_r to c (1 \le l \le r \le n, 1 \le c \le n).  Add c x: Add x to values of all elements a_i (1 \le i \le n) of color c (1 \le c \le n, -10^9 \le x \le 10^9).  Query i: Print a_i (1 \le i \le n). InputThe first line of input contains two integers n and q (1 \le n,q \le 10^6) — the length of array a and the number of queries you have to perform.Each of the next q lines contains the query given in the form described in the problem statement.OutputPrint the answers to the queries of the third type on separate lines.ExamplesInput
5 8
Color 2 4 2
Add 2 2
Query 3
Color 4 5 3
Color 2 2 3
Add 3 3
Query 2
Query 5
Output
2
5
3
Input
2 7
Add 1 7
Query 1
Add 2 4
Query 2
Color 1 1 1
Add 1 1
Query 2
Output
7
7
8
NoteThe first sample test is explained below. Blue, red and green represent colors 1, 2 and 3 respectively.  
5 8
Color 2 4 2
Add 2 2
Query 3
Color 4 5 3
Color 2 2 3
Add 3 3
Query 2
Query 5

2 5 3 
['brute force', 'data structures', 'implementation', '*2400']