冬木市政府想要对城里的主干道进行改造。这次改造的目标是使得所有路口的车辆等候红绿灯队伍的长度不超过一个目标数值。

你是新上任的冬木市交通规划局局长，现在你想知道，至少要将道路扩建到几车道才能达成目标？

你所能得知的信息是一个路口红绿灯的红灯持续时间，以及每单位时间内会来到路口的车辆数。每辆车来到路口时会优先选择车辆最少的车道，而一个路口的等候队伍长度等于所有车道车辆个数的最大值。车辆会在红灯结束后的第$p_i$单位时间开始驶出路口。对于不同的车道数，由于拥挤程度不同，在红灯结束时车辆的启动延迟时间$p_i$也不同，随着车道数上升，路口变得宽敞，$p_i$会逐渐下降。绿灯时间足够让所有车辆开出。

由于主干道上有多个路口，你需要得到每个路口的答案。假设一开始时所有路口都没有车辆。

第一行为2个整数$t,n(1 \le t \le 10^5,1 \le n \le 10^5)$，分别表示主干道的路口数和可以建造的最高车道数。

接下来一行$n$个整数$p_1,p_2,...,p_n(1 \le p_i \le 10^8)$，$p_i$表示车道数为$i$时的启动延迟时间。保证该序列单调非上升。

然后是$t$行，每行为3个整数$t_r,a,x(1 \le t_r,a,x \le 10^8)$，分别表示该路口的红灯持续时间，单位时间内到达路口的车辆数和红绿灯等候队伍长度上限。

$t$个整数，表示每个路口至少要扩建为多少车道。如果扩建到n车道也无法满足需求，则输出-1。

需要注意的是启动延迟时间内仍有车辆到来。

对于第一个路口，只有一车道的话红灯时间+延迟时间共计11单位时间，会来11辆车，超过了5的限制。使用两车道的话红灯时间+延迟时间共计10单位时间，会来10辆车，分到两个车道每边5辆，刚好符合需求。

对于第二个路口，即使开二车道也无法满足条件。