G. Ваша потеря
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано дерево с $$$n$$$ вершинами, пронумерованными от $$$1$$$ до $$$n$$$, а также массив длины $$$n$$$. Значение $$$i$$$-й вершины — $$$a_{i}$$$. Имеется $$$q$$$ запросов. В каждом запросе даны 2 вершины с номерами $$$x$$$ и $$$y$$$.

Рассмотрим путь от вершины с номером $$$x$$$ до вершины с номером $$$y$$$. Пусть путь представлен в виде $$$x = p_0, p_1, p_2, \ldots, p_r = y$$$, где $$$p_i$$$ — промежуточные вершины. Вычислите сумму $$$a_{p_i}\oplus i$$$ по всем $$$i$$$ таким, что $$$0 \le i \le r$$$, где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

Более формально, вычислите $$$$$$\sum_{i =0}^{r} a_{p_i}\oplus i$$$$$$

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

Следующие $$$n-1$$$ строк каждого набора входных данных содержат по $$$2$$$ целых числа $$$u$$$ и $$$v$$$, представляющих собой ребро между вершиной с номером $$$u$$$ и вершиной с номером $$$v$$$. Гарантируется, что $$$u \ne v$$$, и что ребра образуют дерево.

Следующая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 5 \cdot 10^5$$$) — значения вершин.

Следующая строка содержит одно целое число $$$q$$$ ($$$1 \le q \le 10^5$$$) — количество запросов.

Следующие $$$q$$$ строк описывают запросы. В $$$i$$$-м запросе содержится $$$2$$$ целых числа $$$x$$$ и $$$y$$$ ($$$1 \le x,y \le n$$$), обозначающих начальную и конечную вершину пути.

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

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

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

Пример
Входные данные
1
4
1 2
2 3
3 4
2 3 6 5
3
1 4
3 4
1 1
Выходные данные
14
10
2