P12978 流星雨 Meteor

> 星の流れる夜に 星光流动的夜裡\ 北風が通りを吹き抜け 北风穿越过街道\ 待ち人から便りはなく 所盼之人音讯全无\ 明くる日を描くだけ 单单描画翌日之像\ 星は願いを乗せて 繁星承载祈愿\ あの空を静かに散り行き 宁静漫步夜空\ ——じょん / 初音ミク《メテオ》 题外话：现在你看到的是这个题目修改后的版本，其初始版本不太可做（各种方面），有兴趣的可以看看原先出的 [二维版本](https://www.luogu.com.cn/paste/2074cza5)。

现在你坐在观星台的监视屏幕前，这是一个 $n\times n$ 的屏幕，这个屏幕的信号转换算法相当老旧，所以不在整像素点上的流星将被暂时忽略直到它出现在整点上。正是流星雨爆发的时候，你调整屏幕使得流星雨像是瀑布一样向正下飞去。 恰好共有 $n$ 颗流星。为了方便，我们给流星依次标号，并以左下角为原点，将屏幕看作平面直角坐标系的第一象限。对第 $i$ 颗流星，有一个一开始能够被监测到的起点，$(x_i,y_i)$（是整点，此时是第 $0$ 时刻）；也有一个平行于 $y$ 轴且向下做匀速直线运动的速度，用 $(v_i,t_i)$ 表示每 $t_i$ 秒运动 $v_i$ 个像素。**此外，我们保证 $x_i=i$**。同时每个流星还有一个权值 $a_i$ 表示它的神秘学参数。 繁星承载着祈愿，但同时彗星在古代被称作灾难的象征，为了提前预知，你找来了魔法师来占卜。你为他锁定了 $Q$ 次观星台的镜头，找出可能的灾厄。镜头拍出的画面是一个会调整大小的矩形。为了让他提前准备，你需要确定他至少要对屏幕上的流星施法几次，这和流星的神秘学参数相关，也就是： - 在某一时刻 $T_j$，确定当前纵坐标在某个区间内，且落在整点上的流星的权值 $a_i$ 的和； 由于法师过来还需要一会儿，所以允许你把问题离线。

第一行两个整数 $n,Q$，分别表示流星数量（同时也是屏幕尺寸），和询问次数。 第二行到第 $n+1$ 行，每行四个整数 $y_i,v_i,t_i,a_i$ 表示流星的起始坐标、速度，以及神秘学参数。 接下来 $Q$ 行，每行三个整数 $(T_j,l_j,r_j)$ 表示询问时刻 $T_j$ 时纵坐标在 $[l_j,r_j]$ 内的流星的神秘学权值和。 悬赏：如果有人能发现区间询问的非常好的做法，请告知出题人。（即查询编号在某个区间内的答案）

一共 $Q$ 行，每行一个非负整数，表示询问的答案。

以下是数据范围。 | Subtask | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | | $1$ | $n,Q\leq 5000$ | $10$ | | $2$ | 均匀随机生成 $t_i$ | $20$ | | $3$ | 保证 $T_j$ 均匀随机生成，$a_i=1$ | $25$ | | $4$ | 无特殊性质；依赖前三个子任务 | $45$ | 对于所有的数据，保证 $n\leq 10^5,Q\leq3\times 10^5 $，且 $0\leq v_i