背景

瑛太把刚才拍的樱花树的照片发了上去。写到“大学很普通”。

——看起来就是这样的感觉啊。这是来自她的回答，很疑惑，“看什么”，这到底是怎么回事。

然后 line 画面上发来一张照片。像是在哪里见过的景色，在散落了一半的樱花树下有一个驼背男大学生的后背。瑛太的背包，瑛太的衣服，照片里的是瑛太本人。

怀着惊讶和确信的心情，慢慢地回头看。她在后面，十步左右的距离，恶作剧似地笑着。

“我并不是为了追求泉来这的，是因为这里的教育系比较有名。” 她开心地告诉了我不知道的事情，有很多想说的话。

我有很多想说的话，想听的事情也很多。但在她面前，瑛太想要传达的就只剩下，那天没有说出口的话，那天最想传达的想法...

“夏目，我喜欢你。”

在林荫大道上刮起大风，稍强的风把樱花吹得飘落下来，落在两人身上。

“我也是，泉。”

在樱吹雪的风中，她害羞地笑了起来。

题目描述

你有 $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$ 行，每行一个整数表示每个询问的答案。

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

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

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$。