Statement is not available in English language
I. Объединение деревьев
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть два корневых дерева $$$t_1$$$ и $$$t_2$$$, состоящие из $$$n_1$$$ и $$$n_2$$$ вершин соответственно.

Корневое дерево — это дерево с выделенной вершиной, которую называют корнем.

В каждой вершине деревьев $$$t_1$$$ и $$$t_2$$$ записано целое число — вес данной вершины.

Весом дерева называется целое число, которое получается при последовательном выполнении следующих двух операций:

  1. Спуститься по дереву от корня до каждого листа, считая XOR весов всех вершин на пути.
  2. Сложить получившиеся значения для всех листов.

XOR — это операция побитового исключающего ИЛИ, обозначаемая символом $$$\oplus$$$. При вычислении выражения $$$a \oplus b$$$ каждый бит результата будет равен $$$0$$$, если соответствующие биты чисел $$$a$$$ и $$$b$$$ равны, и равен $$$1$$$ иначе.

Например, вес дерева на рисунке равен 16. Он может быть рассчитан следующим образом:

  1. XOR весов на пути до первого листа равен $$$3 \oplus 6 = 5$$$.
  2. XOR весов на пути до второго листа равен $$$3 \oplus 4 = 7$$$.
  3. XOR весов на пути до третьего листа равен $$$3 \oplus 2 \oplus 1 = 0$$$.
  4. XOR весов на пути до четвёртого листа равен $$$3 \oplus 2 \oplus 5 = 4$$$.
  5. Вес всего дерева равен $$$5 + 7 + 0 + 4 = 16$$$.
Корневое дерево из 6 вершин.

Вам необходимо подвесить одно из деревьев за другое таким образом, чтобы вес полученного дерева получился максимальным.

Другими словами, необходимо выполнить одну из следующих операций:

  • Выбрать вершину $$$i$$$ ($$$1 \le i \le n_1$$$) в дереве $$$t_1$$$ и провести от неё ребро к вершине, являющейся корнем дерева $$$t_2$$$.
  • Выбрать вершину $$$j$$$ ($$$1 \le j \le n_2$$$) в дереве $$$t_2$$$ и провести от неё ребро к вершине, являющейся корнем дерева $$$t_1$$$.

В результате получится новое дерево $$$t$$$, состоящее из $$$n_1 + n_2$$$ вершин. Необходимо найти дерево $$$t$$$ такое, вес которого будет максимальным среди всех возможных деревьев, которые можно получить выполнением одной из операций выше.

Входные данные

В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит ровно одно целое число $$$n_1$$$ ($$$1 \le n_1 \le 10^5$$$) — количество вершин в дереве $$$t_1$$$.

Вторая строка каждого набора входных данных содержит ровно $$$n_1$$$ целых чисел — элементы массива $$$w_1$$$, где $$$w_{1_i}$$$ ($$$1 \le w_{1_i} \le 10^9$$$) описывает вес в вершине дерева $$$t_1$$$ с номером $$$i$$$ ($$$1 \le i \le n_1$$$).

Третья строка каждого набора входных данных содержит ровно $$$n_1$$$ целых чисел — элементы массива $$$p_1$$$ предков дерева $$$t_1$$$. Элемент $$$p_{1_i}$$$ содержит номер родителя вершины $$$i$$$. Если $$$p_{1_i} = i$$$, то вершина $$$i$$$ является корнем дерева $$$t_1$$$.

Четвёртая строка каждого набора входных данных содержит ровно одно целое число $$$n_2$$$($$$1 \le n_2 \le 10^5$$$) — количество вершин в дереве $$$t_2$$$.

Пятая строка каждого набора входных данных содержит ровно $$$n_2$$$ целых чисел — элементы массива $$$w_2$$$, где $$$w_{2_i}$$$ ($$$1 \le w_{2_i} \le 10^9$$$) описывает вес в вершине дерева $$$t_2$$$ с номером $$$i$$$ ($$$1 \le i \le n_2$$$).

Шестая строка каждого набора входных данных содержит ровно $$$n_2$$$ целых чисел — элементы массива $$$p_2$$$ предков дерева $$$t_2$$$. Элемент $$$p_{2_i}$$$ содержит номер родителя вершины $$$i$$$. Если $$$p_{2_i} = i$$$, то вершина $$$i$$$ является корнем дерева $$$t_2$$$.

Гарантируется, что сумма $$$n_1$$$ и $$$n_2$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных на отдельной строке выведите ровно одно число — максимальный вес, который можно получить, если подвесить одно дерево за другое.

Пример
Входные данные
3
6
3 6 4 2 1 5
1 1 1 1 4 4
3
1 1 1
1 1 1
2
100 101
1 1
2
1 1
2 2
4
6 6 6 1
4 3 4 4
4
10000 1 1 10000
2 3 3 2
Выходные данные
23
101
30008
Примечание

В первом наборе входных данных

  • Вес дерева $$$t_1$$$ равен $$$16$$$ — оно соответствует дереву, приведённому в тексте условия.
  • Вес дерева $$$t_2$$$ равен $$$0$$$. Оно состоит из $$$3$$$-х узлов, два из которых являются листьями, поэтому вес вычисляется как $$$(1 \oplus 1) + (1 \oplus 1) = 0 + 0 = 0$$$.

Дерево $$$t$$$ максимального веса может быть получено, если подвесить дерево $$$t_2$$$ к вершине номер $$$3$$$ (имеющей вес $$$4$$$) дерева $$$t_1$$$, как показано на рисунке ниже:

Вес данного дерева равен $$$23$$$.