William 有两个数组 $$$a$$$ 和 $$$b$$$,每个数组由 $$$n$$$ 项组成。
对于这些数组的某些段 $$$l..r$$$,William 想知道是否可以使用平衡操作来均衡这些段中项目的值。形式上,如果对于从 $$$l$$$ 到 $$$r$$$ 的每个 $$$i$$$ 都满足 $$$a_i = b_i$$$,则这些值相等。
要执行平衡操作,必须选择偶数个索引,使得 $$$l \le pos_1 < pos_2 < \dots < pos_k \le r$$$。接下来,数组 a 中位置 $$$pos_1、pos_3、pos_5、\dots$$$ 处的项递增 1,数组 b 中位置 $$$pos_2、pos_4、pos_6、\dots$$$ 处的项递增 1。
William 想知道是否可以使用一定数量的平衡操作来均衡每个段的两个数组中的元素值,以及所需的最少操作数量是多少。请注意,对于每个段,操作都是独立执行的。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le q \le 10^5$$$),数组 $$$a$$$ 和 $$$b$$$ 的大小以及段数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ $$$(0 \le a_i \le 10^9)$$$。
第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ $$$(0 \le b_i \le 10^9)$$$。
接下来的 $$$q$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ $$$(1 \le l_i < r_i \le n)$$$,即段的边缘。
输出
对于每个段,输出一个数字 - 所需的平衡操作的最小数量,如果不可能均衡数组段,则为“-1”。
示例
输入 #1
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
输出 #1
1 3 1 -1 -1
注意
对于从 $$$2$$$ 到 $$$6$$$ 的第一段,您可以使用 $$$pos = [2, 3, 5, 6]$$$ 进行一次操作,在此操作之后,数组将是: $$$a = [0, 2, 2, 9, 4, 2, 7, 5]$$$, $$$b = [2, 2, 2, 9, 4, 2, 5, 8]$$$。执行此操作后,从 $$$2$$$ 到 $$$6$$$ 的段上的数组相等。
对于从 $$$1$$$ 到 $$$7$$$ 的第二段,您可以执行以下三个操作:
1. $$$位置 = [1, 3, 5, 6]$$$
2. $$$位置 = [1, 7]$$$
3. $$$位置 = [2, 7]$$$
经过这些操作,数组将是:$$$a = [2, 2, 2, 9, 4, 2, 7, 5]$$$,$$$b = [2, 2, 2, 9, 4, 2, 7, 8]$$$。经过这些操作后,从 $$$1$$$ 到 $$$7$$$ 的段上的数组相等。
对于从 $$$2$$$ 到 $$$4$$$ 的第三段,您可以使用 $$$pos = [2, 3]$$$ 进行一次操作,操作后数组将是: $$$a = [0, 2, 2, 9, 3, 2, 7, 5]$$$, $$$b = [2, 2, 2, 9, 4, 1, 5, 8]$$$。执行此操作后,从 $$$2$$$ 到 $$$4$$$ 的段上的数组相等。
不可能使第四段和第五段相等。