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-----

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-----

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.


-----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


-----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:

$pos = [1, 3, 5, 6]$

$pos = [1, 7]$

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

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Data structures

Greedy algorithms


Solutions:
import sys
input = sys.stdin.readline

class SegTree:

	def __init__(self, n, e, ope, lst=[]):
		self.N0 = 2 ** (n - 1).bit_length()
		self.e = e
		self.ope = ope
		self.data = [e] * (2 * self.N0)
		if lst:
			for i in range(n):
				self.data[self.N0 + i] = lst[i]
			for i in range(self.N0 - 1, 0, -1):
				self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1])

	def f5(self):
		for i in range(self.N0 - 1, 0, -1):
			self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1])

	def update(self, i, x):
		i += self.N0
		self.data[i] = x
		while i > 1:
			i >>= 1
			self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1])

	def add(self, i, x):
		self.update(i, x + self.get(i))

	def query(self, l, r):
		if r <= l:
			return self.e
		res = self.e
		l += self.N0
		r += self.N0
		while l < r:
			if l & 1:
				res = self.ope(res, self.data[l])
				l += 1
			if r & 1:
				r -= 1
				res = self.ope(res, self.data[r])
			l >>= 1
			r >>= 1
		return res

	def get(self, i):
		return self.data[self.N0 + i]

def ope(x, y):
	if x >= y:
		return x
	else:
		return y

def ope2(x, y):
	if x <= y:
		return x
	else:
		return y

def main():
	(n, q) = map(int, input().split())
	alst = list(map(int, input().split()))
	blst = list(map(int, input().split()))
	cum = [0]
	pos = 0
	i_p = [-1] * n
	bef = alst[0] >= blst[0]
	seg = SegTree(n, 0, ope)
	inf = 10 ** 15
	seg_min = SegTree(n + 1, inf, ope2)
	seg_max = SegTree(n + 1, -inf, ope)
	i_p_min = [0] * n
	i_p_max = [0] * n
	tot = 0
	seg_min.data[seg_min.N0] = 0
	seg_max.data[seg_min.N0] = 0
	for (i, (a, b)) in enumerate(zip(alst, blst)):
		cum.append(cum[-1] + a - b)
		if not (a >= b) ^ bef:
			i_p[i] = pos
			i_p_max[pos] = i
		else:
			pos += 1
			i_p[i] = pos
			bef = a >= b
			i_p_min[pos] = i
			i_p_max[pos] = i
		seg.data[seg.N0 + pos] += abs(a - b)
		tot += b - a
		seg_min.data[seg_min.N0 + i + 1] = tot
		seg_max.data[seg_min.N0 + i + 1] = tot
	seg.f5()
	seg_min.f5()
	seg_max.f5()
	for _ in range(q):
		(l, r) = map(int, input().split())
		if cum[r] - cum[l - 1] != 0:
			print(-1)
			continue
		l -= 1
		r -= 1
		if seg_min.data[seg_min.N0 + l] > seg_min.query(l, r + 1):
			print(-1)
			continue
		print(seg_max.query(l, r + 1) - seg_min.query(l, r + 1))
		continue
		posl = i_p[l]
		posr = i_p[r]
		al = abs(cum[l] - cum[i_p_min[posl]])
		ar = abs(cum[i_p_max[posr] + 1] - cum[r + 1])
		seg.add(posl, -al)
		seg.add(posr, -ar)
		print(seg.query(posl, posr + 1))
		seg.add(posl, al)
		seg.add(posr, ar)
for _ in range(1):
	main()


def naiveSolve():
	return

def solve():
	return
import math

class RMQMIN:

	def __init__(self, arr):
		self.arr = arr
		MAXN = len(arr)
		K = int(math.log2(MAXN)) + 1
		self.lookup = [[0 for _ in range(K + 1)] for __ in range(MAXN)]
		self.buildSparseTable()

	def buildSparseTable(self):
		n = len(self.arr)
		for i in range(0, n):
			self.lookup[i][0] = self.arr[i]
		j = 1
		while 1 << j <= n:
			i = 0
			while i + (1 << j) - 1 < n:
				self.lookup[i][j] = min(self.lookup[i][j - 1], self.lookup[i + (1 << j - 1)][j - 1])
				i += 1
			j += 1

	def query(self, L, R):
		j = int(math.log2(R - L + 1))
		return min(self.lookup[L][j], self.lookup[R - (1 << j) + 1][j])

class RMQMAX:

	def __init__(self, arr):
		self.arr = arr
		MAXN = len(arr)
		K = int(math.log2(MAXN)) + 1
		self.lookup = [[0 for _ in range(K + 1)] for __ in range(MAXN)]
		self.buildSparseTable()

	def buildSparseTable(self):
		n = len(self.arr)
		for i in range(0, n):
			self.lookup[i][0] = self.arr[i]
		j = 1
		while 1 << j <= n:
			i = 0
			while i + (1 << j) - 1 < n:
				self.lookup[i][j] = max(self.lookup[i][j - 1], self.lookup[i + (1 << j - 1)][j - 1])
				i += 1
			j += 1

	def query(self, L, R):
		j = int(math.log2(R - L + 1))
		return max(self.lookup[L][j], self.lookup[R - (1 << j) + 1][j])

def main():
	(n, q) = readIntArr()
	a = readIntArr()
	b = readIntArr()
	for i in range(n):
		a[i] -= b[i]
	p = a.copy()
	for i in range(1, n):
		p[i] += p[i - 1]
	rmqMin = RMQMIN(p)
	rmqMax = RMQMAX(p)
	allans = []
	for _ in range(q):
		(l, r) = readIntArr()
		l -= 1
		r -= 1
		total = p[r]
		if l - 1 >= 0:
			total -= p[l - 1]
		if total != 0:
			allans.append(-1)
			continue
		prefixMax = rmqMax.query(l, r)
		if l - 1 >= 0:
			prefixMax -= p[l - 1]
		if prefixMax > 0:
			allans.append(-1)
			continue
		prefixMin = rmqMin.query(l, r)
		if l - 1 >= 0:
			prefixMin -= p[l - 1]
		allans.append(-prefixMin)
	multiLineArrayPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x):
	print('{}'.format(x))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
for _abc in range(1):
	main()


import math
import sys
input = sys.stdin.buffer.readline

def process(A, B, Q):
	S = [0]
	n = len(A)
	for i in range(n):
		ai = A[i]
		bi = B[i]
		di = bi - ai
		S.append(S[-1] + di)
	n = len(S)
	p = math.log(n) / math.log(2)
	p = math.ceil(p)
	p = 2 ** p
	min_tree = [None for i in range(2 * p - 1)]
	max_tree = [None for i in range(2 * p - 1)]
	for i in range(p):
		if i < n:
			min_tree[i] = S[i]
			max_tree[i] = S[i]
		else:
			min_tree[i] = float('inf')
			max_tree[i] = -1 * float('inf')
	for i in range(p, 2 * p - 1):
		i1 = 2 * p - 2 - i
		j1 = 2 * i1 + 1
		j2 = 2 * i1 + 2
		i_left = 2 * p - 2 - j1
		i_right = 2 * p - 2 - j2
		min_tree[i] = min(min_tree[i_left], min_tree[i_right])
		max_tree[i] = max(max_tree[i_left], max_tree[i_right])

	def find_max(l, r, start_l=0, start_r=p - 1, start_i=2 * p - 2):
		if start_i < 0:
			return
		if l == r:
			return max_tree[l]
		if l == start_l and r == start_r:
			return max_tree[start_i]
		i1 = 2 * p - 2 - start_i
		i_l = 2 * p - 2 - (2 * i1 + 2)
		i_r = 2 * p - 2 - (2 * i1 + 1)
		m1 = (start_l + start_r) // 2
		if l > m1:
			return find_max(l, r, start_l=m1 + 1, start_r=start_r, start_i=i_r)
		elif r <= m1:
			return find_max(l, r, start_l=start_l, start_r=m1, start_i=i_l)
		else:
			max1 = find_max(l, m1, start_l=start_l, start_r=m1, start_i=i_l)
			max2 = find_max(m1 + 1, r, start_l=m1 + 1, start_r=start_r, start_i=i_r)
			return max(max1, max2)

	def find_min(l, r, start_l=0, start_r=p - 1, start_i=2 * p - 2):
		assert start_l <= l <= r <= start_r
		if start_i < 0:
			return
		if l == r:
			return min_tree[l]
		if l == start_l and r == start_r:
			return min_tree[start_i]
		i1 = 2 * p - 2 - start_i
		i_l = 2 * p - 2 - (2 * i1 + 2)
		i_r = 2 * p - 2 - (2 * i1 + 1)
		m1 = (start_l + start_r) // 2
		if l > m1:
			return find_min(l, r, start_l=m1 + 1, start_r=start_r, start_i=i_r)
		elif r <= m1:
			return find_min(l, r, start_l=start_l, start_r=m1, start_i=i_l)
		else:
			min1 = find_min(l, m1, start_l=start_l, start_r=m1, start_i=i_l)
			min2 = find_min(m1 + 1, r, start_l=m1 + 1, start_r=start_r, start_i=i_r)
			return min(min1, min2)
	answer = []
	for (l, r) in Q:
		s1 = S[l - 1]
		s2 = S[r]
		if s1 != s2:
			answer.append(-1)
		else:
			my_min = find_min(l, r)
			my_max = find_max(l, r)
			if my_min - s1 < 0:
				answer.append(-1)
			else:
				answer.append(my_max - s1)
	return answer
(n, k) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
Q = []
for i in range(k):
	(l, r) = [int(x) for x in input().split()]
	Q.append([l, r])
answer = process(A, B, Q)
for x in answer:
	print(x)


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, q) = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = [A[i] - B[i] for i in range(n)]
S = [0]
for c in C:
	S.append(S[-1] + c)
LEN = len(S) + 1
Sparse_table0 = [S]
for i in range(LEN.bit_length() - 1):
	j = 1 << i
	B = []
	for k in range(len(Sparse_table0[-1]) - j):
		B.append(min(Sparse_table0[-1][k], Sparse_table0[-1][k + j]))
	Sparse_table0.append(B)

def query0(l, r):
	i = (r - l).bit_length() - 1
	return min(Sparse_table0[i][l], Sparse_table0[i][r - (1 << i)])
Sparse_table1 = [S]
for i in range(LEN.bit_length() - 1):
	j = 1 << i
	B = []
	for k in range(len(Sparse_table1[-1]) - j):
		B.append(max(Sparse_table1[-1][k], Sparse_table1[-1][k + j]))
	Sparse_table1.append(B)

def query1(l, r):
	i = (r - l).bit_length() - 1
	return max(Sparse_table1[i][l], Sparse_table1[i][r - (1 << i)])
for queries in range(q):
	(l, r) = map(int, input().split())
	NOW = S[l - 1]
	MIN = query0(l, r + 1)
	MAX = query1(l, r + 1)
	if NOW == MAX and S[r] == NOW:
		print(MAX - MIN)
	else:
		print(-1)


import sys
(n, q) = [int(i) for i in sys.stdin.readline().split()]
a = [int(i) for i in sys.stdin.readline().split()]
b = [int(i) for i in sys.stdin.readline().split()]
d = [a[i] - b[i] for i in range(n)]
sd = [0]
for i in d:
	sd.append(sd[-1] + i)
(ma, mi) = ([[]], [[]])
ma[0] = mi[0] = sd
for i in range(1, 17):
	l = 1 << i - 1
	ma.append([max(ma[-1][j], ma[-1][j + l]) for j in range(len(sd) - l * 2 + 1)])
	mi.append([min(mi[-1][j], mi[-1][j + l]) for j in range(len(sd) - l * 2 + 1)])
for _ in range(q):
	(a, b) = [int(i) for i in sys.stdin.readline().split()]
	l = (b - a).bit_length() - 1
	m1 = max(ma[l][a], ma[l][b + 1 - (1 << l)])
	m2 = min(mi[l][a], mi[l][b + 1 - (1 << l)])
	sys.stdout.write('%d\n' % (m1 - m2 if m1 == sd[a - 1] and m1 == sd[b] else -1))


import sys
input = sys.stdin.readline

class segtree:

	def __init__(self, Size, op, e, A=[]):
		self.op = op
		for i in range(Size):
			if Size <= 1 << i:
				self.LeavesSize = 1 << i
				break
		self.e = e
		self.Tree = [e] * (self.LeavesSize * 2)
		for i in range(len(A)):
			self.Tree[i + self.LeavesSize - 1] = A[i]
		self.make()

	def make(self, i=0):
		if i < self.LeavesSize - 1:
			self.Tree[i] = self.op(self.make(i * 2 + 1), self.make(i * 2 + 2))
		return self.Tree[i]

	def __getitem__(self, key):
		return self.Tree[key + self.LeavesSize - 1]

	def push(self, Index, Value):
		Index += self.LeavesSize - 1
		self.Tree[Index] = Value
		while Index != 0:
			Index = (Index - 1) // 2
			self.Tree[Index] = self.op(self.Tree[Index * 2 + 1], self.Tree[Index * 2 + 2])

	def get(self, A, B, Index=0, L=0, R=-1):
		if Index == 0:
			R = self.LeavesSize
		if B <= L or R <= A:
			return self.e
		if A <= L and R <= B:
			return self.Tree[Index]
		return self.op(self.get(A, B, Index * 2 + 1, L, (L + R) // 2), self.get(A, B, Index * 2 + 2, (L + R) // 2, R))

	def add(self, Index, Value):
		Value += self.Tree[Index + self.LeavesSize - 1]
		self.push(Index, Value)

	def output(self):
		p1 = 0
		p2 = 1
		print(*self.Tree[p1:p1 + p2])
		while p2 != self.LeavesSize:
			p1 += p2
			p2 *= 2
			print(*self.Tree[p1:p1 + p2])
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = [0] + [A[i] - B[i] for i in range(N)]
for i in range(N):
	C[i + 1] += C[i]
TreeMax = segtree(N, max, -10 ** 18, C)
TreeMin = segtree(N, min, 10 ** 18, C)
for _ in range(Q):
	(L, R) = map(int, input().split())
	L -= 1
	if C[R] - C[L] != 0 or TreeMax.get(L, R) - C[L] > 0:
		print(-1)
	else:
		print(C[L] - TreeMin.get(L, R))


class SegmentTree:

	def __init__(self, data, default=0, func=max):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		start += self._size
		stop += self._size
		res_left = res_right = self._default
		while start < stop:
			if start & 1:
				res_left = self._func(res_left, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res_right = self._func(self.data[stop], res_right)
			start >>= 1
			stop >>= 1
		return self._func(res_left, res_right)

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
data = [0]
for i in range(n):
	data.append(a[i] - b[i] + data[-1])
minSeg = SegmentTree(data, default=float('inf'), func=min)
maxSeg = SegmentTree(data, default=float('-inf'), func=max)
out = []
for _ in range(q):
	(l, r) = map(int, input().split())
	if data[l - 1] != data[r]:
		out.append(-1)
		continue
	start = data[l - 1]
	smol = minSeg.query(l - 1, r)
	tol = maxSeg.query(l - 1, r)
	if tol == start:
		out.append(start - smol)
	else:
		out.append(-1)
print('\n'.join(map(str, out)))


import io, os
import bisect
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

class segment_tree(object):

	def merge(self, num1, num2):
		maximum = max(num1[0], num2[0])
		minimum = min(num1[1], num2[1])
		return (maximum, minimum)

	def __init__(self, n, initial):
		self.n = n
		self.arr = [(0, 0)] * (2 * n)
		for i in range(2 * n - 1, 0, -1):
			if i >= n:
				self.arr[i] = (initial[i - n], initial[i - n])
			else:
				self.arr[i] = self.merge(self.arr[2 * i], self.arr[2 * i + 1])

	def query(self, left, right):
		(i, j) = (self.n + left, self.n + right + 1)
		output = (-float('inf'), float('inf'))
		while i < j:
			if i & 1:
				output = self.merge(self.arr[i], output)
				i += 1
			if j & 1:
				j -= 1
				output = self.merge(self.arr[j], output)
			i = i >> 1
			j = j >> 1
		return output

def main(t):
	(n, q) = map(int, input().split())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	diff = [0] * n
	for i in range(n):
		diff[i] = arr2[i] - arr1[i]
	accu = [0] * (n + 1)
	accu[0] = 0
	pos = []
	for i in range(n):
		accu[i + 1] = accu[i] + diff[i]
		if diff[i] != 0:
			pos.append(i)
	seg = segment_tree(n + 1, accu)
	for _ in range(q):
		(front, rear) = map(int, input().split())
		front -= 1
		(maximum, minimum) = seg.query(front, rear)
		if accu[front] == minimum and accu[rear] == minimum:
			ans = maximum - minimum
		else:
			ans = -1
		print(ans)
T = 1
t = 1
while t <= T:
	main(t)
	t += 1


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n, mod=0):
		self.BIT = [0] * (n + 1)
		self.num = n
		self.mod = mod

	def query(self, idx):
		res_sum = 0
		mod = self.mod
		while idx > 0:
			res_sum += self.BIT[idx]
			if mod:
				res_sum %= mod
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		mod = self.mod
		while idx <= self.num:
			self.BIT[idx] += x
			if mod:
				self.BIT[idx] %= mod
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		self.size = n
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			k >>= 1
			self.tree[k] = self.segfunc(self.tree[2 * k], self.tree[2 * k + 1])

	def query(self, l, r):
		if r == self.size:
			r = self.num
		res = self.ide_ele
		l += self.num
		r += self.num
		right = []
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				right.append(self.tree[r - 1])
			l >>= 1
			r >>= 1
		for e in right[::-1]:
			res = self.segfunc(res, e)
		return res

def merge(x, y):
	return (x[0] + y[0], min(x[1], x[0] + y[1]), max(x[2], x[0] + y[2]))
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.buffer.readline()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
(n, q) = mi()
A = li()
B = li()
C = [A[i] - B[i] for i in range(n)]
for i in range(n):
	if C[i] > 0:
		C[i] = (C[i], 0, C[i])
	else:
		C[i] = (C[i], C[i], 0)
C = C[::-1]
Seg = SegmentTree(C, merge, (0, 0, 0))
for _ in range(q):
	(l, r) = mi()
	(l, r) = (l - 1, r - 1)
	(L, R) = (n - 1 - r, n - 1 - l)
	check = Seg.query(L, R + 1)
	if check[0] == 0 and check[1] == 0:
		print(check[2])
	else:
		print(-1)