Иллюзия XOR-а
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Во время грандиозного шоу иллюзионистов город из $$$n$$$ сцен соединён системой секретных ходов. Каждая сцена — это вершина, каждый ход между двумя сценами — это ребро. Всего ходов $$$n-1$$$, и вместе они образуют дерево.

На каждом ребре написано число $$$w$$$ — «сила иллюзии», с которой зритель переносится между двумя сценами.

Рассмотрим любой маршрут шоу — последовательность различных сцен $$$$$$u_1, u_2, \dots, u_k$$$$$$ где $$$k \geq 2$$$ и соседние сцены соединены прямым секретным ходом. Такой маршрут не может самопересекаться (одна и та же сцена не может появляться более одного раза).

Красотой маршрута назовём XOR всех сил иллюзий на этом пути:

$$$$$$w_{u_1 \rightarrow u_2} \oplus w_{u_2 \rightarrow u_3} \oplus \dots \oplus w_{u_{k - 1} \rightarrow u_k}.$$$$$$

Организаторы шоу хотят знать, сколько существует различных маршрутов с заданной красотой иллюзии.

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

Первая строка содержит число $$$n$$$ — количество сцен ($$$2 \leq n \leq 2 \cdot 10^5$$$).

В следующих $$$n - 1$$$ строках описаны секретные ходы: каждая строка содержит три числа $$$u, v, w$$$ — номера двух сцен и силу иллюзии на ходе между ними ($$$1 \leq u, v \leq n$$$; $$$0 \leq w < 2^{20}$$$).

Далее задано число запросов $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$).

В каждой из следующих $$$q$$$ строк записано число $$$f$$$ — требуемая красота маршрута ($$$0 \leq f < 2^{20}$$$).

Гарантируется, что заданный граф является деревом.

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

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

Примеры

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

    31 2 02 3 13012

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

    1
    2
    0

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

    31 2 102 3 530515

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

    0
    1
    1