题目描述

你有 $n$ 棵树，第 $i$ 棵树位于位置 $p_i$，高度为 $h_i$，保证 $p$ 单调递增。

给定 $q$ 次询问。对于第 $i$ 次询问，只保留 $[l_i,r_i]$ 子区间，你要选择最多的树，使得存在一种砍倒方式使得每棵树都不碰到另一棵树的树桩。

形式化地，设 $S = \{s_1, s_2, \dots, s_k\} \subseteq \{l_i, l_i+1, \dots, r_i\}$ 且 $s_1 < s_2 < \cdots < s_k$。

要求对任意 $1 < j < k$，都有 $p_{s_j} + h_{s_j} < p_{s_{j+1}} \lor p_{s_j} - h_{s_j} > p_{s_{j-1}}$。求 $\max k$。

询问之间互相独立。

输入格式

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

第二行一个长度为 $n$ 的严格递增正整数序列 $p_i$。

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

接下来 $q$ 行，每行两个正整数 $l_i,r_i$ 表示询问的区间。

输出格式

共 $q$ 行，每行一个整数表示每个询问的答案。

输入输出样例 #1

输入 #1

5 3
3 5 8 9 10 
2 7 5 9 9 
4 5
1 5
1 4

输出 #1

2
2
2

输入输出样例 #2

输入 #2

17 16
7 8 15 20 24 27 30 37 40 44 48 52 56 60 64 68 72 
5 1 1 4 1 2 1 2 3 2 2 5 7 4 7 6 7 
2 12
10 12
4 14
4 8
3 3
3 16
3 13
1 16
3 15
15 16
1 15
3 16
2 14
5 16
4 17
4 14

输出 #2

11
3
10
5
1
12
10
14
12
2
14
12
12
10
12
10

说明/提示

【数据范围】

本题使用子任务捆绑。

对于所有测试数据，$1\le n,q \le 5\times 10^5$，$1\le p_i,h_i \le 10^9$，$l_i\le r_i$。对于所有 $1\le i< n$，保证 $p_i < p_{i+1}$。

特殊性质：对于所有 $1\le i\le q$，保证 $l_i=1$。