AT_abc155_f [ABC155F] Perils in Parallel

[problemUrl]: https://atcoder.jp/contests/abc155/tasks/abc155_f 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\

### 制約 - 入力はすべて整数 - $ 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 条件を満たすコードの組合せが複数あり得る場合、どれを出力しても構いません。