#P18339. Gold Miner

Gold Miner

Gold Miner

标准输入,标准输出。

Putata 最近迷上了黄金矿工。游戏在一个二维平面上进行,地图中有 nn 块金子,第 ii 块位于 (xi,yi)(x_i,y_i),其中 yi<0y_i<0。

玩家位于地面上的 (p,0)(p,0)。每关的目标是收集 kk 块金子。由于特殊的地质条件,当玩家与一块金子的欧氏距离为 ss 时,拉动它所需的力为 2s2s;收集这块金子消耗的能量,等于将它拉到玩家所在位置所需的功。

对于随距离变化的力,功应沿位移积分。因此,收集距离为 ss 的一块金子所需的功是

∫0s2x dx=s2.\int_0^s2x\,dx=s^2.

Putata 会采取最优策略,在通过关卡的前提下,使总能量消耗最小。

现在 Budada 设计了 qq 个随机关卡。对于第 ii 个关卡,玩家的位置 pp 是从实数区间 [ai,bi][a_i,b_i] 中独立、均匀随机产生的,需要收集的金子数为 kik_i。请计算每个关卡中,最小总能量消耗的期望,对 109+710^9+7 取模。

位置确定后才能选择收集哪些金子;这个最优选择可以随位置 pp 改变。若 ai=bia_i=b_i,玩家的位置就是这个确定的点。

答案可以表示为最简分数 u/vu/v,题目保证 v≢0(mod109+7)v\not\equiv0\pmod{10^9+7}。请输出唯一整数 rr,满足

0≤r<109+7,rv≡u(mod109+7).0\le r<10^9+7,\qquad rv\equiv u\pmod{10^9+7}.

输入格式

第一行包含两个整数 n,qn,q,分别表示金块数和关卡数。

接下来 nn 行,每行包含两个整数 xi,yix_i,y_i,表示第 ii 块金子的位置。

接下来 qq 行,每行包含三个整数 ai,bi,kia_i,b_i,k_i,描述一个随机关卡。

不同金块可以位于同一个坐标,仍然分别计数。第二个样例中就存在这样的金块。

输出格式

输出 qq 行。第 ii 行包含一个整数,表示第 ii 个关卡的答案。

本题输出模数意义下的整数,不输出实数近似值。

数据范围

  • 1≤n≤20001\le n\le2000;
  • 1≤q≤5⋅1051\le q\le5\cdot10^5;
  • 0≤xi≤1090\le x_i\le10^9;
  • −109≤yi<0-10^9\le y_i<0;
  • 0≤ai≤bi≤1090\le a_i\le b_i\le10^9;
  • 1≤ki≤n1\le k_i\le n。

本题只有一组数据,没有测试用例数。

样例输入 1

4 4
1 -2
4 -1
4 -3
5 -2
2 3 1
0 6 4
3 4 2
4 7 2

样例输出 1

333333339
40
666666679
9

样例输入 2

6 10
7 -5
2 -7
2 -7
5 -3
9 -4
5 -3
2 4 1
2 10 2
5 8 3
3 9 1
5 8 5
1 2 4
4 5 3
7 10 6
3 8 3
2 9 2

样例输出 2

333333349
846354201
625000051
406250015
143
333333477
50
273
575000054
443452410

样例说明

第一个样例的四个期望分别为

103,40,233,9.\frac{10}{3},\quad40,\quad\frac{23}{3},\quad9.