Problem Description

You are given $n$ trees. The $i$-th tree is located at position $p_i$ and has height $h_i$. It is guaranteed that the sequence $p$ is strictly increasing.

There are $q$ queries. For the $i$-th query, only the subarray $[l_i, r_i]$ is kept. You need to choose as many trees as possible such that there exists a way to cut them down so that no tree trunk hits another trunk.

Formally, let $S=\{s_1,s_2,\dots,s_k\}\subseteq\{l_i,l_i+1,\dots,r_i\}$ with $s_1<s_2<\cdots<s_k$.

The requirement is that for every $1<j<k$, we have $p_{s_j}+h_{s_j}<p_{s_{j+1}} \lor p_{s_j}-h_{s_j}>p_{s_{j-1}}.$

Find the maximum possible value of $k$.

Note that you don't actually cut any trees, and when you compute the answer, the trees' positions and heights remain unchanged.

Input Format

The first line contains two positive integers $n,q$.

The second line contains $n$ positive integers, denoting $h_i$.

The third line contains a strictly increasing sequence of $n$ positive integers $p_i$.

The next $q$ lines each contain two positive integers $l_i,r_i$, describing the query interval.

Output Format

Output $q$ lines. Each line should contain one integer, the answer for the corresponding query.

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

Hint

Constraints

For all test cases, $1\le n,q\le 5\times 10^5$, $1\le p_i,h_i\le 10^9$, and $l_i\le r_i$. For all $1\le i<n$, it is guaranteed that $p_i<p_{i+1}$.

• Special property: For all $1\le i\le q$, it is guaranteed that $l_i=1$.