/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 1e5 + 10;
struct interval
{
int l, r;
};
int n, k;
interval seg[maxn];
void input()
{
cin >> n >> k;
for (int i = 1; i <= n; i ++)
cin >> seg[i].l >> seg[i].r;
}
bool cmp(interval it1, interval it2)
{
if (it1.l != it2.l)
return it1.l < it2.l;
return it1.r > it2.r;
}
interval rel[maxn];
int m;
void get_relevant()
{
vector < interval > vec;
for (int i = 1; i <= n; i ++)
vec.push_back(seg[i]);
sort(vec.begin(), vec.end(), cmp);
int cl = 1e9 + 10;
for (int i = n - 1; i >= 0; i --)
{
if (vec[i].r >= cl)
{
continue;
}
rel[++ m] = vec[i];
cl = vec[i].r;
}
reverse(rel + 1, rel + m + 1);
}
int len[2][maxn], pt[2][maxn], used[maxn];
void calc_pointers()
{
int last = 0;
rel[m + 1].l = 1e9 + 10;
for (int i = 1; i <= m; i ++)
{
if (used[i])
continue;
len[0][i] = 0;
pt[0][i] = 0;
if (last != 0)
pt[0][i] = pt[0][last];
while(rel[pt[0][i]].r <= rel[i].l)
pt[0][i] ++;
pt[0][i] --;
while(pt[0][i] > 0 && used[pt[0][i]])
pt[0][i] --;
len[0][i] = len[0][pt[0][i]] + 1;
last = i;
}
last = m + 1;
for (int i = m; i > 0; i --)
{
if (used[i])
continue;
len[1][i] = 0;
pt[1][i] = m + 1;
if (last != m + 1)
pt[1][i] = pt[1][last];
while(rel[pt[1][i]].l >= rel[i].r)
pt[1][i] --;
pt[1][i] ++;
while(pt[1][i] <= m && used[pt[1][i]])
pt[1][i] ++;
len[1][i] = len[1][pt[1][i]] + 1;
///cout << "line 107 " << i << " " << pt[1][i] << endl;
last = i;
}
}
bool intersect(interval a, interval b)
{
if (a.l == b.l)
return true;
if (a.l > b.l)
swap(a, b);
if (a.r >= b.r)
return true;
return a.r > b.l;
}
void get_intersections(interval cur)
{
for (int i = 1; i <= m; i ++)
if (used[i] == 0 && intersect(rel[i], cur))
used[i] = 2;
}
set < pair < int, int > > act;
const int maxlog = 21;
int dp[maxlog][maxn];
void remove_interval(int l, int r)
{
while(true)
{
set < pair < int, int > > :: iterator it = act.lower_bound({l, -1});
if (it == act.end() || it -> first > r)
break;
if (it -> second <= r)
act.erase(it);
else
{
pair < int, int > nw;
nw.first = r + 1;
nw.second = it -> second;
act.erase(it);
act.insert(nw);
break;
}
}
set < pair < int, int > > :: iterator it = act.lower_bound({l, -1});
//cout << "cur " << it -> first << " " << it -> second << endl;
if (it != act.begin())
{
it = prev(it);
///cout << "back " << it -> first << " " << it -> second << endl;
if (it -> second > r)
{
pair < int, int > lf = *it, rf = *it;
lf.second = l - 1;
rf.first = r + 1;
act.erase(it);
act.insert(lf);
act.insert(rf);
}
else if (it -> second >= l)
{
pair < int, int > nw = *it;
nw.second = l - 1;
act.erase(it);
act.insert(nw);
}
}
}
int first_bef(int pos)
{
set < pair < int, int > > :: iterator it = act.lower_bound({pos, -1});
if (it == act.begin())
return 0;
return min(pos - 1, prev(it) -> second);
}
int first_aft(int pos)
{
set < pair < int, int > > :: iterator it = act.lower_bound({pos, -1});
if (it != act.begin() && prev(it) -> second > pos)
return pos + 1;
if (it == act.end())
return m + 1;
return max(pos + 1, it -> first);
}
int lb_last, rb_last;
int get_longest(interval cur)
{
/**int lb = 1;
while(lb <= m && rel[lb].r <= cur.l)
lb ++;
lb --;
while(lb > 0 && used[lb])
lb --;
int rb = m;
while(rb > 0 && rel[rb].l >= cur.r)
rb --;
rb ++;
while(rb <= m && used[rb])
rb ++;*/
int lf = 1, rf = m;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (rel[mf].r <= cur.l)
lf = mf + 1;
else
rf = mf - 1;
}
int lb = lf;
lf = 1;
rf = m;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (rel[mf].l >= cur.r)
rf = mf - 1;
else
lf = mf + 1;
}
int rb = rf;
int longest = len[0][first_bef(lb)] + len[1][first_aft(rb)];
lb_last = lb;
rb_last = rb;
/**for (pair < int, int > cur : act)
cout << cur.first << " ::: " << cur.second << endl;
cout << "borders " << lb << " " << rb << " " << first_bef(lb) << " " << first_aft(rb) << endl;*/
return longest;
}
void reverse_intersections()
{
for (int i = 1; i <= m; i ++)
if (used[i] == 2)
used[i] = 0;
}
void apply_intersections()
{
for (int i = 1; i <= m; i ++)
if (used[i] == 2)
used[i] = 1;
}
void binary_lifting()
{
int last = 0;
rel[m + 1].l = 1e9 + 10;
for (int i = 1; i <= m; i ++)
{
if (used[i])
continue;
len[0][i] = 0;
pt[0][i] = 0;
if (last != 0)
pt[0][i] = pt[0][last];
while(rel[pt[0][i]].r <= rel[i].l)
pt[0][i] ++;
pt[0][i] --;
while(pt[0][i] > 0 && used[pt[0][i]])
pt[0][i] --;
len[0][i] = len[0][pt[0][i]] + 1;
last = i;
}
for (int i = 0; i <= m; i ++)
dp[0][i] = pt[0][i];
for (int j = 1; j < maxlog; j ++)
{
for (int i = 1; i <= m; i ++)
{
dp[j][i] = dp[j - 1][dp[j - 1][i]];
}
}
}
void create_sequence()
{
act.insert({1, m});
binary_lifting();
vector < int > seq;
for (int i = 1; i <= n && k > 0; i ++)
{
bool valid = true;
for (int cur : seq)
{
if (intersect(seg[cur], seg[i]))
{
valid = false;
break;
}
}
if (!valid)
continue;
///get_intersections(seg[i]);
calc_pointers();
int longest = get_longest(seg[i]);
cout << "longest " << i << " -- " << longest << endl;
for (int j = 1; j <= m; j ++)
cout << used[j] << " ";
cout << endl;
/* for (int j = 1; j <= m; j ++)
cout << len[0][j] << " ";
cout << endl;*/
if (longest >= k - 1)
{
seq.push_back(i);
k --;
remove_interval(lb_last, rb_last);
get_intersections(seg[i]);
apply_intersections();
}
/**for (int j = 1; j <= m; j ++)
cout << used[j] << " ";
cout << endl;*/
}
if (k != 0)
{
cout << -1 << endl;
return;
}
for (int cur : seq)
cout << cur << endl;
}
void solve()
{
input();
get_relevant();
///calc_pointers();
create_sequence();
}
int main()
{
solve();
return 0;
}
/**
2 2
1 3
1 2
20 9
18 22
2 5
28 31
21 25
25 27
3 6
36 39
22 26
8 12
27 31
27 29
32 36
14 18
16 20
22 26
10 14
17 21
13 17
15 19
37 40
*/
