题目背景

小 Z 生活的学校就像是一条链，直径很长，宽度很窄。

具体来说，这里有一个长度为 $n$ 的序列，每个位置有一个属性 $a_i\in \{0/1\}$ 和一个类型 $c_i$，在这里有一些贸易事件会发生。

小 Z 从左往右通过这个序列，若当前遇到一个 $0$ 属性的节点，则小 Z 可以购入至多一个 $c_i$ 类型的物品，若当前遇到一个 $1$ 属性的节点，则小 Z 可以卖出至多一个 $c_i$ 类型的物品，显然，在小 Z 没有这种类型的物品时是不能卖出的。

一次合法的交易定义为从某个节点买入，并在某个节点卖出，注意，你需要保证在最后小 Z 手里不存在任何东西。

给出 $q$ 次询问，每次小 Z 从 $l_i$ 顺序走到 $r_i$，问：最大合法交易次数是多少

$q$ 次询问，每次给定一个区间，顺序枚举区间元素，遇到属性为 $0$ 就购入一个该颜色的物品，遇到 $1$ 就卖出这个颜色的物品，权值定义为成功卖出的次数（当前购入 - 卖出 $\ge 1$ 时可以成功卖出）。

输入格式

从标准输入读入数据。

第一行两个正整数 $n,q$。

接下来一行 $n$ 个数，第 $i$ 个表示 $a_i$。

接下来一行 $n$ 个数，第 $i$ 个表示 $c_i$。

接下来 $q$ 行，每行两个数表示 $l_i,r_i$。

输出格式

输出到标准输出。

输出共 $q$ 行，每行一个数表示当前这个询问中的最大合法交易次数。

样例

输入

10 5
1 1 0 0 0 0 0 1 1 1 
1 1 1 1 1 1 1 1 1 1 
4 6
2 4
2 6
7 10
4 7

输出

0
0
0
1
0

解释

子任务

对于所有数据，满足 $1\le n,q\le5\times 10^5,1\le c_i\le n,1\le l_i\le r_i\le n,a_i\in\{0,1\}$。

提示

请注意输入输出效率。