Вам дана последовательность $$$a$$$ длины $$$n-1$$$ и последовательность $$$b$$$ длины $$$n$$$.
Вы можете выполнять следующую операцию любое количество раз (возможно, ноль):
Ваша цель — выполнить минимальное количество операций, чтобы для каждого $$$1 \le i \le n-1$$$ выполнялось условие $$$b_i \, \& \, b_{i+1} = a_i$$$, где $$$\&$$$ обозначает операцию побитового И. Если невозможно удовлетворить всем условиям, также сообщите об этом.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^5$$$).
Вторая строка содержит $$$n-1$$$ целых чисел $$$a_1, a_2, \ldots, a_{n-1}$$$ ($$$0 \le a_i \lt 2^{29}$$$).
Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \lt 2^{29}$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.
Для каждого набора входных данных вам нужно вывести только одно целое число.
Если цель может быть достигнута, выведите одно целое число — минимальное количество необходимых операций. В противном случае выведите $$$-1$$$.
741 4 41 2 3 444 0 41 1 1 1210 031 10 1 261 2 3 4 51 1 4 5 1 4200 040 1 0536870911 536870911 536870911 536870911
4 -1 2 2 -1 0 536870916
В первом наборе входных данных одной из оптимальных стратегий является использование $$$4$$$ операций, чтобы сделать $$$b = [1,5,4,4]$$$, что удовлетворяет всем условиям. Мы можем доказать, что невозможно использовать менее чем $$$4$$$ операций.
Во втором наборе входных данных, поскольку $$$b_1 \, \& \, b_2 = 4$$$ и $$$b_2 \, \& \, b_3 =0$$$, то $$$b_3 \, \& \, 4 =0$$$. Однако мы требуем, чтобы $$$b_3 \, \& \, b_4 =4$$$, что означает, что невозможно удовлетворить всем условиям.
| Codeforces Round 1035 (Div. 2) |
|---|
| Закончено |
