题目描述

Yuzu 最近在实习。由于她摸鱼摸得太多，引起了主管的注意，所以她要美化她的统计数据。

Yuzu 总共实习了 $n$ 天，第 $i$ 天的工作量是 $a_i$。Yuzu 知道主管手上还有一个长为 $n$ 的 01 序列 $\{b_i\}$，如果 $b_i = 1$ 那么第 $i$ 天是一个 关键日期。

Yuzu 知道主管会检查第 $l$ 天到第 $r$ 天之间的工作，所以她需要把 $[a_l,a_{l+1},\ldots,a_r]$ 分成若干个区间，其中每个区间都包含 恰好一个 关键日期。如果一个区间 $[x,y]$ 内的工作量之和非负，即 $a_x+a_{x+1}+\ldots+a_y \ge 0$，那么主管认为 Yuzu 在这个区间内有好好工作。Yuzu 当然希望这样的区间越多越好。

但是 Yuzu 惊动的主管实在是太多了！现在有 $q$ 个主管要来检查她的工作，第 $i$ 个主管检查的区间是 $[l_i,r_i]$。对于每次检查，Yuzu 想知道，她最多可以使多少个区间的总工作量非负。如果 $[l_i,r_i]$ 中没有包含任何一个关键日期，那么输出 $0$。

输入格式

第一行一个正整数 $T$，代表数据组数。接下来 $T$ 组数据，每组数据的格式如下：

• 第一行两个正整数 $n,q$，代表序列长度和查询次数；
• 接下来一行 $n$ 个整数，代表序列 $[a_1,a_2,\ldots,a_n]$；
• 接下来一行 $n$ 个整数，代表序列 $[b_1,b_2,\ldots,b_n]$；
• 接下来 $q$ 行，第 $i$ 行两个整数 $l_i,r_i$，代表第 $i$ 个主管查询的区间。

输出格式

对于每组数据，输出 $q$ 行，每行一个整数，代表该组查询的答案。

1
5 3
-3 2 1 -2 3
1 0 0 0 1
1 5
1 4
2 4

2
0
0

样例解释 1

• 对于第一组询问，Yuzu 可以选择区间 $[1,3],[4,5]$，这样的话两个区间的工作量之和分别为 $0,1$；
• 对于第二组询问，Yuzu 唯一的选择是 $[1,4]$，此时工作量之和为 $-2$，不满足要求；
• 对于第三组询问，区间 $[2,4]$ 中不包含关键日期，所以输出 $0$。

数据范围

• 对于 $30\%$ 的数据，$T \le 5$，$n \le 10^3$，$q = 1$；
• 对于 $60\%$ 的数据，$T \le 5$，$n \le 10^5$，$q = 1$；
• 对于 $100\%$ 的数据：
  • $1 \le T \le 5 \cdot 10^5$，$1 \le n,\sum n \le 5 \cdot 10^5$，$1 \le q,\sum q \le 5 \cdot 10^5$；
  • $|a_i| \le 10^9$，$0 \le b_i \le 1$，$1 \le l_i \le r_i \le n$。