Stations
Description
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$.
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.
Input
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.
Output
For each query, print in a single line the sum of $b_j$ over the given interval.
Samples
1 3
2 1 1
1 1 1
2 1 1
1
1
5 10
1 3 4
2 3 5
1 1 5
2 1 5
1 4 5
2 2 4
1 2 3
2 1 3
1 5 5
2 2 5
4
10
5
4
5
Note
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, 2, 1]$;
- $[1, 2, 2, 3, 2]$;
- $[1, 2, 2, 1, 2]$;
- $[1, 1, 2, 1, 2]$;
- $[1, 1, 2, 1, 1]$.