Time Limit : 2 sec
You have a long street of length N, and you want to install some lamps to light some segments of the road. So you will be given Q queries of two kinds:

1 L R : Install a lamp that can light the segment from L to R.

2 L R : What is the minimum number of installed lamps needed to light the segment [L, R], more formally, find the number of the smallest group of installed lamps such that the combined segments they light up fully cover the segment from point L to point R.

Input

The first line contains one integer N (1 ≤ N ≤ 2 × 10^5). The length of the street.

The second line contains one integer Q (2 ≤ Q ≤ 2 × 10^5). The number of queries.

Then follows Q lines. The i-th line contains three integers ti Li Ri. (ti ∈ {1, 2}, 1 ≤ Li ≤ Ri ≤ N), which represents the i-th query.

It is guaranteed that there is at least one query of type 2.

Output

For each query of type 2, output one line containing its answer or -1 if the answer doesn’t exist.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200000;
int  n, q, B;                          
int  val[MAXN + 2];                     
int  lazy[(MAXN+450)/450 + 2];         

void addLamp(int L,int R){             
    int bl = L / B , br = R / B;

    if (bl == br){                    
        for (int i=L;i<=R;++i) val[i] = max(val[i], R);
        return;
    }

    int endL = (bl+1)*B - 1;
    for (int i=L;i<=endL;++i) val[i] = max(val[i], R);

    for (int b=bl+1;b<br;++b)
        lazy[b] = max(lazy[b], R);

    int startR = br*B;
    for (int i=startR;i<=R;++i) val[i] = max(val[i], R);
}

int minLamps(int L,int R){              
    int cur=L, ans=0;
    while (cur <= R){
        int b   = cur / B;
        int best = max(val[cur], lazy[b]);   
        if (best < cur) return -1;          
        ++ans;
        cur = best + 1;                      
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    B = int(sqrt(n)) + 1;
    fill(val,  val+n+2, -1);
    fill(lazy, lazy+ (n+B-1)/B + 2, -1);
    while (q--){
        int t,L,R; cin >> t >> L >> R;
        --L; --R;                           
        if (t==1) addLamp(L,R);
        else      cout << minLamps(L,R) << '\n';
    }
}