P17666 [IO 2025 #3] 奈弗莫尔学院的事件

奈弗莫尔学院的一条长走廊上站着 $n$ 名居民。可以将这条走廊看作一条数轴。第 $i$ 名居民具有以下属性： - 他在走廊上的坐标 $x_i$； - 他的个人智力值 $m_i$； - 他的团队协作能力 $z_i$； - 一项特殊技巧：他可以暂时降低自己的智力，提高团队协作能力。 具体来说，第 $i$ 名居民还具有两个参数 $c_i$ 和 $a_i$。在任意时刻，他可以不花费时间地将自己当前的智力值改为 $\left\lfloor\dfrac{\text{当前智力值}}{c_i}\right\rfloor$，同时将自己的团队协作能力增加 $a_i$。只要有利，他就可以使用任意多次这一操作。 居民可以在走廊中移动：每单位时间，每名居民都可以沿数轴向 $+1$ 或 $-1$ 方向移动一个单位。 如果若干名居民在某一时刻到达走廊上的同一点，他们就可以组成一个团队。此时： - 团队的智力值等于所有成员的智力值之和； - 团队的协作能力等于所有成员的团队协作能力的最小值。 学院中发生了 $q$ 个互相独立的事件。对于第 $j$ 个事件，已知： - 事件的坐标 $y_j$，即需要集合团队的位置； - 所需智力值 $s_j$； - 所需团队协作能力 $t_j$。 对于每个事件，你需要求出：考虑居民的移动及其特殊技巧，最少经过多长时间，可以在位置 $y_j$ 将现有居民组成一个团队，使团队的总智力值至少为 $s_j$，且团队协作能力至少为 $t_j$。如果无法组成这样的团队，输出 $-1$。

第一行包含两个整数 $n,q$，分别表示居民的数量和事件的数量，满足 $1\le n,q\le 10^5$。 第二行包含 $n$ 个整数 $x_i$，表示居民的坐标，满足 $0\le x_i\le 10^9$。 第三行包含 $n$ 个整数 $m_i$，满足 $0\le m_i\le 10^5$。 第四行包含 $n$ 个整数 $z_i$，满足 $0\le z_i\le 10^5$。 第五行包含 $n$ 个整数 $c_i$，满足 $1\le c_i\le 10^5$。 第六行包含 $n$ 个整数 $a_i$，满足 $1\le a_i\le 10^5$。 接下来 $q$ 行，每行包含三个整数 $y_j,s_j,t_j$，分别表示事件的坐标、所需智力值和所需团队协作能力，满足 $0\le y_j\le 10^9$，$0\le s_j,t_j\le 10^{14}$。

对于每个事件，输出一行一个整数，表示最少经过多长时间，可以在位置 $y_j$ 组成总智力值至少为 $s_j$、团队协作能力至少为 $t_j$ 的团队。如果无法组成，输出 $-1$。