/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 100000;
const int BITS = 17;
int N, K;
struct Segment
{
int l, r;
};
bool operator < (const Segment &a, const Segment &b)
{
if(a.l != b.l)
return a.l < b.l;
return a.r > b.r;
}
Segment seg[N_MAX + 2];
vector <Segment> sorted;
int anc[N_MAX + 2][BITS];
int sumMax;
set <int> del;
set <int> active;
int getMax (int first, int last)
{
if(first > last)
return 0;
int curr = last;
int cnt = 1;
for(int bit = BITS - 1; bit >= 0; bit--)
if(first <= anc[curr][bit])
{
cnt += (1 << bit);
curr = anc[curr][bit];
}
return cnt;
}
void init ()
{
int j = -1;
for(int i = 0; i < (int) sorted.size(); i++)
{
while(j < i - 1 && sorted[j + 1].r < sorted[i].l)
j++;
anc[i][0] = j;
}
for(int bit = 1; bit < BITS; bit++)
for(int i = 0; i < (int) sorted.size(); i++)
{
if(anc[i][bit - 1] == -1)
anc[i][bit] = -1;
else
anc[i][bit] = anc[anc[i][bit - 1]][bit - 1];
}
for(int i = 0; i < (int) sorted.size(); i++)
active.insert(i);
del.insert(-1);
del.insert((int) sorted.size());
sumMax = getMax(0, (int) sorted.size() - 1);
}
void delSeg (int i)
{
if(del.find(i) != del.end())
return;
set <int> :: iterator itr = del.upper_bound(i);
set <int> :: iterator itl = prev(itr);
int il = *itl;
int ir = *itr;
sumMax -= getMax(il + 1, ir - 1);
del.insert(i);
active.erase(i);
sumMax += getMax(il + 1, i - 1);
sumMax += getMax(i + 1, ir - 1);
}
void addSeg (int i)
{
set <int> :: iterator it = del.find(i);
if(it == del.end())
return;
set <int> :: iterator itr = next(it);
set <int> :: iterator itl = prev(it);
int il = *itl;
int ir = *itr;
sumMax -= getMax(il + 1, i - 1);
sumMax -= getMax(i + 1, ir - 1);
del.erase(it);
active.insert(i);
sumMax += getMax(il + 1, ir - 1);
}
vector <int> prevDels;
void delAll (int l, int r)
{
int curr;
{
int L = 0, R = (int) sorted.size();
while(L < R)
{
int mid = (L + R) / 2;
if(l <= sorted[mid].r)
R = mid;
else
L = mid + 1;
}
curr = L;
}
while(curr < (int) sorted.size() && sorted[curr].l <= r)
{
prevDels.push_back(curr);
delSeg(curr);
curr++;
}
}
void addAll ()
{
while(prevDels.empty() == false)
{
addSeg(prevDels.back());
prevDels.pop_back();
}
}
struct SGTNode
{
ll sum;
int lazy;
};
SGTNode operator + (const SGTNode &u, const SGTNode &v)
{
return SGTNode{u.sum + v.sum, 0};
}
SGTNode SGT[N_MAX * 2 * 4 + 2];
void split (int node, int l, int r)
{
int mid = (l + r) / 2;
int lSon = node * 2, rSon = node * 2 + 1;
SGT[lSon].sum += (ll) SGT[node].lazy * (mid - l + 1);
SGT[rSon].sum += (ll) SGT[node].lazy * (r - mid);
SGT[lSon].lazy += SGT[node].lazy;
SGT[rSon].lazy += SGT[node].lazy;
SGT[node].lazy = 0;
}
void update (int node, int l, int r, int ul, int ur, int uval)
{
if(ul <= l && r <= ur)
{
SGT[node].sum += (ll) uval * (r - l + 1);
SGT[node].lazy += uval;
return;
}
split(node, l, r);
int mid = (l + r) / 2;
int lSon = node * 2, rSon = node * 2 + 1;
if(ul <= mid)
update(lSon, l, mid, ul, ur, uval);
if(mid + 1 <= ur)
update(rSon, mid + 1, r, ul, ur, uval);
SGT[node] = SGT[lSon] + SGT[rSon];
}
void update (int ul, int ur, int uval)
{
update(1, 1, N * 2, ul, ur, uval);
}
ll query (int node, int l, int r, int ql, int qr)
{
if(ql <= l && r <= qr)
return SGT[node].sum;
split(node, l, r);
int mid = (l + r) / 2;
int lSon = node * 2, rSon = node * 2 + 1;
ll sum = 0;
if(ql <= mid)
sum += query(lSon, l, mid, ql, qr);
if(mid + 1 <= qr)
sum += query(rSon, mid + 1, r, ql, qr);
return sum;
}
ll query (int ql, int qr)
{
return query(1, 1, N * 2, ql, qr);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> K;
for(int i = 1; i <= N; i++)
cin >> seg[i].l >> seg[i].r;
{
vector <int> aux;
for(int i = 1; i <= N; i++)
{
aux.push_back(seg[i].l);
aux.push_back(seg[i].r);
}
sort(aux.begin(), aux.end());
aux.resize(unique(aux.begin(), aux.end()) - aux.begin());
unordered_map <int, int> mp;
for(int i = 0; i < (int) aux.size(); i++)
mp[aux[i]] = i + 1;
for(int i = 1; i <= N; i++)
{
seg[i].l = mp[seg[i].l];
seg[i].r = mp[seg[i].r];
}
}
for(int i = 1; i <= N; i++)
seg[i].r--;
{
for(int i = 1; i <= N; i++)
sorted.push_back(seg[i]);
sort(sorted.begin(), sorted.end());
vector <Segment> newSorted;
for(Segment s : sorted)
{
while(newSorted.empty() == false && s.r <= newSorted.back().r)
newSorted.pop_back();
newSorted.push_back(s);
}
sorted = newSorted;
}
init();
if(sumMax < K)
{
cout << "-1\n";
return 0;
}
int curr = 1;
for(int i = 1; i <= K; i++)
{
while(curr <= N)
{
if(query(seg[curr].l, seg[curr].r) > 0)
{
curr++;
continue;
}
delAll(seg[curr].l, seg[curr].r);
update(seg[curr].l, seg[curr].r, + 1);
if(sumMax < K - i)
{
addAll();
update(seg[curr].l, seg[curr].r, - 1);
curr++;
continue;
}
prevDels.clear();
break;
}
cout << curr << "\n";
curr++;
}
return 0;
}
