I. Брачное агенство
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Эта история происходит в городе BubbleLand. В этом городе есть n домов. В каждом из этих n домов живет мальчик или девочка. В этом городе люди действительно любят числа, и у каждого есть свое любимое число f. Это означает, что мальчик или девочка, живущие в городе в i-м доме, имеют свое любимое число, равное fi.

Дома пронумерованы числами от 1 до n.

Дома соединены n - 1 двунаправленными дорогами, от любого дома возможно добраться до любого другого. Между каждой парой домов есть ровно один путь.

Новое брачное агенство открыло свои офисы в этом странном городе, и жители были восхищены. Они сразу же отправили q запросов в агенство, каждый запрос был в следующем формате:

  • a b — спрашивает, сколько есть способов выбрать пару (мальчик и девочка) такую, что они имеют одинаковое любимое число и живут в домах, находящимся на уникальном пути от дома a до дома b.

Помогите брачному агенству ответить на запросы и расширить их бизнес.

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

Первая строка содержит одно целое число n (1 ≤ n ≤ 105) — число домов в городе.

Вторая строка содержит n целых чисел, i-е из этих чисел равно 1, если в i-м доме живет мальчик, и 0, если в i-м доме живет девочка.

Третья строка содержит n целых чисел, где i-е число равно любимому числу fi (1 ≤ fi ≤ 109) девочки или мальчика, живущих в i-м доме.

Следующие n - 1 строк содержат информацию о дорогах, i-я из них содержит два целых числа ai и bi (1 ≤ ai, bi ≤ n), которые означают, что есть дорога между этими двумя домами. Гарантируется, что от любого дома можно добраться до любого другого по дорогам.

Следующая строка содержит одно целое число q (1 ≤ q ≤ 105) — число запросов.

Каждая из следующих q строк описывает запрос и содержит два целых числа a и b (1 ≤ a, b ≤ n).

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

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

Пример
Входные данные
7
1 0 0 1 0 1 0
9 2 9 2 2 9 9
2 6
1 2
4 2
6 5
3 6
7 4
2
1 3
7 5
Выходные данные
2
3
Примечание

В первом вопросе на пути от дома 1 до дома 3 потенциальными парами являются (1, 3) и (6, 3).

Во втором вопросе на пути от дома 7 до дома 5 потенциальными парами являются (7, 6), (4, 2) и (4, 5).