Недавно на голову Боба с неба упало дерево. В дереве \(n\) вершин. В каждой вершине \(u\) дерева записано целое число \(a_u\). В дереве нет фиксированного корня, так как оно упало с неба.
В настоящее время Боб изучает дерево. Чтобы внести некоторую изюминку, Алиса предлагает игру. Сначала Боб выбирает некоторую вершину \(r\) корнем дерева. После этого Алиса выберет вершину \(v\) и сообщит ее Бобу. Затем Боб выберет одну или несколько вершин из поддерева вершины \(v\). Его результат будет равен побитовому исключающему ИЛИ всех значений, записанных в выбранных им вершинах. Боб должен сказать, какой максимальный результат он может получить для заданных \(r\) и \(v\).
Поскольку Боб не умеет решать задачи, он просит вас помочь ему найти ответ. Сможете ли вы ему помочь? Вам нужно найти ответ для нескольких комбинаций \(r\) и \(v\) для одного дерева.
Напомним, что дерево — это связный неориентированный граф без циклов. Поддерево вершины \(u\) — это множество всех вершин \(y\) таких, что простой путь от \(y\) до корня проходит через \(u\). Обратите внимание, что вершина \(u\) входит в поддерево вершины \(u\).
Выходные данные
Для каждого набора входных данных для каждого запроса выведите строку, содержащую целое число, обозначающее максимальный результат, который может получить Боб.
Примечание
На каждом из приведенных ниже рисунков вершина, окрашенная в зеленый цвет — это вершина, выбранная Бобом, а вершина, окрашенный в красный цвет — это вершина, выбранная Алисой. Значения вершин помещены в синие ячейки рядом с вершинами.
Рассмотрим первый пример. В первом запросе, если мы примем вершину \(4\) за корень, дерево будет выглядеть так, как показано на рисунке ниже:
Дерево с корнем \(4\) в первом запросе. Вершинами в поддереве
\(2\) являются:
\([2,1,5,6,3]\). Среди них Боб может выбрать вершину
\(3\),
\(5\) и
\(6\). Его результат будет следующим:
\(a_3 \oplus a_5 \oplus a_6 = 8 \oplus 6 \oplus 1 = 15\). Он не может набрать больше этого значения.
Во втором запросе, если сделать корнем \(3\), то дерево будет выглядеть так:
Дерево с корнем \(3\) во втором запросе. Единственной вершиной в поддереве
\(5\) является
\(5\). Боб может выбрать только вершину
\(5\). Его результатом будет
\(a_5 = 6\).
В третьем запросе, если корень — \(1\), то дерево выглядит следующим образом:
Дерево с корнем \(1\) в третьем запросе. Вершинами в поддереве
\(2\) являются:
\([2,3,6,4]\). Среди них Боб может выбрать вершину
\(2\),
\(3\) и
\(4\). Его результат будет следующим:
\(a_2 \oplus a_3 \oplus a_4 = 12 \oplus 8 \oplus 25 = 29\). Он не может набрать больше этой суммы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6
12 12 8 25 6 1
1 5
1 2
2 6
2 3
2 4
3
4 2
3 5
1 2
2
3 8
1 2
4
2 2
2 1
1 2
1 1
3
3 8 7
1 2
2 3
2
2 2
2 1
|
15
6
29
11
3
8
11
15
3
|