seuOJ166 - 女仆修行

题目类型：传统
输入文件：标准输入流
输出文件：标准输出流
时间限制：5000 ms
空间限制：256 MiB
题目标签：春季, 校赛, 2019

题目描述

托尔开始了女仆修行！

为了好好服侍小林，托尔想出了 $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

样例输出