题目描述

有 $n$ 个二元组 $(a_i,b_i)$，编号为 $1$ 到 $n$。

有一个初始为空的栈 $S$，向其中加入元素 $(a_i,b_i)$ 时，先不断弹出栈顶元素直至栈空或栈顶元素 $(a_j,b_j)$ 满足 $a_i\neq a_j$ 且 $b_i

如果一个二元组入栈后栈内只有这一个元素，则称该二元组是“成功的”。

有 $m$ 个询问 $[l_i,r_i]$，表示若将编号在 $[l_i,r_i]$ 中的二元组按编号从小到大依次入栈，会有多少个二元组是“成功的”。

询问之间相互独立。

输入格式

从 stack.in 中输入。

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

第二行 $n$ 个正整数表示 $a_i$。

第三行 $n$ 个正整数表示 $b_i$。

接下来 $m$ 行，每行两个正整数 $l_i,r_i$, 表示一组询问。

输出格式

输出到 stack.out 中。

$m$ 行，每行一个自然数表示一组询问的答案。

样例 1~4

见下发文件中的 stack/stack*.in 和 stack/stack*.ans。

测试点约束

对于所有测试点：$1\leq n,q\leq 5\times 10^5$，$1\leq a_i,b_i\leq n$，$1\leq l_i\leq r_i\leq n$。

大样例