A14510. Stations

There are $n$ cities in a row numbered from $1$ to $n$ .

The cities will be building broadcasting stations. The station in the $i$ -th city has height $h_i$ and range $w_i$ . It can broadcast information to city $j$ if the following constraints are met:

- $i \le j \le w_i$ , and
- for each $k$ such that $i < k \le j$ , the following condition holds: $h_k < h_i$ .

In other words, the station in city $i$ can broadcast information to city $j$ if $j \ge i$ , $j$ is in the range of $i$ -th station, and $i$ is strictly highest on the range from $i$ to $j$ (including city $j$ ).At the beginning, for every city $i$ , $h_i = 0$ and $w_i = i$ .

Then $q$ events will take place. During $i$ -th event one of the following will happen:

- City $c_i$ will rebuild its station so that its height will be strictly highest among all stations and $w_{c_i}$ will be set to $g_i$ .
- Let $b_j$ be the number of stations that can broadcast information to city $j$ . Print the sum of $b_j$ over all $j$ satisfying $l_i \le j \le r_i$ .

Your task is to react to all events and print answers to all queries.

The first line contains two integers $n$ and $q$ ( $1 \le n, q \le 2\cdot10^5$ ) — number of cities and number of events.

Then $q$ lines follow. The $i$ -th line begins with an integer $p_i$ ( $p_i = 1$ or $p_i = 2$ ).

If $p_i = 1$ a station will be rebuilt. Then two integers $c_i$ and $g_i$ ( $1 \le c_i \le g_i \le n$ ) follow — the city in which the station is rebuilt and its new broadcasting range.

If $p_i = 2$ you are given a query. Then two integers $l_i$ and $r_i$ ( $1 \le l_i \le r_i \le n$ ) follow — the range of cities in the query.

For each query, print in a single line the sum of $b_j$ over the given interval.

In the first test case, only station $1$ reaches city $1$ before and after it is rebuilt.

In the second test case, after each rebuild, the array $b$ looks as follows:

1. $[1, 1, 1, 2, 1]$ ;
2. $[1, 2, 2, 3, 2]$ ;
3. $[1, 2, 2, 1, 2]$ ;
4. $[1, 1, 2, 1, 2]$ ;
5. $[1, 1, 2, 1, 1]$ .