Мінімізуйте суму#12877

Мінімізуйте суму

Табличка n \times m заповнена невід'ємними числами. Андрійко з'ясував, що всіх чисел в -му рядку рівний row_i (для від до ), а всіх чисел в -му стовпчику рівний col_i (для від до ).

Чи міг Андрійко сказати правду? Якщо так, то якою найменшою могла бути сума всіх чисел в табличці?

Нагадаємо, що позначає операцію побітового виключного АБО. Наприклад, 13 \text{ } XOR \text{ } 6 = 11, адже в двійковому записі 1101, а 0110, тому їх має бути рівним 1011 .

Input

Перший рядок містить єдине ціле число (1 \le t \le 10^4)  — кількість наборів вхідних даних. Далі слідує опис наборів вхідних даних.

Перший рядок кожного набору вхідних даних містить два цілих числа (1 \le n, m \le 2\cdot 10^5)  — кількості рядків та стовпчиків відповідно.

Другий рядок кожного набору вхідних даних містить цілих чисел row_1, row_2, \ldots, row_n (0 \le row_i < 2^{20}).

Третій рядок кожного набору вхідних даних містить цілих чисел col_1, col_2, \ldots, col_m (0 \le col_i < 2^{20}).

Гарантується, що сума по всім наборам вхідних даних не перевищує 2\cdot 10^5, а також що сума по всім наборам вхідних даних не перевищує 2\cdot 10^5.

Output

Для кожного набору вхідних даних, якщо такої таблички не могло існувати, виведіть . Інакше, виведіть мінімальну можливу суму всіх чисел в табличці, в якій всіх чисел в -му рядку рівний row_i (для від до ), а всіх чисел в -му стовпчику рівний col_i (для від до ).

Examples

Example 1

Loading
Loading

Note

В першому наборі вхідних даних можна просто заповнити всю таблицю нулями. в кожному рядочку та стовпчику буде рівний . Очевидно, що отримати меншу суму неможливо.

В другому наборі вхідних даних можна показати, що такої таблиці не може існувати.

В третьому наборі вхідних даних один з прикладів заповнення таблиці такий: