H. 女仆修行

托尔开始了女仆修行！

为了好好服侍小林，托尔想出了 $n$ 种策略（烧尾巴肉、一键打扫等等）。但作为一名资（新）深（手）女仆，她只能选择其中连续的一些策略。

由于身为龙，在服侍的同时托尔必须控制自己的力量：达成第 $i$ 个策略需要 $a_i$ 的力量。托尔力量的变化幅度为所选策略要求的最高力量与最低力量之差。

她可能需要寻求康娜的帮助，但是康娜还要上幼儿园，可能会没有时间。

现在托尔有 $m$ 次询问，她想要知道从第 $q_i$ 个策略开始选择、力量变化幅度不大于 $r_i$、至少受到帮助 $t_i$ 次时，最多能连续达成多少种策略。

第一行有一个正整数 $T(1\le T\le 10)$，表示数据的组数。

对于每组数据，第一行有两个正整数 $n(1\le n\le 10^{5},1\le \sum_{}^{} n\le 4\times 10^{5})$和$m(1\le m\le 10^{5},1\le \sum_{}^{} m\le 4\times 10^{5})$，分别表示策略的数量和查询次数。

第二行有 $n$ 个正整数 $a_i(1\le a_i\le 10^{7})$，表示达成第 $i$ 种策略需要 $a_i$ 的力量。

第三行有 $n$ 个数，每个数为 $0$ 或 $1$，表示康娜在托尔进行策略 $i$ 时能否提供帮助，$0$ 表示不可以，$1$ 表示可以。

接下来 $m$ 行，每行有三个正整数 $q_i(1\le q_i\le n)$、$r_i(1\le r_i\le 10^{7})$、$t_i(0\le t_i\le n)$，分别表示从 $q_i$ 种策略开始选择、托尔力量的最大变化幅度 $r_i$、需要康娜帮忙的次数 $t_i$。

对于每组数据，输出 $m$ 行，每行一个正整数，表示在满足询问条件的前提下最多能连续达成多少种策略。

样例输入

1
10 5
4 9 5 5 8 6 5 9 5 10
0 1 1 1 0 0 0 1 1 0
4 3 1
1 2 2
3 1 1
3 8 1
1 15 1

样例输出

4
0
2
8
10