参考：Rectangle Sum

問題文

2 次元平面上に重み付きの点が $N$ 個あります。$i$ 個目の座標は $(x_i, y_i)$ で、重みは $w_i$ です。$Q$ 個のクエリを処理してください。

• $l$ $d$ $r$ $u$：$l \le x \lt r$, $d \le y \lt u$ を満たす点について、重さの総乗を求める。

答えは mod$10^9+7$ で求めてください。ただし、$0$ 個の点の総乗は $1$ です。

制約

• $1 \le N \le 10^5$
• $1 \le Q \le 10^5$
• $0 \le x_i,y_i \lt 10^9$
• $1 \le w_i \le 10^9$
• $0 \le l \lt r \le 10^9$
• $0 \le d \lt u \le 10^9$

入力

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

$i$ 番目のクエリ query$i$ は以下の形式で与えられる。

出力

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

入力例 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