参考:Rectangle Sum

問題文

2 次元平面上に重み付きの点が NN 個あります。ii 個目の座標は (xi,yi)(x_i, y_i) で、重みは wiw_i です。QQ 個のクエリを処理してください。

  • ll dd rr uulx<rl \le x \lt r, dy<ud \le y \lt u を満たす点について、重さの総乗を求める。

答えは mod109+710^9+7 で求めてください。ただし、00 個の点の総乗は 11 です。

制約

  • 1N1051 \le N \le 10^5
  • 1Q1051 \le Q \le 10^5
  • 0xi,yi<1090 \le x_i,y_i \lt 10^9
  • 1wi1091 \le w_i \le 10^9
  • 0l<r1090 \le l \lt r \le 10^9
  • 0d<u1090 \le d \lt u \le 10^9

入力

入力は以下の形式で標準入力から与えられる。

NN QQ
x0x_0 y0y_0 w0w_0
x1x_1 y1y_1 w1w_1
\vdots
xN1x_{N-1} yN1y_{N-1} wN1w_{N-1}
query00
query11
\vdots
queryQ1Q-1

ii 番目のクエリ queryii は以下の形式で与えられる。

ll dd rr uu

出力

QQ 行出力せよ。ii 行目には ii 個目のクエリに対する答えを出力せよ。

入力例 1

5 5
0 0 2
0 3 3
1 2 5
1 4 7
3 1 11
0 0 5 5
0 0 5 4
0 2 5 5
1 1 3 5
1 0 3 2

出力例 1

2320
330
105
35
1

入力例 2

2 1
0 0 100000
0 0 100001
0 0 1 1

出力例 2

99930

Submit


Go (1.21)