時間制限 : sec, メモリ制限 : KB
English / Japanese  

領域探索(kD 木)

いくつかの属性を持つレコードの集合(データベース)から、特定の属性の値が指定された領域に入るものを見つける問題を領域探索と呼びます。

2次元の平面上の点の集合に対し、与えられた領域に含まれる点を列挙してください。ただし、与えられた点の集合に対して、点の追加・削除は行われません。

入力

n
x0 y0
x1 y1
:
xn-1 yn-1
q
sx0 tx0 sy0 ty0
sx1 tx1 sy1 ty1
:
sxq-1 txq-1 syq-1 tyq-1

1行目の n は集合に含まれる点の数を表します。続く n 行に i 番目の点の座標が2つの整数 xi, yi で与えられます。

続く1行にクエリの数 q が与えられます。続く q 行に各クエリが4つの整数 sxi, txi, syi, tyi で与えられます。

出力

各クエリについて、点集合の中で sxixtxi かつ syiytyi を満たす点の番号を、番号の昇順に出力してください。1つの点の番号を1行に出力し、各クエリに対する出力の最後に1つの空行を出力してください(条件を満たす点がない場合は1つの空行になります)。

制約

  • 0 ≤ n ≤ 500,000
  • 0 ≤ q ≤ 20,000
  • -1,000,000,000 ≤ x, y, sx, tx, sy, ty ≤ 1,000,000,000
  • sxtx
  • syty
  • 各クエリについて、与えられた領域内に含まれる点の数は 100 を超えない。

入力例 1

6
2 1
2 2
4 2
6 2
3 3
5 4
2
2 4 0 4
4 10 2 5

出力例 1

0
1
2
4

2
3
5