Equilibrium
Contest: Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2)
Difficulty rating: 2200
Tags: data structures, dp, greedy

William has two arrays $$$a$$$ and $$$b$$$, each consisting of $$$n$$$ items.

For some segments $$$l..r$$$ of these arrays William wants to know if it is possible to equalize the values of items in these segments using a balancing operation. Formally, the values are equalized if for each $$$i$$$ from $$$l$$$ to $$$r$$$ holds $$$a_i = b_i$$$.

To perform a balancing operation an even number of indices must be selected, such that $$$l \le pos_1 < pos_2 < \dots < pos_k \le r$$$. Next the items of array a at positions $$$pos_1, pos_3, pos_5, \dots$$$ get incremented by one and the items of array b at positions $$$pos_2, pos_4, pos_6, \dots$$$ get incremented by one.

William wants to find out if it is possible to equalize the values of elements in two arrays for each segment using some number of balancing operations, and what is the minimal number of operations required for that. Note that for each segment the operations are performed independently.

Input format:
The first line contains a two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le q \le 10^5$$$), the size of arrays $$$a$$$ and $$$b$$$ and the number of segments.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(0 \le a_i \le 10^9)$$$.

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ $$$(0 \le b_i \le 10^9)$$$.

Each of the next $$$q$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ $$$(1 \le l_i < r_i \le n)$$$, the edges of segments.

Output format:
For each segment output a single number — the minimal number of balancing operations needed or "-1" if it is impossible to equalize segments of arrays.

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

Note:
For the first segment from $$$2$$$ to $$$6$$$ you can do one operation with $$$pos = [2, 3, 5, 6]$$$, after this operation the arrays will be: $$$a = [0, 2, 2, 9, 4, 2, 7, 5]$$$, $$$b = [2, 2, 2, 9, 4, 2, 5, 8]$$$. Arrays are equal on a segment from $$$2$$$ to $$$6$$$ after this operation.

For the second segment from $$$1$$$ to $$$7$$$ you can do three following operations:

1. $$$pos = [1, 3, 5, 6]$$$
2. $$$pos = [1, 7]$$$
3. $$$pos = [2, 7]$$$

After these operations, the arrays will be: $$$a = [2, 2, 2, 9, 4, 2, 7, 5]$$$, $$$b = [2, 2, 2, 9, 4, 2, 7, 8]$$$. Arrays are equal on a segment from $$$1$$$ to $$$7$$$ after these operations.

For the third segment from $$$2$$$ to $$$4$$$ you can do one operation with $$$pos = [2, 3]$$$, after the operation arrays will be: $$$a = [0, 2, 2, 9, 3, 2, 7, 5]$$$, $$$b = [2, 2, 2, 9, 4, 1, 5, 8]$$$. Arrays are equal on a segment from $$$2$$$ to $$$4$$$ after this operation.

It is impossible to equalize the fourth and the fifth segment.

Example input:
8 5
0 1 2 9 3 2 7 5
2 2 1 9 4 1 5 8
2 6
1 7
2 4
7 8
5 8

Example output:
1
3
1
-1
-1

Editorial:
The first step to solving this problem is to create some array $$$C$$$, where $$$c_i = a_i - b_i$$$. Then we can select some elements from this array C and do operations $$$+1, -1, +1, -1 \dots$$$ for these elements for the corresponding elements. And the challenge is to make this array consist of zeros.
It is argued that this can always be done if the following conditions are met: 1. no prefix with positive-sum and no suffix with negative 2. the sum of all elements is zero
Let us prove the sufficiency of these conditions: we can find the smallest prefix with a negative sum and the smallest suffix with a positive one, do the operation with one $$$+1$$$ and one $$$-1$$$, and reduce the sum of the absolute values ​​of the elements.
Assertion: the minimum number of operations is the maximum modulus of the sum on the subsegment. This is a lower estimate, since on any segment, the sum changes by at most 1. Let us prove the upper bound by presenting a constructive solution. Let now the array of differences $$$c_1, c_2, \dots, c_n$$$, and the maximum modulus of the sum is $$$M$$$.
Let's do the following: find the first negative number, there is $$$+1$$$, the first positive number after it, there is $$$-1$$$, and so on. Statement: the last operation will be $$$-1$$$, because otherwise, our last nonzero number is negative, which means it is a negative prefix.
We can reformulate greed as follows: throw out all zeros, put $$$+1$$$ in the first element for each negative segment, and $$$-1$$$ for each positive one in the first element. Let us prove that on any subsegment with the sum $$$M$$$, it has decreased in absolute value. Without loss of generality, consider the segment $$$[l, r]$$$ with a positive-sum [the prefix corresponds to the suffix].
Consider again the array obtained by throwing out zeros. It is clear that our segment $$$[l, r]$$$ did not cut any segment of negative/positive ones, otherwise, it has no maximum sum. It is also clear that the first and last segments in $$$[l, r]$$$ are positive, so we have bet $$$-1$$$ more than $$$+1$$$.