You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小Y是《王国保卫战》系列塔防游戏的忠实粉丝。在新一代的《王国保卫战：复仇》中，小Y 最喜欢的塔是腐烂森林，它可以不断对其控制范围内的所有敌人造成伤害。

小Y非常喜欢这个有AOE效果（范围群体伤害）的防御塔，于是他决定在游戏中只使用腐烂森林！为了实践排列防御塔的策略，小Y对游戏内容进行了建模，并进行了多次数值实验。

为了简化问题，小Y 假设路径是一个数轴。敌人将从某些点生成，并以 $1$ 单位距离每秒的恒定速度沿数轴的正方向移动。

路径沿途有 $n$ 个腐烂森林塔，其中第 $i$ 个塔的控制范围为 $[L_i，R_i]$ ，并将在每整数秒结束时对其控制范围内的 每个敌人造成 $w_i$ 的伤害。注意不同塔控制的范围可能会重叠。在重叠的情况下，重叠区域内敌人每秒受到的伤害是控制该区域的所有塔楼的伤害之和（即伤害是累加的）。

例如，假设有一个塔控制范围 $[3,4]$ ，另一个塔控制范围 $[4,5]$ 。如果敌人在时间 $t=0.5$ 秒时在坐标 $0.5$ 处生成，则它将在第三、第四和第五秒结束时受到伤害；特殊的，在第四秒结束时，它将受到来自两座防御的伤害。

在这场战斗中，在 $t=0.5s$ 时生成了 $m$ 个敌人，其中在 $x_i+0.5$ 的坐标处生成了第 $i$ 个敌人，其生命值为 $h_i$ 。一旦某个敌人受到的总伤害大于或等于其生命值，它将立即死亡。小Y想知道每个敌人的确切死亡时间，或者报告现有的塔楼不足以杀死这个敌人。

输入格式

从 kingdomrush.in 文件读入数据。

第一行包括两个整数 $n, m$，表示塔的数量和敌人数量。

接下来 $n$ 行，第 $i$ 行包含三个整数 $l_i, r_i, w_i$ ，表示第 $i$ 个塔的控制范围和其一秒能造成的伤害。

接下来 $m$ 行，每行包含两个整数 $x_i,h_i$，表示第 $i$ 个敌人在 $x_i+0.5$ 处产生，初始生命值为 $h_i$ 。

输出格式

输出到 kingdomrush.out 文件。

输出 $m$ 行，第 $i$ 行包含一个整数，表示第 $i$ 个敌人的死亡时间。如果无法击杀它则输出-1。

样例 1

6 6
1 3 1
2 4 1
3 5 1
4 6 1
5 7 1
6 8 1
0 15
0 17
1 3
1 15
5 7
6 2

6
7
2
6
-1
1

样例 2

点击链接 ex_kingdomrush2.in 和 ex_kingdomrush2.out 下载大样例 2 的输入数据和输出数据。

数据范围

对于每个测试点， 保证 $1\le n,m\le 10^5, 1\le l_i\le r_i\le 10^9, 1\le w_i\le 10^4,0\le x_i\le 10^9,1\le h_i\le 10^{18}$