У Василия есть два массива \(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\) прибавляется единица.
Василия интересует, можно ли уравнять значения элементов двух массивов для каждого отрезка, используя некоторое количество операций балансировки, и какое минимальное количество операций для этого потребуется. Обратите внимание, что для каждого отрезка операции проводятся независимо.
Примечание
Для первого отрезка от \(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\) после этой операции совпадают.
Для четвертого и пятого отрезков добиться равенства невозможно.