No.647 明太子

レベル : / 実行時間制限 : 1ケース 4.500秒 / メモリ制限 : 256 MB / 通常問題
タグ : / 解いたユーザー数 203
作問者 : mokomoko / テスター : cielciel
3 ProblemId : 2103 / 出題時の順位表

問題文

明太子同好会には$N$人のメンバーがいる。
今日は年に一度の明太子パーティーの日なので、メンバー達は明太子を買いに行くことにした。

明太子直売所では$M$種類の明太子が販売されており、$i$番の明太子の値段は$X_i$円、辛さは$Y_i$である。

$j$番のメンバーは$A_j$円以内で辛さが$B_j$以上の明太子を見ると購入せずにはいられなくなり、そのような条件に合う明太子は1種類につき1つ、必ず購入する。しかし、明太子にこだわりがある彼らがどちらか1つでも条件に合わない明太子は絶対に購入しない。

明太子同好会では最も多くの人が買ってきた明太子を「奇跡の明太子」とし1年間毎食欠かさず食べる文化があるのでどの明太子が最も多くの人に購入されたかを知りたい。

最も多く購入された明太子が複数ある場合は、全て「奇跡の明太子」に選ばれるようになる。

明太子同好会の代わりに「奇跡の明太子」に選ばれる明太子を求めてください。

2018/03/18 制約が4.5秒になりました。

入力

$N$
$A_1\ B_1$
$.$
$.$
$A_N\ B_N$
$M$
$X_1\ Y_1$
$.$
$.$
$X_M\ Y_M$

$1 \le N \le 10^4$
$1 \le M \le 10^3$
$1 \le X_i,Y_i,A_i,B_i \le 10^8$

出力

明太子同好会で「奇跡の明太子」に選ばれる明太子の番号を1行に1つずつ、昇順に出力してください。
1つも明太子が明太子同好会のメンバーに購入されなかった場合は0を出力してください。
また、最後には改行してください。

サンプル

サンプル1
入力
3
6 4
5 2
2 5
2
4 3
5 4
出力
2

1番の明太子は2番のメンバーに、2番の明太子は1,2番のメンバーにそれぞれ購入されます。
3番のメンバーは条件に合う明太子がないため1つも明太子を購入しません。

サンプル2
入力
5
5 7
6 3
4 1
8 6
5 4
3
2 4
6 5
4 2
出力
1

1番の明太子は2,3,5番のメンバーに、2番の明太子は1番のメンバーに、3番の明太子は3番のメンバーにそれぞれ購入されます。

サンプル3
入力
4
8 6
3 5
4 2
7 3
1
10 2
出力
0

明太子同好会のメンバーは全員、1つも明太子を購入することができません。

サンプル4
入力
3
3 4
1 7
5 3
4
1 5
2 6
5 2
6 7
出力
1
2

1番の明太子と2番の明太子はそれぞれ2人のメンバーに購入されます。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。