Вам дано дерево с \(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\(\)
Выходные данные
Для каждого запроса выведите одно число — искомую сумму.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
4
1 2
2 3
3 4
2 3 6 5
3
1 4
3 4
1 1
|
14
10
2
|