問題文

2次元座標平面上に $N$ 個の点があり、$i$ ($1 \leq i \leq N$) 番目の点の座標は $(X_i, Y_i)$ です。以下の $Q$ 個のクエリに答えてください：

• $(x_j, y_j)$ ($1 \leq j \leq Q$) からマンハッタン距離が $K_j$ 以下である点の個数を求めてください。

制約

• $1 \leq N \leq 10^6$
• $1 \leq Q \leq 10^6$
• $1 \leq X_i, Y_i, x_j, y_j, K_j \leq 2\times10^3$

入力

入力はすべて自然数であり、以下の $N + Q + 1$ 行から構成されています。

出力

$Q$ 行出力してください。 $j$ ($1 \leq j \leq Q$) 行目には $j$ 番目のクエリに対する答えを出力してください。

サンプル

4 2
2 2
2 4
4 2
4 4
2 3 2
3 3 2

2
4

問題の背景 ～近傍探索とBoids～

はじめまして。KCSの $CG$ 班です。 今回の三田祭では映像作品を展示しています。班の垣根を超えた様々なメンバーの協力のもと創り上げた作品です。ぜひ御覧ください！

ところで「どうしてCG班が競プロの問題を？」と驚かれるかもしれません。その経緯には、実はこの問題に関係したCGのアルゴリズムが関わってくるのです。 問題の解法には直接関係しませんので、競プロに興味がない人でもぜひお読みください！

突然ですが皆さんは「Boids（ボイド）」をご存知でしょうか？ BoidsはCGにおいて生命を再現するためのアルゴリズムの一つです。とりわけ魚や鳥など群れを成す動物の動きを再現することができます。 映画のCGアニメーションにも応用されていることも多いです。幻想的な演出で鳥や魚の群れが自由に踊る――そんなシーンにはだいたいBoidsが関わっています。

こうした胸を打つようなリッチな演出に使われるアルゴリズムですが、実はとても単純な仕組みになっています。 一つ一つのオブジェクトが則るルールはたったの $3$ つだけ！

1. 分離（Separation） オブジェクトが近くのオブジェクトとぶつからないように距離をとる。
2. 整列（Alignment） オブジェクトが近くのオブジェクトと同じ方向に飛ぶように速度と方向を合わせる。
3. 結合（Cohesion） オブジェクトが近くのオブジェクトが集まっている群れの中心方向へ向かうように方向を変える。

たったのこれだけで動物が群れを成してそれっぽく動きます！ こうした簡単なアルゴリズムなので、拡張性も高く、様々な動物の動きに応用できます。

それでは、どうしてこのBoidsが今回の問題に関わるのでしょうか？ それはこれらのルールに注目するとわかります。いずれのルールも「近くのオブジェクト」に影響されるものだからです。 つまり近くのオブジェクトを求める必要があるのです。これを「近傍探索」と言います。それも、ただの近傍探索では不十分です。 ゲームなどのインタラクティブな作品への応用を考えてみましょう。このような場合では30fpsや60fpsといった厳しい条件が求められます。つまり私たちは1/60秒で近くのオブジェクトを求める必要があるのです。 この問題ではそうしたCGの厳しい奥深さの一端を味わってもらうために作成しました。

では、実際の現場ではどのようなアルゴリズムが採用されるのでしょうか？ これはケースバイケースです。それこそオブジェクト中心に距離N以内のオブジェクトを探索するといった条件では、今回の問題のような手法が取られることでしょう。 しかし先述のような厳しい条件ではまだ力不足です。よって、近傍探索の条件を緩めた「格子探索」という手法が主流です。

格子探索ではまず以下のように下準備を行います。

1. まずオブジェクトの存在する領域を格子状に分割します。そして格子ごとに0～Nまで番号(index)を割り振ります。
2. 各オブジェクトが属する格子の番号(index)を求めます。
3. 格子の番号(index)でソート(*)します。
4. 次に長さNの配列を用意します。この配列は、各格子（またはセル）に属するオブジェクトの開始位置を保持するためのものです。具体的には、配列の各要素に、該当する格子に含まれる最初のオブジェクトのインデックスが格納されます。 この上で、近くのオブジェクトを探すときは次のとおりに行います。
5. そのオブジェクトが属する格子のインデックスを求めます。
6. その格子と隣接する格子に属するオブジェクトが「近くのオブジェクト」です。

この格子探索では、ユークリッド距離に依存しないため直感的ではないかもしれません。しかし、こうした格子を用いた近似により、実用上は問題ないレベルで十分高速化することができるのです！

いかがでしたでしょうか？ 競技プログラミングに直接関係しない内容ではありましたが、この説明を聞いて少しでも $CG$ の世界に興味を持っていただければ幸いです！ 以上、KCSの $CG$ 班でした。お読みいただきありがとうございました！

(*) 注釈: ここで用いられるソートはバイトニックソートであることが多いです。 $O(n(\log n)^2)$ ではありますが、GPUの特性により爆速で処理できます。もしGPUでの高速化に興味がありましたら、このバイトニックソートについて調べると面白いかもしれません。