You 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$).

Input

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

Output

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

Note

The first sample test is explained below. Blue, red and green represent colors $1$, $2$ and $3$ respectively.