题目描述

给出 $n$ 个二元组 $(x_i,y_i)$，你需要回答 $q$ 个询问，每个询问给出闭区间 $[l,r]$，请回答满足以下条件的整数 $j$ 数量：

• $l\leq j\leq r$；

• 不存在 $l\leq k\leq r, k\neq j$，使得 $x_k\geq x_j$ 且 $y_k\geq y_j$。

输入格式

第一行两个正整数 $n,q$（$1\leq n,q\leq 10^6$），分别表示二元组数量和询问数量。

第二行 $n$ 个非负整数 $x_1,x_2,\dots,x_n$（$0\le x_i\le 10^6$）。

第三行 $n$ 个非负整数 $y_1,y_2,\dots,y_n$（$0\le y_i\le 10^6$）。

接下来 $q$ 行，每行两个正整数 $l,r$（$1\leq l\leq r\leq n$），表示询问的区间。

输出格式

对于每个询问，输出一行一个整数表示答案。

8 7
1 9 7 8 0 7 2 3
19 20 5 6 1 14 9 5
1 8
3 7
2 6
4 4
5 7
3 8
6 7

1
2
1
1
1
2
1

提示

对于询问 $1$，满足条件的整数为 $2$。

对于询问 $2$，满足条件的整数为 $4$、$6$。

对于询问 $3$，满足条件的整数为 $2$。

对于询问 $4$，满足条件的整数为 $4$。

对于询问 $5$，满足条件的整数为 $6$。

对于询问 $6$，满足条件的整数为 $4$、$6$。

对于询问 $7$，满足条件的整数为 $6$。