题目描述

AlDebaran 王国の侵攻によって、AtCoder 王国の各地に爆弾が仕掛けられてしまいました。

幸いにも AtCoder 王国 ABC 隊の健闘により制御装置の一部が手に入ったので、あなたはこれを使って解除を試みることにしました。

仕掛けられた爆弾は $N$ 個あり、$1$ から $N$ の番号がついています。爆弾 $i$ は座標 $A_i$ にあり、電源は $B_i=1$ のときオンに、$B_i=0$ のときオフになっています。

制御装置には $M$ 本のコードがあり、$1$ から $M$ の番号がついています。コード $j$ を切ると、座標が $L_j$ 以上 $R_j$ 以下の全ての爆弾の電源のオン・オフが切り替わります。

切るコードをうまく選ぶことで全ての爆弾の電源をオフにできるか判定し、できるならばそのようなコードの組合せを $1$ つ出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $A_1$ $B_1$ : $A_N$ $B_N$ $L_1$ $R_1$ : $L_M$ $R_M$

输出格式

全ての爆弾の電源をオフにすることが不可能であれば -1 と出力せよ。可能であれば、それを達成するコードの組合せを次のように出力せよ。

$k$ $c_1$ $c_2$ $\dots$ $c_k$

ここで、$k$ は切るコードの本数 ($0$ でもよい) である。

また、$c_1,\ c_2,\ \dots,\ c_k$ は切るコードの番号であり、$1\ \leq\ c_1\ <\ c_2\ <\ \dots\ <\ c_k\ \leq\ M$ を満たす必要がある。

题目大意

有 $n$ 个电灯，编号从 $1$ 到 $n$ ，第 $i$ 个电灯在 $a_i$ 处，状态为$b_i$（ $b_i=0$ 或 $1$ ）。

有 $m$ 个开关，编号从 $1$ 到 $m$ ，第 $i$ 个开关控制 $l_i$ 到 $r_i$ ，如果按下开关则所有 $l_i$ 到 $r_i$ 中的电灯状态取反。

求是否有一组可行解，使得所有电灯状态都为0。没有输出-1，有则输出方案

3 4
5 1
10 1
8 0
1 10
4 5
6 7
8 9

2
1 4

4 2
2 0
3 1
5 1
7 0
1 4
4 7

-1

3 2
5 0
10 0
8 0
6 9
66 99

0

12 20
536130100 1
150049660 1
79245447 1
132551741 0
89484841 1
328129089 0
623467741 0
248785745 0
421631475 0
498966877 0
43768791 1
112237273 0
21499042 142460201
58176487 384985131
88563042 144788076
120198276 497115965
134867387 563350571
211946499 458996604
233934566 297258009
335674184 555985828
414601661 520203502
101135608 501051309
90972258 300372385
255474956 630621190
436210625 517850028
145652401 192476406
377607297 520655694
244404406 304034433
112237273 359737255
392593015 463983307
150586788 504362212
54772353 83124235

5
1 7 8 9 11

提示

制約

• 入力はすべて整数
• $1\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ A_i\ \leq\ 10^9\ (1\ \leq\ i\ \leq\ N)$
• $A_i$ は互いに相異なる
• $B_i$ は $0$ か $1$ のいずれか $(1\ \leq\ i\ \leq\ N)$
• $1\ \leq\ M\ \leq\ 2\ \times\ 10^5$
• $ 1\ \leq\ L_j\ \leq\ R_j\ \leq\ 10^9\ (1\ \leq\ j\ \leq\ M) $

Sample Explanation 1

座標 $5,\ 10$ に電源がオンの爆弾が、座標 $8$ に電源がオフの爆弾があります。 コード $1$ を切ると座標 $1$ 以上 $10$ 以下にある爆弾、つまり全ての爆弾の電源が切り替わります。 コード $4$ を切ると座標 $8$ 以上 $9$ 以下にある爆弾、つまり爆弾 $3$ のみの電源が切り替わります。 したがって、コード $1,\ 4$ の $2$ 本を切ることで全ての爆弾の電源がオフになります。

Sample Explanation 2

切るコードをどう選んでも、全ての爆弾の電源をオフにすることは不可能です。

Sample Explanation 3

はじめから全ての爆弾の電源がオフなので、コードを切る必要はありません。

Sample Explanation 4

条件を満たすコードの組合せが複数あり得る場合、どれを出力しても構いません。