配点: $600$ 点

問題文

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$ つ出力してください。

制約

• 入力はすべて整数
• $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)$

入力

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

$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$ を満たす必要がある。

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

2
1 4

座標 $5, 10$ に電源がオンの爆弾が、座標 $8$ に電源がオフの爆弾があります。

コード $1$ を切ると座標 $1$ 以上 $10$ 以下にある爆弾、つまり全ての爆弾の電源が切り替わります。

コード $4$ を切ると座標 $8$ 以上 $9$ 以下にある爆弾、つまり爆弾 $3$ のみの電源が切り替わります。

したがって、コード $1, 4$ の $2$ 本を切ることで全ての爆弾の電源がオフになります。

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

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