Equilibrium

Source: Codeforces

Version: Phuoc Hung OJ Extended

You are given two arrays $A$ and $B$ of length $N$. Each query segment $[l,r]$ is processed independently.

One balancing operation selects an even number of positions:

Then $A_{p_1},A_{p_3},A_{p_5},\ldots$ are increased by $1$, while $B_{p_2},B_{p_4},B_{p_6},\ldots$ are increased by $1$.

For each query, find the minimum number of operations needed to make $A_i=B_i$ for all $i\in[l,r]$, or print $-1$ if it is impossible.

Input

The first line contains $N,Q$.

The second line contains $A_1,\ldots,A_N$.

The third line contains $B_1,\ldots,B_N$.

Each of the next $Q$ lines contains $l,r$ with $l<r$.

Output

For every query, print the minimum number of operations, or $-1$ if impossible.

Subtasks

• Subtask 1 — 20%: $2\le N\le 50$, $1\le Q\le 50$, $0\le A_i,B_i\le 1000$.
• Subtask 2 — 30%: $2\le N\le 5000$, $1\le Q\le 5000$, $0\le A_i,B_i\le 10^9$.
• Subtask 3 — 50%: $2\le N,Q\le 10^5$, $0\le A_i,B_i\le 10^9$.

Examples

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

Output

1
3
1
-1
-1

Explanation

The sample follows the operations exactly; each printed line corresponds to a query that requires output.