Runic Echo Row

Time limit: 3000 msMemory limit: 256 MB

A row of runes is kept on a table. Each rune has a color $c$ and a positive weight $w$ .

For any nonempty consecutive segment of the current row, split that segment into maximal contiguous blocks whose runes all have the same color. If a block $B$ contains runes with weights $w_1, w_2, \ldots, w_k$ , define its block weight as

W(B) = \sum_{j=1}^{k} w_j.

The echo score of the segment is

\sum_{B} W(B)^2,

where the sum is over all maximal same-color blocks $B$ inside the segment.

You must process updates to the row and answer echo score queries.

Input

The first line contains two integers $N$ and $Q$ ( $1 \le N \le 2 \times 10^5$ , ), the initial number of runes and the number of operations.

Output

For each operation of type $4$ , print one line containing a single integer: the echo score of the requested segment at that moment.

If there are no operations of type $4$ , print nothing.

Samples

Sample 1

Input

Output

For the first query, the blocks in positions $1$ through $5$ have total weights $5$ , $5$ , and $5$ , so the printed value is $5^2 + 5^2 + 5^2 = 75$ . The later printed values correspond to the row after the reversal, insertion, and deletion operations shown in the input.

Runic Echo Row

Input

Output

Samples

Sample 1

Submit

Submissions