Cân bằng (Equilibrium)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Cho hai mảng $A$ và $B$, mỗi mảng có $N$ phần tử. Với mỗi truy vấn đoạn $[l,r]$, các thao tác chỉ được thực hiện độc lập trong đoạn đó.

Một thao tác cân bằng chọn một số chẵn vị trí:

Sau đó tăng $A_{p_1},A_{p_3},A_{p_5},\ldots$ thêm $1$ và tăng $B_{p_2},B_{p_4},B_{p_6},\ldots$ thêm $1$.

Hãy tìm số thao tác nhỏ nhất để làm $A_i=B_i$ với mọi $i\in[l,r]$, hoặc in $-1$ nếu không thể.

Input

Dòng đầu chứa $N,Q$.

Dòng thứ hai chứa $A_1,\ldots,A_N$.

Dòng thứ ba chứa $B_1,\ldots,B_N$.

$Q$ dòng tiếp theo, mỗi dòng chứa $l,r$ với $l<r$.

Output

Với mỗi truy vấn, in số thao tác nhỏ nhất hoặc $-1$ nếu không thể.

Subtask

• 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$.

Ví dụ

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

Giải thích

Ba truy vấn đầu có thể cân bằng với số thao tác tối thiểu lần lượt $1,3,1$; hai truy vấn cuối vi phạm điều kiện cần nên kết quả là $-1$.