Observation Towers
Contest: Kotlin Heroes: Episode 10
Difficulty rating: 2400
Tags: *special

Consider a segment of an OX axis from $$$1$$$ to $$$n$$$. There are $$$k$$$ observation towers on this segment.

Each tower has two parameters — the coordinate $$$x_i$$$ and the height $$$h_i$$$. The coordinates of all towers are distinct. From tower $$$i$$$, you can see point $$$j$$$ if $$$|x_i - j| \le h_i$$$ (where $$$|a|$$$ is an absolute value of $$$a$$$).

You can increase the height of any tower by $$$1$$$ for one coin. The height of each tower can be increased any number of times (including zero).

You need to process $$$q$$$ independent queries. In the $$$i$$$-th query, two different points $$$l$$$ and $$$r$$$ are given. You need to calculate the minimum number of coins required to be able to see both of these points (from one tower or from different towers).

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le n$$$) — the length of the segment of an OX axis and the number of observation towers.

The second line contains $$$k$$$ integers $$$x_1, x_2, \dots, x_k$$$ ($$$1 \le x_i \le n$$$) — the coordinates of the observation towers. The coordinates of all towers are distinct.

The third line contains $$$k$$$ integers $$$h_1, h_2, \dots, h_k$$$ ($$$0 \le h_i \le n$$$) — the heights of the observation towers.

The fourth line contains a single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le n$$$) — the description of the next query.

Output format:
For each query, output a single integer — the minimum number of coins required to be able to see both points (from one tower or from different towers).

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
20 3
2 15 10
6 2 0
3
1 20
10 11
3 4

Example output:
3 1 0

Example input:
10 2
2 9
1 2
3
4 5
5 6
1 10

Example output:
2 2 0

Editorial:
Let's start with a simple case: the points are visible from different towers. That is, for each point, we need to find a tower to increase as little as possible, and add the two answers together.
Let's solve for point $$$l$$$. There are three possibilities here. The point is already covered by some tower, there is a tower to the left of the point, and there is a tower to the right of the point.
Let's start with the case to the left. Which points are visible from the towers to the left? We don't care about the left boundaries, and the right boundaries are equal to $$$x_i + h_i$$$ for all such $$$i$$$ that $$$x_i < l$$$. If we increase the height by $$$k$$$, it will be $$$x_i + h_i + k$$$. So, we need to find the tower with the greatest value of $$$x_i + h_i$$$. Then the answer will be $$$l - (x_i + h_i)$$$. You can notice that if $$$x_i + h_i \ge l$$$, then we can take the maximum with $$$0$$$ in the formula, and the first case will disappear by itself. For the tower to the right, the situation is symmetric: we need to find the tower with the smallest value of $$$x_i - h_i$$$, and the answer will be $$$\max(0, (x_i - h_i) - l)$$$.
Thus, we can build prefix maximums based on the values of $$$x_i + h_i$$$ at position $$$x_i$$$ and suffix minimums based on the values of $$$x_i - h_i$$$ at position $$$x_i$$$ and make queries in $$$O(1)$$$.
Now the case where both points are covered by the same tower. Again, we will divide the problem into two cases. Either we will first see point $$$l$$$ from the tower, and then $$$r$$$, or vice versa. Where should the tower be for each case? Obviously, in the first case it is closer to $$$l$$$, and in the second case it is closer to $$$r$$$. That is, if $$$x_i \le \frac{l + r}{2}$$$ (formula without rounding), then the first case, otherwise the second.
It turns out that we have now reduced the problem to the case with independent towers. In the first case, we need to find a tower on the prefix up to the middle between $$$l$$$ and $$$r$$$, from which $$$r$$$ will be visible as soon as possible — maximum by $$$x_i + h_i$$$. In the second case — a tower on the suffix from the middle between $$$l$$$ and $$$r$$$, from which $$$l$$$ will be visible as soon as possible — minimum by $$$x_i - h_i$$$. That is, we can use the same prefix and suffix arrays.
Overall complexity: $$$O(n + q)$$$.