Colin is a huge fan of the Kingdom Rush franchise tower defense games. In the latest generation of Kingdom Rush: Vengeance, Colin's favorite tower is the rotten forest, which can continuously inflict damage to all enemies within its control range.

Colin liked this convenient AOE(area-of-effect) damage tower so much that he decided to only use the rotten forest in the game! In order to practice the strategy of arranging towers, Colin modeled the game content and conducted several numerical experiments.

To simplify the problem, Colin assumes that the path of the map is a number axis. Enemies will be generated from some points and move in the positive direction of the number axis at a constant speed of $$$1$$$ unit per second. There are $$$n$$$ rotten forest towers along the path, where the $$$i$$$-th tower controls the range $$$[L_i,R_i]$$$ and will inflict $$$w_i$$$ damage to each enemy within its control range at the end of each second. Note that the ranges controlled by different towers may overlap. In this case, the damage received by enemies in the overlapping area per second is the sum of the damage of all towers controlling this area. For example, assume that there is a tower that controls the range $$$[3,4]$$$ and another tower controls the range $$$[4,5]$$$. If an enemy is generated at the point $$$0.5$$$ at time $$$t=0.5s$$$, then it will receive the damage at the end of the third, fourth, and fifth seconds; and at the end of the fourth second, it will receive the damage from both towers.

In this battle $$$m$$$ enemies are generated at $$$t=0.5s$$$, and the $$$i$$$-th one is generated at the point $$$x_i+0.5$$$ with health $$$h_i$$$. Once the total damage received by an enemy is greater or equal to its health, it will die immediately. Colin wants to know the exact death time of each enemy, or if the existing towers are not enough to kill this enemy.