E. Миша и LCP на дереве
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
512 мегабайт
ввод
stdin
вывод
stdout

У Миши есть дерево с написанными на вершинах символами. Он может выбрать две вершины s и t этого дерева и записать символы, соответствующие вершинам дерева, лежащим на пути из s в t. Будем говорить, что такая строка соответствует паре (s, t).

У Миши есть m запросов вида: дано 4 вершины a, b, c, d; необходимо найти наибольший общий префикс строк, соответствующих парам (a, b) и (c, d). Ваша задача — помочь ему.

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

В первой строке дано целое число n (1 ≤ n ≤ 300 000) — количество вершин в дереве.

Далее следует строка, состоящая из n маленьких латинских букв. i-й символ строки соответствует символу, написанному на i-й вершине.

В последующих n - 1 строках находится информация о ребрах. Ребро задается парой чисел u, v (1 ≤ u, v ≤ n, u ≠ v), разделенных пробелом.

В следующей строке дано целое число m (1 ≤ m ≤ 1 000 000) — количество запросов.

В последующих m строках находится информация о запросах. Запрос задается четырьмя числами a, b, c, d (1 ≤ a, b, c, d ≤ n), разделенными пробелами.

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

На каждый запрос выведите длину наибольшего общего префикса в отдельной строке.

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