AT_past202004_n ビルの建設

[problemUrl]: https://atcoder.jp/contests/past202004-open/tasks/past202004_n $ 2 $ 次元平面上に、各辺が x, y 軸に並行な正方形の敷地が $ N $ 個あり、$ i $ 個目の敷地の範囲は領域 $ xmin_i\ \leq\ x\ \leq\ xmin_i\ +\ D_i,\ ymin_i\ \leq\ y\ \leq\ ymin_i\ +\ D_i $ です。各敷地にはコストが定まっており、$ i $ 番目の敷地のコストは $ C_i $ です。 今、$ Q $ 件のビル建設計画があり、$ j $ 件目の計画での建設予定地点の座標は $ (A_j,\ B_j) $ です。 各計画のコストは、その計画の建設座標を含む (または境界線上に持つ) すべての敷地のコストの和です。 各計画のコストを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ xmin_1 $ $ ymin_1 $ $ D_1 $ $ C_1 $ $ xmin_2 $ $ ymin_2 $ $ D_2 $ $ C_2 $ $ : $ $ xmin_N $ $ ymin_N $ $ D_N $ $ C_N $ $ A_1 $ $ B_1 $ $ : $ $ A_Q $ $ B_Q $

$ Q $ 行出力せよ。$ j $ 行目に $ j $ 件目の計画のコストを出力すること。

### 注意 この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 1\ \leq\ N\ \leq\ 50000 $ - $ 1\ \leq\ Q\ \leq\ 100000 $ - $ -10^9\ \leq\ xmin_i,\ ymin_i\ \leq\ 10^9 $ - $ 1\ \leq\ D_i\ \leq\ 10^9 $ - $ 0\ \leq\ C_i\ \leq\ 10^9 $ - $ -10^9\ \leq\ A_i,\ B_i\ \leq\ 10^9 $ - 入力は全て整数 ### Sample Explanation 1 \- $ 1 $ 件目の計画の座標は、$ 1,\ 2 $ 個目の敷地に含まれるので、$ 10\ +\ 20\ =\ 30 $ を出力してください。 - $ 2 $ 件目の計画の座標は、どちらの敷地にも含まれないので、$ 0 $ を出力してください。 - $ 3 $ 件目の計画の座標は、$ 1 $ 個目の敷地に含まれるので、$ 10 $ を出力してください。 - $ 4 $ 件目の計画の座標は、どちらの敷地にも含まれないので、$ 0 $ を出力してください。 ### Sample Explanation 2 \- $ 1 $ 件目の計画の座標は、$ 1,\ 2 $ 個目の敷地に含まれるので、$ 100\ +\ 30\ =\ 130 $ を出力してください。 - $ 2 $ 件目の計画の座標は、$ 1 $ 個目の敷地に含まれるので、$ 100 $ を出力してください。 - $ 3 $ 件目の計画の座標は、$ 2 $ 個目の敷地に含まれるので、$ 30 $ を出力してください。