У Василия есть два массива $$$a$$$ и $$$b$$$, состоящие из $$$n$$$ элементов.
Для некоторых отрезков $$$l..r$$$ этих массивов Василий хочет узнать, можно ли уравнять значения массивов на этих отрезках, используя операцию балансировки. Формально говоря, значения на отрезке уравнены, если для всех $$$i$$$ от $$$l$$$ до $$$r$$$ выполняется $$$a_i = b_i$$$.
Для того, чтобы выполнить операцию балансировки, необходимо выбрать четное количество индексов массива $$$l \le pos_1 < pos_2 < \dots < pos_k \le r$$$. Далее к элементам массива a на позициях $$$pos_1, pos_3, pos_5, \dots$$$ прибавляется единица и к элементам массива b на позициях $$$pos_2, pos_4, pos_6, \dots$$$ прибавляется единица.
Василия интересует, можно ли уравнять значения элементов двух массивов для каждого отрезка, используя некоторое количество операций балансировки, и какое минимальное количество операций для этого потребуется. Обратите внимание, что для каждого отрезка операции проводятся независимо.
Первая строка содержит два целых числа $$$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», если сделать отрезки массива одинаковыми не получится.
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 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$$$ можно сделать три следующие операции:
- $$$pos = [1, 3, 5, 6]$$$
- $$$pos = [1, 7]$$$
- $$$pos = [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$$$ после этой операции совпадают.
Для четвертого и пятого отрезков добиться равенства невозможно.
