F. Stationstime limit per test2.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThere 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.InputThe 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.OutputFor each query, print in a single line the sum of b_j over the given interval.ExamplesInput
1 3
2 1 1
1 1 1
2 1 1
Output
1
1
Input
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
Output
4
10
5
4
5
NoteIn 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]. 
1 3
2 1 1
1 1 1
2 1 1

1 1 
['data structures', '*3400']