题目描述

奈弗莫尔学院的一条长走廊上站着 $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$。

4 6
0 10 5 7
10 6 4 3
1 5 2 4
2 2 2 3
3 1 2 1
5 12 4
0 6 6
10 7 4
5 25 3
5 15 5
7 5 4

5
10
3
-1
-1
2